401-3901-00L  Linear & Combinatorial Optimization

SemesterAutumn Semester 2021
LecturersR. Zenklusen
Periodicityyearly recurring course
Language of instructionEnglish


AbstractMathematical treatment of optimization techniques for linear and combinatorial optimization problems.
ObjectiveThe goal of this course is to get a thorough understanding of various classical mathematical optimization techniques for linear and combinatorial optimization problems, with an emphasis on polyhedral approaches. In particular, we want students to develop a good understanding of some important problem classes in the field, of structural mathematical results linked to these problems, and of solution approaches based on such structural insights.
ContentKey topics include:
- Linear programming and polyhedra;
- Flows and cuts;
- Combinatorial optimization problems and polyhedral techniques;
- Equivalence between optimization and separation.
Literature- Bernhard Korte, Jens Vygen: Combinatorial Optimization. 6th edition, Springer, 2018.
- Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. This work has 3 volumes.
- Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
- Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley, 1986.
Prerequisites / NoticeSolid background in linear algebra.

Former course title: Mathematical Optimization.
CompetenciesCompetencies
Subject-specific CompetenciesConcepts and Theoriesassessed
Techniques and Technologiesfostered
Method-specific CompetenciesAnalytical Competenciesassessed
Decision-makingassessed
Media and Digital Technologiesfostered
Problem-solvingassessed
Project Managementfostered
Social CompetenciesCommunicationassessed
Cooperation and Teamworkfostered
Customer Orientationfostered
Leadership and Responsibilityfostered
Self-presentation and Social Influence fostered
Sensitivity to Diversityfostered
Negotiationfostered
Personal CompetenciesAdaptability and Flexibilityfostered
Creative Thinkingassessed
Critical Thinkingfostered
Integrity and Work Ethicsfostered
Self-awareness and Self-reflection fostered
Self-direction and Self-management fostered