Hoppa till huvudinnehållet
Till KTH:s startsida Till KTH:s startsida

SF2812 Applied Linear Optimization 7,5 hp

Course memo Spring 2022-60154

Version 1 – 12/30/2021, 11:41:58 AM

Course offering

Spring 2022-1 (Start date 18/01/2022, English)

Language Of Instruction

English

Offered By

SCI/Mathematics

Course memo Spring 2022

Administrera Om kursen

The course gives a deepened and broadened theoretical and methodological knowledge in linear and integer programming. Some subjects dealt with in the course are: The simplex methods, interior methods, decomposition, column generation, stochastic programming, Lagrangian relaxation and subgradient methods in integer programming.

The course also gives training in modeling and solving practical problems, and to present the results in talking as well as writing.

Headings denoted with an asterisk ( * ) is retrieved from the course syllabus version Autumn 2020

Content and learning outcomes

Course contents

  • The simplex method and interior methods for linear programming.
  • Utilization of problem structure in linear programming, e.g., decomposition and column generation.
  • Stochastic programming: methods and utilization of problem structure.
  • Branch-and-bound methods for integer programming.
  • Lagrangian relaxation and subgradient methods for large-scale integer programming problems with special structure.

Intended learning outcomes

To pass the course, the student shall be able to:

  • Apply theory, concepts and methods from the parts of optimization that are given by the course contents to solve problems.
  • Model, formulate and analyze simplified practical problems as optimization problems and solve by making use of given software.
  • Collaborate with other students and demonstrate ability to present orally and in writing.

To receive the highest grade, the student should in addition be able to do the following:

  • Combine and explain the methods in the course, and
  • Apply and explain the theory and the concepts of the course in the practical problems that are included.

Learning activities

The main activities of the course are:

  • Lectures. Lecture notes will be made available before each lecture. The lecture notes contain "Preparatory questions". Study these preparatory questions before the lectures. 
  • Exercise sessions. The course contains 8 exercise session.
  • Project assignments. The course contains 2 project assignments.

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. 
  • Integer programming
    Formulations of integer programs. Branch-and-bound. Lagrangian relaxation and subgradient methods applied on integer programs with special structure.

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.) The same book is also used in SF2822.
  • Exercises in applied linear optimization, . Available via Canvas.
  • Lecture notes in applied linear optimization, Available via Canvas.
  • Theory questions in applied linear optimization, 2020/2021. 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 28 and February 10 respectively.

Additional notes that may be handed out during the course are also included.

Detailed plan

Schema VT-2022-211

Preliminary schedule

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

Type Day Date Time Room Subject
L1 Tue Jan 18 15-17 U21 Introduction. Linear programming models.
L2 Wed Jan 19 15-17 U21 Linear programming. Geometry.
L3 Thu Jan 20 8-10 W42 Lagrangian relaxation. Duality. LP optimality.
L4 Fri Jan 21 8-10 U21 Linear programming. The simplex method.
E1 Mon Jan 24 15-17 U21 Linear programming. The simplex method.
L5 Wed Jan 26 10-12 W42 More on the simplex method.
P1 Fri Jan 28 8-10 U21 Introduction to GAMS.
P2 Mon Jan 31 10-12 U31 GAMS excercise session.
E2 Tue Feb 1 15-17 U21 Linear programming. The simplex method.
L6 Thu Feb 3 8-10 U21 Stochastic programming.
E3 Fri  Feb 4 8-10 U21 Stochastic programming.
L7 Mon Feb 7 15-17 W42 Interior methods for linear programming.
E4 Wed Feb 9 13-15 U21 Interior methods for linear programming.
L8 Thu Feb 10 15-17 U21 Integer programming models.
P3 Mon Feb 14 15-17 U51 Presentation of project assignment 1.
L9 Tue Feb 15 13-15 U31 Branch-and-bound.
E5 Wed Feb 16 10-12 U21 Integer programming.
L10 Thu Feb 17 10-12 U21 Decomposition and column generation.
E6 Mon Feb 21 15-17 U21 Decomposition and column generation.
L11 Tue Feb 22 10-12 U31 Lagrangian relaxation. Duality.
E7 Wed Feb 23 10-12 W42 Lagrangian relaxation. Duality.
P4 Mon Feb 28 15-17 U21 Presentation of project assignment 2.
L12 Wed Mar 2 10-12 U51 Subgradient methods.
E8 Thu Mar 3 13-15 U21 Subgradient methods.
  Fri Mar 4 8-10 U21  

Mapping of exercises to lectures

The sections in the exercise booklet may roughly be mapped to the lectures as follows:

  1. The simplex method. After L4.
  2. Sensitivity analysis. After L4.
  3. Interior point methods. After L7.
  4. Decomposition and column generation. After L10.
  5. Linear programming - remaining. After L7.
  6. Stochastic programming. After L6.
  7. Formulation - integer programming. After L8.
  8. Lagrangian relaxation and duality. After L11.
  9. Subgradient methods. After L12.

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.

Preparations before course start

Literature

Main course literature:

In the course, we mainly use the book

Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer, SIAM, 2009.
(The book can also be ordered from several places. Please note that you can become a SIAM member for free and obtain a discount at the SIAM bookstore.)

The same book is also used in SF2822.

Examination and completion

Grading scale

A, B, C, D, E, FX, F

Examination

  • PRO1 - Project, 1.5 credits, Grading scale: A, B, C, D, E, FX, F
  • PRO2 - Project, 1.5 credits, Grading scale: A, B, C, D, E, FX, F
  • TEN1 - Examination, 4.5 credits, Grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

The section below is not retrieved from the course syllabus:

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 Friday March 11 2021, 8.00-13.00.

Grading criteria/assessment criteria

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.

Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

No information inserted

Course Coordinator

Teachers

Examiner

Other Contacts

Round Facts

Start date

18 Jan 2022

Course offering

  • Spring 2022-60154

Language Of Instruction

English

Offered By

SCI/Mathematics

Contacts

Course Coordinator

Teachers

Examiner

Other Contacts