KTH /
Engineering Science
/
Mathematics
/
Optimization and Systems Theory
SF2812 Applied Linear Optimization, 7.5hp, 2017/2018
Instructor and examiner
Anders Forsgren
(andersf@kth.se),
room 3533, Lindstedtsv. 25, tel 790 71 27.
Office hours: Monday 1112.
(Or by agreement.)
Exercise leader and project leader
David Ek
(daviek@kth.se),
room 3736,
Lindstedtsv. 25, tel. 790 62 94.
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, 2017/2018.
Available via Canvas.
 Lecture notes in applied linear optimization,
2017/2018.
May be downloaded from this web page, see the schedule below. Also
available
via Canvas.
 Supplementary course material in applied linear optimization,
2017/2018.
Available via Canvas.
 Theory questions in applied linear optimization,
2017/2018.
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, February 1 and February 15 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 Thursday February 15 and presence at the
following dicussion session.

Pass project assignment 2, with presence at the compulsory
presentation lecture on Wednesday February 28 and presence at the
following dicussion 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. PhD students register via email to
the instructor.
Project assignments
The project assignments are performed in groups,
where the instructor determines the division of 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 group
must hand in a wellwritten report which describes the exercise and
the 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.

When handing in the report, each student should append an individual
sheet with a brief selfassessment of his/her contribution to the project
work, quantitatively as well as qualitatively.

At the presentation lecture, all assignments will be presented and
discussed. Each student is expected to be able to present the
assignment of his/her 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 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, reachable from
the course home page. Each 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 AC). Normally, the same
grade is given to all members of a group.
Each group must solve their task independently. Discussion between the
groups concerrning interpretation of statements etc. are encouraged,
but each group must work independently without making use of solutions
provided by others. All 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 (2224), D (2530), C
(3136), B (3742) and A (4350).
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 Monday March 12 2018, 8.0013.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.
Type  Day  Date  Time  Room  Subject

L1.  Tue  Jan 16  1517  U21
 Introduction. Linear programming models.
(pdf)

L2.  Thu  Jan 18  810  U21
 Linear programming. Geometry.
(pdf)

L3.  Fri  Jan 19  1517  U21
 Lagrangian relaxation. Duality. LP optimality.
(pdf)

L4.  Tue  Jan 23  1517  U21
 Linear programming. The simplex method.
(pdf)

E1.  Thu  Jan 25  810  U21
 Linear programming. The simplex method.

L5.  Fri  Jan 26  1517  U21
 More on the simplex method.
(pdf)

E2.  Tue  Jan 30  1517  U21
 Linear programming. The simplex method.

P1.  Wed  Jan 31  1012  U21
 Introduction to GAMS.
(pdf)

P2.  Thu  Feb 1  810 
Gul
 GAMS excercise session.

L6.  Fri  Feb 2  1517  U21
 Stochastic programming.
(pdf)

E3.  Tue  Feb 6  1517  U21
 Stochastic programming.

L7.  Thu  Feb 8  810  U21
 Interior methods for linear programming.
(pdf)

E4.  Fre  Feb 9  1517  U21
 Interior methods for linear programming.

L8.  Tue  Feb 13  1517  U21
 Integer programming models.
(pdf)

L9.  Wed  Feb 14  1012  U21
 Branchandbound.
(pdf)

P3.  Thu  Feb 15  810  U21
 Presentation of project assignment 1.

E5.  Fri  Feb 16  1517  U21
 Integer programming.

L10.  Tue  Feb 20  1517  U21
 Decomposition and column generation.
(pdf)

E6.  Thu  Feb 22  810  U31
 Decomposition and column generation.

L11.  Fri  Feb 23  1517  U21
 Lagrangian relaxation. Duality.
(pdf)

E7.  Tue  Feb 27  1517  U31
 Lagrangian relaxation. Duality.

P4.  Wed  Feb 28  1012  U21
 Presentation of project assignment 2.

L12.  Thu  Mar 1  810  U31
 Subgradient methods.
(pdf)

E8.  Fri  Mar 2  1517  L52
 Subgradient methods.

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.
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, primaldual interior methods in particular.
(Chapters 47 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. Branchandbound. Lagrangian
relaxation and subgradient methods applied on integer programs with
special structure.
(Supplementary course material.)
Welcome to the course!
Course home page:
http://www.math.kth.se/optsyst/grundutbildning/kurser/SF2812/.
