English

Every other spring semester

The course is aiming at making the participants familiar with basic knowledge of (mixed) integer programming (MIP) – the fundamental optimization approach to real-life engineering problems. The main methods of MIP will be illustrated with a set of representative communication network design problems, including multi-commodity flow network models. Besides, the students will get familiar with GUROBI – an efficient optimization package for solving MIP problems. The students not working in communications will have an opportunity to develop MIP models related to their own fields of interest.

1. Introduction. An illustrative example: multi-commodity flow network design problem. Simple and difficult variants of the problem.
2. Linear programming (LP). Basic notions and properties of LP problems. Basic features of the simplex method.
3. Mixed-integer programming (MIP) and its relation to LP. Branch-and-bound (B&B) algorithm for problems involving binary variables. Applications to single-path allocation and network topology design. Extension to a general MIP formulation. Effectiveness of B&B.
4. Modeling non-linearity. Convex and concave objective functions and the crucial differences between the two. Step-wise cost functions.
5. General form of an optimization problem. Relaxation, linear relaxation, Elements of the dual theory. Duality in convex programming. Duality gap. Duality in LP.
6. Duality in MIP and Lagrangean relaxation (LR). Dual separation and column generation (an application: flow allocation problem). Benders’ decomposition.
7. Cutting plane method. Valid inequalities and branch-and-cut (B&C) approach. Branch-and-price (B&P) approach.
8. Heuristics for combinatorial optimization. Local search. Stochastic heuristics: simulated annealing (application to travelling salesman problem) and evolutionary algorithm (application to modular flow allocation).
9. The notion of NP-completeness. Separation theorem.
10. Application: design of wireless networks.

understand the modeling and solution approaches to optimization problems emerging in engineering applications. The PhD student should demonstrate understanding of the process of formulating models based on linear and integer programming. Furthermore, the student should demonstrate understanding of the Simplex method and the branch-and-bound algorithm, together with their extensions such as column generation and the cutting plane method. Finally, the student should understand the limitations in efficient computational treatment of the studied problems.

be able to independently construct models for optimization problems and to apply the GUROBI optimization package (or alike) for resolving them with full understanding of the solution process and output data. Furthermore, the student should be able to develop examples elaborated on his own in accordance with specific educational outcomes to undergraduate students.

be able to critically evaluate the correctness of obtained results, especially with respect to simplifying assumptions needed to create a tractable model. The student should be well versed in the limitations of existing theoretical approaches in terms of computational efficiency, and demonstrate clear judgement of the validity and accuracy of the formulated optimization models.

Lectures

Exercises

Project

Self-study literature review

The role of self-study will be two-fold. First, the students will extend the study of the theory behind MIP and solve appropriate exercises illustrating the theory. Second, the students will prepare the main individual project assignment to be solved using GUROBI, and write a report.

Written exam

Written report

Written assignments

Failed, pass

The participants should be fluent in standard mathematics, including calculus, elements of analytical geometry, linear equations, and in computer programming.

Wolsey, L.A.: Integer Programming. J. Wiley, 1998. ISBN 0471283665.
Lasdon, L.: Optimization Theory for Large Systems. MacMillan, 1972.
Pioro, M.: Network Optimization Techniques, Chapter 18 in Serpedin, E., Chen, T. and Rajan, D. (eds.), Signal Processing, Communications, and Networking. CRC Press, 2012. ISBN 9781439855133.

Item 2. Library of Congress catalog card number: 78-95301

Course coordinator: Michal Pioro, michal.pioro@eit.lth.se

EIT090F

 -08-26

FN1/Anders Gustafsson