This unit aims at discrete optimization and its application for modelling and decision aid of real-life problems frequently encountered in practice. It consists of three parts: integer linear programming, combinatorial optimization techniques, and dynamic and stochastic decision making.
The first part addresses the modelling by mathematical programming, in particular by integer linear programming (IP), and relevant solution techniques.
The third part addresses the models and methods for stochastic and dynamic decision making, i.e. for determination of optimal policies for control of a dynamic discrete event systems subject to random perturbations.
The more detailed content of each part is described below.
| On completion of the unit, the student will be capable of: | Classification level | Priority |
|---|---|---|
| Modeling a real-life problem by mathematical programming | 7. Create | Essential |
| Develop efficient optimization methods | 7. Create | Important |
| Modeling a real-life dynamic decision making problems by Markov decision process | 7. Create | Essential |
| Develop efficient dynamic decision making policies | 7. Create | Important |
| Analyzing the properties of optimal solutions/policies | 4. Analyse | Useful |
| Percentage ratio of individual assessment | Percentage ratio of group assessment | ||||
|---|---|---|---|---|---|
| Written exam: | 1 | % | Project submission: | 1 | % |
| Individual oral exam: | % | Group presentation: | % | ||
| Individual presentation: | % | Group practical exercise: | 1 | % | |
| Individual practical exercise: | % | Group report: | % | ||
| Individual report: | % | ||||
| Other(s): % | |||||
| Type of teaching activity | Content, sequencing and organisation |
|---|---|
| Part I Integer Linear Programming | - Motivation and interests of mathematical modelling, - Usual IP models, - Generic solution methods : tree search and cutting planes, - IP equivalent to their linear programming relaxation (unimodularity and total unimodularity), - Solution approaches : Lagrangian relaxation and column generation. |
| Part II Discrete optimization methods | - Branch-and-Bound : branching/evaluation/exploration strategies, - Constraint programming, - Greedy heurstics, - Local search methods, - Global search methods (meta-heurstics : tabu search, simulated annealing, genetic algorithms. |
| Part III Stochastic and dynamic decision making | - Dynamic programming, - Markov decision process (MDP), - Finite horizon MDP, - Discounted cost MDP, - Average cost MDP, - Continuous time MDP, - Properties of value functions and optimal control policies. |