Course Outline
Bahador Bakhshi
Department of Computer Engineering
Amirkabir University of Technology
September 13, 2014
Bahador Bakhshi (CE@AUT)
September 13, 2014
1 / 17
Outline
Outline
1
Course Introduction
2
Syllabus
3
Policies
4
Text Books & References
Bahador Bakhshi (CE@AUT)
September 13, 2014
2 / 17
Course Introduction
Outline
1
Course Introduction
2
Syllabus
3
Policies
4
Text Books & References
Bahador Bakhshi (CE@AUT)
September 13, 2014
3 / 17
Course Introduction
What this course is
Optimization
Application in Networking
Bahador Bakhshi (CE@AUT)
September 13, 2014
4 / 17
Course Introduction
What this course is
Optimization
What is the optimization theory?
Operation Research!
Mathematical Programming!!!
Application in Networking
Bahador Bakhshi (CE@AUT)
September 13, 2014
4 / 17
Course Introduction
What this course is
Optimization
What is the optimization theory?
Operation Research!
Mathematical Programming!!!
Application in Networking
Apply optimization techniques on networking problems
Network design problems
Performance bound on heuristic algorithms
Bahador Bakhshi (CE@AUT)
September 13, 2014
4 / 17
Course Introduction
What are Optimization Problems?
Very popular kind of problems in real life
When we want to find the best
Bahador Bakhshi (CE@AUT)
September 13, 2014
5 / 17
Course Introduction
What are Optimization Problems?
Very popular kind of problems in real life
When we want to find the best
Best route to go from point A to point B
Best location for vacation
Best university to study
Minimizing power consumption in the network
Minimizing cost of network
Maximizing network throughput
...
Bahador Bakhshi (CE@AUT)
September 13, 2014
5 / 17
Course Introduction
What are Optimization Problems?
An objective
Shortest Path, Minimum delay path, ...
Bahador Bakhshi (CE@AUT)
September 13, 2014
6 / 17
Course Introduction
What are Optimization Problems?
An objective
Shortest Path, Minimum delay path, ...
Set of constraints
Start from source, Maximum delay, ...
Bahador Bakhshi (CE@AUT)
September 13, 2014
6 / 17
Course Introduction
What are Optimization Problems?
An objective
Shortest Path, Minimum delay path, ...
Set of constraints
Start from source, Maximum delay, ...
Multiple solutions that satisfy constraints
Route: A ⇒ B ⇒ C ⇒ D ⇒ Z
Route: A ⇒ W ⇒ X ⇒ Z
Bahador Bakhshi (CE@AUT)
September 13, 2014
6 / 17
Course Introduction
What are Optimization Problems?
An objective
Shortest Path, Minimum delay path, ...
Set of constraints
Start from source, Maximum delay, ...
Multiple solutions that satisfy constraints
Route: A ⇒ B ⇒ C ⇒ D ⇒ Z
Route: A ⇒ W ⇒ X ⇒ Z
However, with different value of objective
Bahador Bakhshi (CE@AUT)
September 13, 2014
6 / 17
Course Introduction
What are Optimization Problems?
An objective
Shortest Path, Minimum delay path, ...
Set of constraints
Start from source, Maximum delay, ...
Multiple solutions that satisfy constraints
Route: A ⇒ B ⇒ C ⇒ D ⇒ Z
Route: A ⇒ W ⇒ X ⇒ Z
However, with different value of objective
We should decide what to do in order to achieve the
objective
Select node B or W?
Bahador Bakhshi (CE@AUT)
September 13, 2014
6 / 17
Course Introduction
Optimization Theory
Mathematical foundation to solve these problems
Definition
General form of Optimization Problems
max
min
s.t
Bahador Bakhshi (CE@AUT)
f (x)
gi (x) ∼ 0 1 ≤ i ≤ m
September 13, 2014
7 / 17
Course Introduction
Optimization Theory
Mathematical foundation to solve these problems
Definition
General form of Optimization Problems
max
min
s.t
f (x)
gi (x) ∼ 0 1 ≤ i ≤ m
f (x): Objective function
g(x): Constraints
x: n × 1 vector, decision variables
Ω = {x | gi (x) ∼ 0, 1 ≤ i ≤ m}: Solution space
x ∈ Ω: A feasible solution
Bahador Bakhshi (CE@AUT)
September 13, 2014
7 / 17
Course Introduction
Learning Objectives
Optimization Theory
Problem Modeling
Optimization Tools
Bahador Bakhshi (CE@AUT)
September 13, 2014
8 / 17
Course Introduction
Learning Objectives
Optimization Theory
Problem classification
Unconstrained, Convex, LP, IP, ...
Algorithms
Problem Modeling
Optimization Tools
Bahador Bakhshi (CE@AUT)
September 13, 2014
8 / 17
Course Introduction
Learning Objectives
Optimization Theory
Problem classification
Unconstrained, Convex, LP, IP, ...
Algorithms
Problem Modeling
Modeling techniques
Network optimization problems modeling
Optimization Tools
Bahador Bakhshi (CE@AUT)
September 13, 2014
8 / 17
Course Introduction
Learning Objectives
Optimization Theory
Problem classification
Unconstrained, Convex, LP, IP, ...
Algorithms
Problem Modeling
Modeling techniques
Network optimization problems modeling
Optimization Tools
Modeling languages
Solvers
Bahador Bakhshi (CE@AUT)
September 13, 2014
8 / 17
Course Introduction
What this course is not
Mathematical proofs
Details of algorithms
All available solvers, tools and modeling languages
Lot of (important) problems
Multi-objective
Stochastic
Online
...
Bahador Bakhshi (CE@AUT)
September 13, 2014
9 / 17
Syllabus
Outline
1
Course Introduction
2
Syllabus
3
Policies
4
Text Books & References
Bahador Bakhshi (CE@AUT)
September 13, 2014
10 / 17
Syllabus
Tentative Syllabus
Part-I: Preliminaries
Part-II: Optimization Theory
Part-III: (Networking) Applications
Bahador Bakhshi (CE@AUT)
September 13, 2014
11 / 17
Syllabus
Tentative Syllabus
Part-I: Preliminaries
Mathematical background review
Introduction to optimization
Part-II: Optimization Theory
Part-III: (Networking) Applications
Bahador Bakhshi (CE@AUT)
September 13, 2014
11 / 17
Syllabus
Tentative Syllabus
Part-I: Preliminaries
Mathematical background review
Introduction to optimization
Part-II: Optimization Theory
Unconstrained optimization
Constraint optimization (in General)
Convex optimization
Linear programming (LP)
Integer linear programming (ILP)
Network flow problems
Part-III: (Networking) Applications
Bahador Bakhshi (CE@AUT)
September 13, 2014
11 / 17
Syllabus
Tentative Syllabus
Part-I: Preliminaries
Mathematical background review
Introduction to optimization
Part-II: Optimization Theory
Unconstrained optimization
Constraint optimization (in General)
Convex optimization
Linear programming (LP)
Integer linear programming (ILP)
Network flow problems
Part-III: (Networking) Applications
Wired networks optimization problems
Wireless networks optimization problems
Bahador Bakhshi (CE@AUT)
September 13, 2014
11 / 17
Policies
Outline
1
Course Introduction
2
Syllabus
3
Policies
4
Text Books & References
Bahador Bakhshi (CE@AUT)
September 13, 2014
12 / 17
Policies
Assumptions
Familiar with wired & wireless networks and
fundamental problems
Love (like) mathematic (at least don’t hate)
Interested in theoretical aspect of networking
This course is very different that Network Management
or Internet Engineering
Everything is abstract model of real network
Bahador Bakhshi (CE@AUT)
September 13, 2014
13 / 17
Policies
Grading
Item
Total% Minimum
Midterm
35
40%
Final
35
40%
Homework
20
40%
Project
10
15% penalty per day for late submission of homework
Bahador Bakhshi (CE@AUT)
September 13, 2014
14 / 17
Text Books & References
Outline
1
Course Introduction
2
Syllabus
3
Policies
4
Text Books & References
Bahador Bakhshi (CE@AUT)
September 13, 2014
15 / 17
Text Books & References
Course Homepage: ceit.aut.ac.ir/∼bakhshis/ON
Books: fileserver\common\Bakhshi\Optimization in
Networking
Bahador Bakhshi (CE@AUT)
September 13, 2014
16 / 17
Text Books & References
Course Homepage: ceit.aut.ac.ir/∼bakhshis/ON
Books: fileserver\common\Bakhshi\Optimization in
Networking
J. Nocedal and S. J. Wright, ”Numerical Optimization”
S. Boyd, L. Vandenberghe, ”Convex Optimization”
R. J. Vanderbei, ”Linear Programming: Foundations and
Extensions”
F. S. Hillier and G. J. Lieberman, ”Introduction to
Operations Research”
M. and D. Medhi, ”Routing, Flow, and Capacity Design
in Communication and Computer Networks”
R. K. Sundaram, ”A First Course in Optimization
Theory”
Bahador Bakhshi (CE@AUT)
September 13, 2014
16 / 17
Text Books & References
Note: Extra classes
Option 1: Extend this class for 30 min
Option 2: An extra class every two weeks
Bahador Bakhshi (CE@AUT)
September 13, 2014
17 / 17
© Copyright 2024 ExpyDoc
