Optimization Techniques

Learning Outcomes

The course pertains to the modeling and solving of operational research problems via linear programming, integer programming and related optimization models. In this context, the theoretical foundations of these optimization models are developed; solving algorithms are presented, for global optimization (e.g., the Simplex method, Branch-and-Bound), as much as the design and analysis of heuristic methods, inclusively of local search and approximation algorithms.

Upon successful completion of the course, the students will be in position:

• to develop the formal/abstract mathematical representation of an operational optimization problem, given its description in natural language along with the problem’s parameters and input data.
• to choose appropriate solving methods for a given mathematical model of an operational optimization problem.
• to program a mathematical optimization model in an appropriate programming language, while using relevant software for solving the model.
• to assess and evaluate the solution to a mathematical optimization model, along with the performance of the chosen solving method.
• to discriminate between computationally tractable and hard mathematical models for operational research problems.

Course Contents

• Modeling Problems through Linear Programming.
• Linear Programming Theory, Duality.
• The Simplex Algorithm.
• Integer Linear Programming, Branch and Bound Method.
• Transportation and Assignment Problems.
• Network Optimization (paths, trees, flows, matchings, cuts).
• Computationally Hard Optimization Problems.
• Introduction to Approximation Algorithms.
• Local Search Methods.

Recommended Readings

• F. S. Hillier, G. J. Lieberman. Introduction to Operations Research. McGraw-Hill Higher Education, 2004.
• J. Kleinberg, E. Tardos. Algorithm Design. Pearson, 2013.