TMA521/MMA510 Optimization, project course, 7.5 hec, lp1 2011

Links to more courses in Optimization at Chalmers and University of Gothenburg.

• Examiner and lecturer: Ann-Brith Strömberg, anstr ( at ) chalmers.se, tel.: 772 5378, office: MV L2087

• The course starts on Tuesday 30 August 2011 at 13:15 in MV:F32. Welcome!
• Link to the TimeEdit schedule


• Course plan. Note that some of the lectures booked in the TimeEdit schedule are currently NOT scheduled in the course plan.
  Updated course plan 110927.


• Lectures are given: Tuesdays at 13:15-15:00 in MV:F32; Wednesdays and Fridays at 10:00-11:45 in MV:F23

• Course literature:
  • Optimization Theory for Large Systems by Leon S. Lasdon, Dover Publications 2002, ISBN: 9780486419992. Legal copies of the book by Lasdon are available at Cremona.
    
  • Material on Lagrangean duality is also found in the book: An Introduction to Continuous Optimization, by N. Andréasson, A. Evgrafov, and M. Patriksson, Studentlitteratur, available at Cremona.
  • Articles.

• Links to project files, articles, lecture notes and slides will be added as the course proceeds

• There will be a series of lectures on the following topics:

  • Simple/difficult problems

    What distinguishes a simple optimization problem, or a difficult problem? We will learn about some simple problems, such as linear programming and classes of network flow problems. We also study the related topics of matroid problems (and intersections of matroids) and greedy algorithms.
    Literature:
    • Excerpt from Wolsey;
    • Excerpt from Lawler;
    • Chapter 2.1-2.2 from the book Knapsack problems - Algorithms and computer implementations by Martello and Toth.
    For more difficult problems, we review classic relaxation methods. We investigate how to prove that a problem is difficult by relating it to a known difficult one by means of "polynomial transformations". We take a closer look at the discrete network design problem, and discuss its properties.
    Literature:
    • Notes.
    For a basic problem in the field of facility location, we take a closer look at the workings of a Lagrangian relaxation method in the literature.
    Literature:
    • Barcelo et al.

    Downloads for Lecture 1

    Downloads for Lecture 2

    Questions on the network design problem

  • Lagrangian relaxation

    We review Lagrangian duality for problems with a zero duality gap.
    Literature:
    • Lasdon Ch. 8.1-4.
    • Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.1-3.
    Downloads for Lecture 3

    We present methodologies for solving Lagrangian dual problems, in particular the classes of subgradient optimization and bundle algorithms.
    Literature:

    • Lasdon Ch. 8.5-7(8);
    • Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.4.
    Downloads for Lecture 4

    For applications to integer programming, we specialize Lagrangian duality. In particular, we discuss the strength of different relaxations relate Lagrangian relaxation to continuous relaxations and the convexification of the original problem.
    Literature:

    • Notes;
    • Andréasson, Evgrafov, and Patriksson Ch. 6.7.
    We discuss the topic of primal recovery, that is, how to obtain an optimal solution to the primal problem. We discuss the use of Lagrangian heuristics as well as the use of ergodic sequences and master problems, thereby touching already now the subject of price decomposition, Dantzig-Wolfe decomposition and column generation.
    Literature:
    • Notes;
    • Larsson, Patriksson, and Strömberg (1999) (reachable from Chalmers domain); or Larsson, Patriksson, and Strömberg (1999) (local archive)
    • Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.5.
    Downloads for Lecture 5 (Updated version 110907)

  • Optimality conditions with applications

    We derive a set of global optimality conditions that extend those from the convex case (Lagrangian optimality; primal feasibility; complementarity) to any problem. The conditions involve perturbations in the classic conditions. They are then used to derive Lagrangian heuristics for the set covering problem as well as core problems and column generation algorithms for classes of integer and combinatorial optimization problems.
    Literature:
    • Notes;
    • Larsson and Patriksson (2006) (reachable from Chalmers domain).
    Downloads for Lecture 7

  • Column generation

    Dantzig-Wolfe decomposition, or price decomposition in linear programming, is investigated and applied. Its extension to integer programming is usually called column generation; we discuss its application to the classic cutting stock problem, and its combination with branch & bound known as branch & price.
    Literature:
    • Notes;
    • Lasdon Ch. 3 & 4.1;
    • Barnhart et al (1998) (reachable from Chalmers domain).
    Downloads for Lecture 8
    Downloads for Lecture 9

  • Presentation of the scheduling problem by Karin Thörnblad (1 lecture)

    Downloads for Lecture 10

  • Computational complexity with applications by Adam Wojciechowski (1 lecture)

    Downloads for Lecture 12

  • Students' presentations of Project 1 (1 lecture)

  • Benders decomposition

    The dual correspondance to Dantzig-Wolfe decomposition is a cutting plane method. While Dantzig-Wolfe decomposition does not extend to integer programming, the cutting plane method does, when it is referred to as Benders decomposition. We derive it and discuss its applications.
    Literature:
    • Notes;
    • Lasdon Ch. 7.3.
    Downloads for Lecture 14

