• 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.

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.

The main learning activities are:

• Lectures
• Exercise sessions
• Two project assignments
• Office hours

Instructor and examiner

Jan Kronqvist (jankr@kth.se), Lindstedtsv. 25.
Office hours: To be decided

Exercise and project leaders

Pim Heeman, pimh@kth.se,  Lindstedtsv. 25.

Office hours: To be decided

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,  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

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

Preliminary schedule

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

To be announced at the beginning of the course. Preliminary literature:

Linear and Nonlinear Programming by S.G.Nash och A.Sofer, McGraw-Hill, and some material from the department.

Students at KTH with a permanent disability can get support during studies from Funka:

Funka - compensatory support for students with disabilities

• PRO2 - Project, 1.5 credits, grading scale: A, B, C, D, E, FX, F
• PRO1 - 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.

If the course is discontinued, students may request to be examined during the following two academic years.

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 Tuesday February 10 and presence at the following discussion session.
• Pass project assignment 2, with presence at the compulsory presentation lecture on Monday February 26 and presence at the following discussion session.
• Pass final exam.
•  

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.

Projects: 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 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.

However, a final grade of C or higher requires at least a grade of D in the exam.

• 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.