Detaljer för kursplan för kurs EIT090F giltig från och med Autumn 2014 Utskriftsvänlig visning Kurskod:EIT090F Gäller från och med:Autumn 2014 Kursplanen är fastställd Allmänt Undervisningsspråk:English Ges:Varannan vårtermin Kurshemsida: Syfte 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. Innehåll 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. Kunskap och förståelse För godkänd kurs skall doktoranden 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. Färdighet och förmåga För godkänd kurs skall doktoranden 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. Värderingsförmåga och förhållningssätt För godkänd kurs skall doktoranden 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. Undervisningsformer Föreläsningar övningar Projekt Litteraturkurs som självstudier Kommentarer: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. Examinationsformer Skriftlig tentamen Skriftlig rapport Inlämningsuppgifter Betygsskala:Underkänd, godkänd Förkunskapskrav Förutsatta förkunskaper The participants should be fluent in standard mathematics, including calculus, elements of analytical geometry, linear equations, and in computer programming. Urvalskriterier Litteratur Litteratur: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. Kommentarer:Item 2. Library of Congress catalog card number: 78-95301 Övrig information Course coordinator: Michal Pioro, michal.pioro@eit.lth.se Kurskod Kurskod:EIT090F Administrativ information Datum för fastställande: -08-26 Beslutad av:FN1/Anders Gustafsson Alla publicerade kurstillfällen för kursplanen Inga matchande kurstillfällen hittades. 0 kurstillfällen. Utskriftsvänlig visning