Integer Programming and Combinatorial Optimization

Integer programming and combinatorial optimization course is a course of the 6th semester of the department of Mechanical Engineering at the University of Thessaly. During the semester the students are taught the basic knowledge of linear integer and mixed integer programming. Students are taught heuristic and exact solution approaches and algorithms through small, medium and large scale examples. Finally, through detailed toy examples from the bibliography as well as real case examples from the industry the teaching focuses on modeling technics. Students get experience on modeling approaches in order to get the ability to develop robust and compact mathematical models for real case studies.

Objectives

The course requires knowledge of basic concepts of linear programming. The aim is to introduce the students to the fundamental principles of integer programming and combinatorial optimization and their applications. Additionally, emphasis is given on the procedure of designing and analyzing optimization algorithms. After the end of the class, the students should be able to formulate problems, develop optimization techniques, design solution procedures and use advanced tools for problem solution.

Prerequisites

This class requires basic knowledge on operational research. More specifically, the students need basic knowledge on linear programming and algebra.

Syllabus

Formulation and applications of integer and mixed integer programming problems. Clever uses of binary variables to formulate models. Branch and bound method. Cutting plane method. Design and analysis of algorithms, combinatorial optimization. Complexity of algorithms. Applications on networks and graphs. Solution of problems using local optimization techniques, dynamic programming, myopic algorithms, approximate and heuristic methods.