Kungl Tekniska högskolan / Optimization and Systems Theory /[an error occurred while processing this directive]This is a printer-friendly version of http://www.math.kth.se/optsyst/forskning/forskarutbildning/SF3850/info.html?utskriftSF3850 Numerical linear programming, 7.5crGeneral informationThis graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.Summary of contentsThe course deals with theory and algorithms for linear programming problems (LP problems).From the 1940s untils about thirty years ago the simplex method, developed by Dantzig, was the only practically used method for solving LP problems. Khachian had in the late 1970s presented the polynomial ellipsoid method, but it had not been successful in practice. When Karmarkar presented his interior method in 1984, all this changed. This method was polynomial and also claimed to be superior to the simplex method in practice. Karmarkar's method lead to an "explosion" within the area of linear programming. Gill et. al. soon showed that Karmarkar's method was equivalent to a logarithmic barrier method, and the development of new interior methods was rapid. This "competition" between the simplex method and interior methods has lead to significant improvement in both types of method over the last decade. The purpose of this course is to reflect this development. Some more advanced aspects of the simplex method are included, e.g., steepest edge, partial pricing, and of the interior-point methods e.g., primal-dual methods, affine-scaling methods, predictor-corrector methods. In particular, we try to understand how the different methods work. PrerequisitesSuitable prerequisites are the courses SF2812 Applied linear optimization and DN2251 Applied numerical methods III, or similar knowledge.LiteratureThe literature is a textbook, a set of articles and extract from textbooks. Below is a listing of these articles and books, where it is also indicated what parts are of significant importance.
ScheduleTwelve lectures will be given in the autumn of 2016.First meeting Tuesday September 20, 2016, 13.15-15.00, in Room 3721, Lindstedtsvägen 25. ExaminationThe examination is by five sets of homework assignments and an oral final exam.ExaminerAnders Forsgren, room 3533, Lindstedtsvägen 25, tel. 790 71 27. E-mail:Optimization and Systems Theory, KTH Anders Forsgren, andersf@kth.se |