ITA | ENG
B029651 - COMBINATORIAL OPTIMIZATION
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Further information
Type of Assessment
Course program
Academic Year 2019-20
Coorte 2019 - Second Cycle Degree in TELECOMMUNICATION ENGINEERING
Course year
First year - Second Semester
Belonging Department
Information Engineering (DINFO)
Course Type
Single education field course
Scientific Area
MAT/09 - OPERATIONS RESEARCH
Credits
6
Teaching Hours
48
Teaching Term
02/03/2020 ⇒ 12/06/2020
Attendance required
No
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Mutuality
Course teached as:
B029651 - COMBINATORIAL OPTIMIZATION
Second Cycle Degree in COMPUTER ENGINEERING
B029651 - COMBINATORIAL OPTIMIZATION
Second Cycle Degree in COMPUTER ENGINEERING
Teaching Language
Italian
Course Content
1. Modeling with binary and integer variables.
2. Algorithms to solve Combinatorial Optimization problems.
3. Data-uncertainty and robustness.
2. Algorithms to solve Combinatorial Optimization problems.
3. Data-uncertainty and robustness.
Suggested readings (Search our library's catalogue)
Integer Programming (L. Wolsey)
Network Flows: Theory, Algorithms, and Applications
(R.K. Ahuja, T.L. Magnanti,
J.B. Orlin)
Network Flows: Theory, Algorithms, and Applications
(R.K. Ahuja, T.L. Magnanti,
J.B. Orlin)
Learning Objectives
1) Ability to formulate combinatorial and network flow optimization problems.
2) Knowledge of algorithms for combinatorial optimization.
3) Ability to use and adapt standard combinatorial optimization algorithms to specific application contexts.
2) Knowledge of algorithms for combinatorial optimization.
3) Ability to use and adapt standard combinatorial optimization algorithms to specific application contexts.
Prerequisites
Basic notions of Operations Research and Linear Algebra.
Teaching Methods
Lessons
Further information
E-learning with Moodle
Type of Assessment
Oral examination.
The oral examination focuses on questions relating to models and algorithms for solving a particular combinatorial optimization problem addressed during the course.
In order to pass the exam, students must show that they have a basic knowledge of the subjects, be able to recognize the structure of a problem and discuss mathematical models and algorithms for its resolution, dealt with in the course .
The oral examination focuses on questions relating to models and algorithms for solving a particular combinatorial optimization problem addressed during the course.
In order to pass the exam, students must show that they have a basic knowledge of the subjects, be able to recognize the structure of a problem and discuss mathematical models and algorithms for its resolution, dealt with in the course .
Course program
Integer Programming and Combinatorial Optimization
Part I. Modeling with binary and integer variables
• Network flow problems: a quick review of well-solved problems
• Assignment and matching problems
• Covering, packing, partitioning problems
• Spanning tree problem
• Vehicle Routing problem
•Multicommodity flows
• Network design
Part II. Algorithms to solve Combinatorial Optimization problems
• Linear and Lagrangean relaxations
• Polyhedral theory: generation of valid inequalities, strong valid inequalities and facets
• The Cutting Plane approach (row generation)
• The column generation approach: master problem and pricing subproblems
• Branch & Cut
• Decomposition algorithms
Part III. Data-uncertainty and robustness
• Re-establishment tools in the design of robust networks.
Alternative frameworks: (i) protection and (ii) restoration.
What is necessary to restore: link vs path, link restoration vs path restoration
Resource management: dedicated vs shared.
• Robust optimization.
Part I. Modeling with binary and integer variables
• Network flow problems: a quick review of well-solved problems
• Assignment and matching problems
• Covering, packing, partitioning problems
• Spanning tree problem
• Vehicle Routing problem
•Multicommodity flows
• Network design
Part II. Algorithms to solve Combinatorial Optimization problems
• Linear and Lagrangean relaxations
• Polyhedral theory: generation of valid inequalities, strong valid inequalities and facets
• The Cutting Plane approach (row generation)
• The column generation approach: master problem and pricing subproblems
• Branch & Cut
• Decomposition algorithms
Part III. Data-uncertainty and robustness
• Re-establishment tools in the design of robust networks.
Alternative frameworks: (i) protection and (ii) restoration.
What is necessary to restore: link vs path, link restoration vs path restoration
Resource management: dedicated vs shared.
• Robust optimization.