SF2812 Applied Linear Optimization, 7.5hp, 2011/2012

Instructor and examiner

Exercise leader and project leader

Course material

• Linear and Nonlinear Optimization, second edition, by I. Griva, S. G. Nash och A. Sofer, SIAM, 2009.
  Information on how to order the book can be found here.
  
• Exercises in applied linear optimization, 2011/2012. For sale at the department's student expedition, Lindstedtsv. 25.
• Appended course material in applied linear optimization, 2011/2012. For sale at the department's student expedition, Lindstedtsv. 25.
• Lecture notes in applied linear optimization, 2011/2012. Can be downloaded from this web page, see the schedule below.
• GAMS, A user's guide. For sale at the department's student expedition, Lindstedtsv. 25. May alternatively be downloaded from the GAMS web site.
• GAMS. GAMS is installed in computer rooms for F and MMT. 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, September 12 and September 27 respectively.

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

Course goals

• 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

• Pass project assignment 1, with presence at the compulsory presentation lecture on Tuesday September 27, and presence at the following dicussion session.
• Pass project assignment 2, with presence at the compulsory presentation lecture on Tuesday October 11, and presence at the following dicussion session.
• Pass final exam.

Course registration

Project assignments

• At the beginning of the presentation lecture, each group must hand in a well-written report which describes the exercise and the group's suggestion for solving the exercise. 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 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. 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 these sessions are in the form of a 20 minutes question session, one group at a time. There will be times 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. 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 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 Thursday October 20 2011, 14.00-19.00 , in rooms V01 and V11.

Final grade

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

Mapping of exercises to lectures

• 1. The simplex method. After F4.
• 2. Sensitivity analysis. After F4.
• 3. Interior point methods. After F6.
• 4. Decomposition and column generation. After F10.
• 5. Linear programming - remaining. After F6.
• 6. Stochastic programming. After F7.
• 7. Formulation - integer programming. After F8.
• 8. Lagrangian relaxation and duality. After F11.
• 9. Subgradient methods. After F12.

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

Welcome to the course!