• Examination (updated 29 August 2008):

  1. To pass the course you must take active part in the lectures, and in the two course projects. The projects are to be presented in the form of written reports as well as orally during seminars. Each group must also act as opponents/discussants on another group's projects, and each student must take active part in all of these activities.

  2. In order to reach a better mark than "pass" you can take an oral exam, based on the lecture material of the course and the projects. A majority of the possible topics that may be discussed during such an exam are gathered in the study material that is found here. In addition, you should be ready to discuss both the course's projects.

     The exam will be arranged thus: Apart from questions on the projects, and any side questions that may be relevant, the main part of the exam will consist of questions from the above study material. A selection will be made at random among them, making sure that the three (3) questions selected will cover the course material well enough and also include both grade 4 and 5 questions. (A "question" refers to a chapter in the study material.)

• Projects

  All handing in of programs and reports shall be made to anstr.chalmers@analys.urkund.se

  Project groups consist of two or one person(s)

  • Project 1 (updated 30 August 2011)

    You will investigate the use of Lagrangian relaxation on a VLSI design problem. You have access to codes in Matlab and c to perform data collection as well as to solve the Lagrangian subproblems and illustrate the solutions, but you must write the Lagrangian optimization code in Matlab yourself.

    Project description files
    The project description is found here: Swedish or English.

    The problem files are here: gsp.c, sph.c, visagrid.m, p6.m, p10.m, p11.m.
    (The file gsp.c should be compiled in Matlab ("mex gsp.c") in order to create the gsp command.)

    Important dates: Deadline for handing in the Matlab programs and their descriptions is 19 September. Deadline for the complete report, with Matlab-supported graphics of the best feasible solution for each problem, convergence charts for the subgradient algorithm (together with a discussion on your experience with using it!), and discussions on your feasibility heuristics, its complexity, and your experience with it (for example, did it always manage to find a feasible solution?) is 20 September. On 23 September there will be discussion sessions on Project 1. Each gruop should then give an oral presentation of their solution of the project assignment.

  • Project 2 - (updated 27 September 2011)

    The second project is described here (updated 110922). The deadlines are, however, updated below.

    Karin's licentiate thesis

    AMPL-files for solving the engineer's model (version 2011): MTC3_v4_proj_course.zip
    AMPL-files for solving the time-discrete model (version 2011): MTC6_v2_proj_course.zip

    AMPL CPLEX 12.1 Users Guide

    The AMPL homepage offers several examples of implementations of decomposition algorithms using AMPL-scripts at LOOPING AND TESTING 2

    Important dates and deadlines (updated 5 October 2011):

    • The deadline for sending the preliminary report to the teachers and the respective opponents is Monday morning, October 10
    • The competition tasks will then be published on Monday afternoon, October 10
    • The deadline for sending the computer program to the teachers is Tuesday morning, October 11
    • The oral presentations, oppositions and the competition will take place on Wednesday, October 12, at 10-12 in MV:L23
    • The deadline for sending in the final report Monday morning, October 17
    
    AMPL-files (version 2010):
    AMPL-files for solving the engineer's model (version 2010): MTC3_fix_y.mod, MTC3_fix_y.run, datfiles_MTC3.zip
    AMPL-files for solving the time-discrete model (version 2010): MTC4_v3_1_proj_course.mod, MTC4_v3_1_proj_course.run, datfiles_MTC4.zip

  Good luck!

  <body> </body>