Valid from: Autumn 2014
Decided by: FN1/Anders Gustafsson
Date of establishment: 2013-08-26
Division: Electrical and Information Technology
Course type: Third-cycle course
Teaching language: English
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.
Knowledge and Understanding
For a passing grade the doctoral student must 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.
Competences and Skills
For a passing grade the doctoral student must 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.
Judgement and Approach
For a passing grade the doctoral student must 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.
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.
Item 2. Library of Congress catalog card number: 78-95301
Types of instruction: 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.
Examination formats: Written exam, written report, written assignments
Grading scale: Failed, pass
Examiner:
Assumed prior knowledge: The participants should be fluent in standard mathematics, including calculus, elements of analytical geometry, linear equations, and in computer programming.
Course coordinator: Michal Pioro, michal.pioro@eit.lth.se
Course coordinators: