Course PM

SF2812 Applied Linear Optimization, 7.5hp, 20201/20212 Instructor and examiner Gianpiero Canessa (canessa@kth.se), room 3733, Lindstedtsv. 25. Office hours: Monday 11-12. (Or bBy agreement.)

Exercise leader and project leader David Ek (daviek@kth.se), room 3734, Lindstedtsv. 25. Office hours: By agreement.

Course material
* Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer, SIAM, 2009. (The book can be ordered from several places. Please note that you can become a SIAM member for free and obtain a discount at the SIAM bookstore.)
* Exercises in applied linear optimization, 2019/2020. Available via Canvas.
* Lecture notes in applied linear optimization, 2019/2020. Available via Canvas.
* Supplementary course material in applied linear optimization, 2019/2020. Available via Canvas.
* Theory questions in applied linear optimization, 2019/2020. Available via Canvas.
* GAMS, A user's guide. Available at the GAMS web site.
* GAMS. GAMS is installed in the KTH linux computer rooms. It may also be downloaded from the GAMS web site for use on a personal computer.
* Two project assignments that are handed out during the course, January 30 and February 13 respectively.
Additional notes that may be handed out during the course are also included.

Course goals After completed course, the student should be able to:

* explain fundamental concepts of linear programming and integer linear programming;
* explain how fundamental methods for linear programming and integer linear programming work;
* illustrate how these methods work by solving small problems by hand calculations;
* starting from a suitably modified real problem, formulate a linear program or an integer linear program; make a model in a modeling language and solve the problem;
* analyze the solutions of the optimization problem solved, and present the analysis in writing as well as orally;
* interact with other students when modeling and analyzing the optimization problems.
Examination The examination is in two parts, projects and final exam. To pass the course, the following requirements must be fulfilled:

* Pass project assignment 1, with presence at the compulsory presentation lecture on WednesMonday February 125 and presence at the following discussion session.
* Pass project assignment 2, with presence at the compulsory presentation lecture on Wednesday February 26Monday March 1 and presence at the following discussion session.
* Pass final exam.
Course registration Due to the project based nature of this course, students must register no later than January 31. Registration is made by the students online following KTH standard procedures.

Project assignments The project assignments are performed in groups, where the instructor determines the division of project groups. This division is changed between the two assignments. The assignments are carried out by the modeling language GAMS. The project assignments must be carried out during the duration of the course and completed by the above mentioned presentation lectures. It is the responsibility of each student to allocate time so that the project group can meet and function. Presence at the presentation lectures is compulsory. For passing the projects, the following requirements must be fulfilled:

* No later than the night before the presentation lecture, each project group must hand in a well-written report which describes the exercise and the project group's suggestion for solving the exercise through Canvas as a pdf file. Suitable word processor should be used. The report should be on a level suitable for another participant in the course who is not familiar with the group's specific problem.
* At the beginning of the presentation lecture, each student should hand in an individual sheet with a brief self-assessment of his/her contribution to the project work, quantitatively as well as qualitatively.
* At the presentation lecture, all assignments will be presented and discussed. The presentations and discussions will be made in small presentation groups, first in presentation groups where each student has worked on the same project assignment, and then in presentation groups where the students have worked on different project assignments. Each student is expected to be able to present the assignment of his/her project group, the modeling and the solution. In particular, each student is expected to take part in the discussion. The presentation and discussion should be on a level such that students having had the same assignment can discuss, and students not having had the same assignment can understand the issues that have arisen and how they have been solved. Each student should bring a copy of the project group's report to the presentation lecture, either in paper or electronically.
* Each project group should make an appointment for a discussion session with the course leaders. There is no presentation at this session, but the course leaders will ask questions and give feedback. There will be time slots available the days after the presentation session. One week prior to the presentation lecture, a list of available times for discussion sessions will be made available at Doodle, announced via Canvas. Each project group should sign up for a discussion session prior to the presentation lecture.
Each project assignment is awarded a grade which is either fail or pass with grading E, D, C, B and A. Here, the mathematical treatment of the problem as well as the report and the oral presentation or discussion is taken into account. The exercises are divided into basic exercises and advanced exercises. Sufficient treatment of the basic exercises gives a passing grade. Inclusion of the advanced exercises is necessary for the higher grades (typically A-C). Normally, the same grade is given to all members of a project group. A student who has not worked on the advanced exercises says so in the self assessment form.

Each project group must solve their task independently. Discussion between the project groups concerning interpretation of statements etc. are encouraged, but each project group must work independently without making use of solutions provided by others. All project groups will not be assigned the same exercises.

Final exam The final exam consists of five exercises and gives a maximum of 50 points. At the exam, the grades F, Fx, E, D, C, B and A are awarded. For a passing grade, normally at least 22 points are required. In addition to writing material, no other material is allowed at the exam. Normally, the grade limits are given by E (22-24), D (25-30), C (31-36), B (37-42) and A (43-50).

The grade Fx is normally given for 20 or 21 points on the final exam. An Fx grade may be converted to an E grade by a successful completion of two supplementary exercises, that the student must complete independently. One exercise among the theory exercises handed out during the course, and one exercise which is similar to one exercise of the exam. These exercises are selected by the instructor, individually for each student. Solutions have to be handed in to the instructor and also explained orally within three weeks of the date of notification of grades.

The final exam is given MonThursday March 911 20201, 8.00-13.00.

Final grade By identitying A=7, B=6, C=5, D=4, E=3, the final grade is given as

round( (grade on proj 1) + (grade on proj 2) + 2 * (grade on final exam) ) / 4),

where the rounding is made to nearest larger integer in case of a tie.

Preliminary schedule "L" means lecture, "E" means exercise session, "P" means project session.

TypeDayDateTimeRoomSubject L1 WedMon Jan 158 15-17 Q2Zoom Introduction. Linear programming models. L2 ThuWed Jan 16 8-10 Q220 10-12 Zoom Linear programming. Geometry. L3 FriThu Jan 217 8-10 Q2Zoom Lagrangian relaxation. Duality. LP optimality. L4 TueFri Jan 21 15-17 Q22 8-10 Zoom Linear programming. The simplex method. E1 ThuMon Jan 23 8-10 Q25 15-17 Zoom Linear programming. The simplex method. L5 FriWed Jan 247 150-17 Q22 Zoom More on the simplex method. P1 TueFri Jan 28 15-17 Q29 8-10 Zoom Introduction to GAMS. P2 Wed Jan 29 10-12 Q2Mon Feb 1 15-17 Zoom GAMS excercise session. E2 Thu Jan 30 8-10 Q2Wed Feb 3 15-17 Zoom Linear programming. The simplex method. L6 Fri Jan 31 15-17 Q2Thu Feb 4 10-12 Zoom Stochastic programming. E3 TueFri Feb 4 15-17 Q25 8-10 Zoom Stochastic programming. L7 ThuMon Feb 6 8-10 Q28 15-17 Zoom Interior methods for linear programming. E4 FriWed Feb 710 150-17 Q22 Zoom Interior methods for linear programming. L8 TueFri Feb 11 15-17 Q22 8-10 Zoom Integer programming models. P3 WedMon Feb 125 105-12 Q27 Zoom Presentation of project assignment 1. L9 ThuWed Feb 13 8-10 Q27 10-12 Zoom Branch-and-bound. E5 FriThu Feb 148 150-17 Q22 Zoom Integer programming. L10 TueFri Feb 18 15-17 Q29 8-10 Zoom Decomposition and column generation. E6 ThuMon Feb 20 8-10 Q22 15-17 Zoom Decomposition and column generation. L11 FriWed Feb 214 153-17 Q25 Zoom Lagrangian relaxation. Duality. E7 Thue Feb 25 15-17 D38-19 Zoom Lagrangian relaxation. Duality. P4 Wed Feb 26Mon Mar 1 105-12 D37 Zoom Presentation of project assignment 2. L12 Thu Feb 27Wed Mar 3 8-10 Q2Zoom Subgradient methods. E8 Fri Feb 28 15-17 Q2Thu Mar 4 8-10 Zoom Subgradient methods. Mapping of exercises to lectures The sections in the exercise booklet may roughly be mapped to the lectures as follows:

* The simplex method. After L4.
* Sensitivity analysis. After L4.
* Interior point methods. After L7.
* Decomposition and column generation. After L10.
* Linear programming - remaining. After L7.
* Stochastic programming. After L6.
* Formulation - integer programming. After L8.
* Lagrangian relaxation and duality. After L11.
* Subgradient methods. After L12.
Overview of course contents
* Linear programming Fundamental LP theory with corresponding geometric interpretations. The simplex method. Column generation. Decomposition. Duality. Complementarity. Sensitivity. Formulations of LPs. Interior methods for linear programming, primal-dual interior methods in particular. (Chapters 4-7 in Griva, Nash and Sofer, except 5.2.3, 5.2.4, 5.5.1, 6.5, 7.5, 7.6. Chapter 9.3 in Griva, Nash and Sofer. Chapter 10 in Griva, Nash and Sofer, except 10.3, 10.5.)
* Stochastic programming Fundamental theory. (Supplementary course material.)
* Integer programming Formulations of integer programs. Branch-and-bound. Lagrangian relaxation and subgradient methods applied on integer programs with special structure. (Supplementary course material.)
Support for students with disabilities Students with disabilities may have the right to certain compensatory support for example during examination. KTH has coordinators for students with disabilities, Funka, who deals with issues relating to functional disabilities. You should turn to Funka at funka@kth.se for information about support.

Welcome to the course! Instructions for GAMS

* GAMS at the KTH linux computers.
* Type "module add gams" or add it to a suitable login file.
* Use an editor, for example emacs, to create/modify model files (".gms") and reading output files (".lst").
* Put the model files in your home catalog. Run GAMS from that catalog, e.g. "gams trans1".
* Please note that there is a whole library of example files at GAMS subdirectory "modlib".

* GAMS on your own computer.
* The demo version of GAMS (which we use) can be downloaded from the GAMS website.

* GAMS resources
* GAMS documentation
* GAMS user's guide