EduXchange.EU

Applied Discrete Optimization

WI000819
Business and Economics

About this course

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

Learning outcomes

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.

Examination

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.

Course requirements

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.

Resources

  • 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.

Activities

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.

Additional information

  • Credits
    ECTS 6
  • Contact hours per week
    4
  • Instructors
    Anulark Naber, Jens Brunner, Markus Frey, Andreas Schulz
  • Mode of instruction
    Hybrid
If anything remains unclear, please check the FAQ of TUM (Germany).

Offering(s)

  • Start date

    23 April 2025

    • Ends
      25 July 2025
    • Term *
      Summer 2025
    • Instruction language
    • Register between
      29 Oct - 29 Nov 2024
    Enrolment open
    Apply now
These offerings are valid for students of Technion (Israel)