Applied Discrete Optimization

Discrete optimization problems arise in many practical applications and functional areas. The module Applied Discrete Optimization focuses on the underlying polyhedral theory and both exact and heuristic solution methods to solve large - scale and complex mathematical models. Topics include

1. Review of linear programming
2. Revised simplex and column generation methods
3. Discrete optimization problems and model formulations
4. Computational complexity
5. Basic exact solution methods: a. Branch-and-Bound methods b. Cutting-Plane methods
6. Advanced exact solution methods: a. Strong Valid Inequalities b. Branch-and-Cut c. Dantzig-Wolfe Decomposition d. Branch-and-Price / Branch-Price-Cut e. Lagrangian Relaxation f. Bender’s Decomposition
7. Heuristic / Metaheuristic methods

At the end of the module, students shall understand the complexity of discrete optimization models, the polyhedral theory, and the theoretical concepts underlying the advanced methods in solving the discrete models. These methods include Branch-and-Cut, Branch-and-Price, Branch-Price-Cut, Benders' Decomposition, and Lagrangian relaxation. Students will be able to apply appropriately these solution approaches to solve their complex problems either by exact or heuristic methods.

Exercises (Any combination of homework assignments, semester project or report, and presentation) and Test (written)

The final grade is composed of individual or group exercises, as well as a written individual test at the end of the semester. The exercises will count for 40%-60% and the test for 60%-40% respectively, of the final grade.

In the exercises, the students show their theoretical understanding and, thus, ability to apply different methodologies, either exact or heuristic, to solve problems including the real-world applications in the field of operations research. In the test, the theoretical understanding of each student is queried.

This module is dedicated to advanced students who have background in Management Science or Operations Research, specifically in linear programming and duality theory. To work on the assignments, students should have knowledge in using any optimization packages such as OPL/CPLEX, GUROBI, LINGO, or Excel Solver. Knowledge in programming languages is not expected but can be useful for the assignments.

• 1. Nemhauser G.L. and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley. 1988. 2. Wolsey, L.A. Integer Programming. Wiley. 1998. 3. Wintston, Operations Research: Applications and Algorithms. 1993. 4. Any reference or textbook in management science or operations research.

The module consists of a series of lectures that describe the fundamental theories behind the solution methods and illustrate their examples and applications. A few selected technical papers addressing specific problems and solutions to the described problems will be discussed. Assignments are of student groupwork to practice the solution methods learned in class and to review the real-world applications.