Study-Unit Description

Study-Unit Description


CODE SOR3350

 
TITLE Combinatorial Optimization

 
UM LEVEL 03 - Years 2, 3, 4 in Modular Undergraduate Course

 
MQF LEVEL 6

 
ECTS CREDITS 4

 
DEPARTMENT Statistics and Operations Research

 
DESCRIPTION - Discussion of Several Combinatorial Optimization Problems
- Unimodular and Totally Unimodular Matrices
- Integrality of Polyhedra
- Indicator Variables and Logical Constraints
- Disjunctive Constraints
- Set-Covering, Set-Packing and Set-Partitioning Problems
- Preprocessing
- Branch-and-Bound Method
- Cutting Plane Methods
- Branch-and-Cut
- Dantzig-Wolfe Decomposition and Column Generation
- Benders Decomposition
- Introduction to Dynamic Programming
- Computational Complexity Theory (Classes P and NP)
- Reductions among Combinatorial Optimization Problems.

Study-Unit Aims:

Combinatorial optimization deals with finding the best arrangement, grouping, ordering, or selection of a finite number of discrete objects. There are various applications of combinatorial optimization in Operations Research including routing vehicles to deliver goods to customers, scheduling tasks on machines, assigning personnel to work shifts, and identifying the placement of facilities such as fuel pumps and waste plants. This study-unit aims at providing students an appreciation of such real-world combinatorial optimization problems and how these can be formulated as mathematical models. It also aims at providing knowledge of the main exact solution approaches for tackling such problems.

Learning Outcomes:

1. Knowledge & Understanding:
By the end of the study-unit the student will be able to:

- demonstrate through mathematical programming the use of combinatorial optimization in several real-life settings;
- define integral polyhedra through selected fundamental theorems related to such feasible sets;
- formulate original examples of integral and non-integral polyhedra;
- describe verbally and apply the branch-and-bound and cutting plane methods to different combinatorial optimization problems;
- distinguish between the principles underpinning Dantzig-Wolfe and Benders decomposition for large-scale problems;
- show the appropriateness of dynamic programming on different problems;
- derive computational complexity theory results such as proofs of intractability for certain problems.

2. Skills
By the end of the study-unit the student will be able to:

- formulate mathematical models for a selection of classical combinatorial optimization problems;
- construct and solve search trees for combinatorial optimization problems via branch-and-bound;
- apply cutting plane algorithms to solve integer or mixed integer linear programs;
- decompose very large problems via Dantzig-Wolfe or Benders decomposition;
- identify when a combinatorial optimization problem is intractable;
- use software packages for optimization purposes;
- analyze and correctly interpret the results obtained.

Main Text/s and any supplementary readings:

Main Texts:

- Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., & Schrijver, A. (1998). Combinatorial Optimization, John Wiley & Sons.
- Korte, B., & Vygen, J. (2012). Combinatorial Optimization Theory and Algorithms, Fifth Edition, Springer Berlin.
- Papadimitriou, C.H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity, Dover Publications.
- Schrijver, A. (2003). Combinatorial Optimization, Polyhedra and Efficiency, Springer.
- Wolsey, L.A. (1998). Integer Programming, John Wiley and Sons.
- Wolsey, L.A., & Nemhauser, G.L. (1999). Integer and Combinatorial Optimization, John Wiley and Sons.

Supplementary Readings:

- Lee, J. (1998). A First Course in Combinatorial Optimization, Cambridge University Press.
- Schrijver, A. (1998). Theory of Linear & Integer Programming, John Wiley and Sons.
- Williams, H.P. (2010). Logic and Integer Programming, Springer.
- Williams, H.P. (2013). Model Building in Mathematical Programming, Fifth Edition, John Wiley and Sons.

 
ADDITIONAL NOTES Pre-Requisite Study-Units: SOR1310, SOR1320

 
STUDY-UNIT TYPE Lecture and Tutorial

 
METHOD OF ASSESSMENT
Assessment Component/s Assessment Due Sept. Asst Session Weighting
Project SEM2 No 30%
Computer-Assisted Examination (2 Hours) SEM2 Yes 70%

 
LECTURER/S Monique Sciortino

 

 
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints.
Units not attracting a sufficient number of registrations may be withdrawn without notice.
It should be noted that all the information in the description above applies to study-units available during the academic year 2024/5. It may be subject to change in subsequent years.

https://www.um.edu.mt/course/studyunit