TMA521/MMA510 Optimization, project course, 7.5 higher education credits, lp1 2010

Link to the homepage of the fall 2011 version of the course.

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

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

• The course starts on Wednesday 1 September 2010 at 10:00 in MV:F23. Welcome!
• Link to the TimeEdit schedule.


• Lecture plan. NEWS!! Lectures 8 and 9 will switch places: The lecture on optimality conditions (lecture 9) will be held on Friday 17/9; the second lecture on column generation (lecture 8) will be held on Monday 20/9


• Lecture schedule (All lectures, except those indicated, are given in the classroom MV:F23 at 10.00-11.45)
  • LV1 (week 35): Wednesday 1/9, Friday 3/9
  • LV2 (week 36): Monday 6/9, Wednesday 8/9, Friday 10/9
  • LV3 (week 37): Monday 13/9, Wednesday 15/9, Friday 17/9
  • LV4 (week 38): Monday 20/9, Wednesday 22/9, Friday 24/9
  • LV5 (week 39): Monday 27/9, Wednesday 29/9, Friday 1/10
  • LV6 (week 40): Most likely, no lectures this week but the following hours are booked, as a reserve: Monday 4/10, Wednesday 6/10, Friday 8/10
  • LV7 (week 41): Monday 11/10, Wednesday 13/10 (13 october also 13-15)


• Important dates and deadlines
  • 1 September: Introduction of project 1
  • 20 September: Deadline for programs, project 1
  • 23 September: Deadline for report, project 1
  • 24 September: Introduction of project 2
  • 29 September and 1 October: Discussion sessions of project 1
  • 6 October: Distribute preliminary version of report, project 2, to opponents
  • 11 October: Deadline for program and final report of project 2
    
  • 13 October (10-12 and 13-15): Competition and discussion of project 2

• Course literature:
  • Optimization Theory for Large Systems by Leon S. Lasdon, Dover Publications 2002, ISBN: 9780486419992.
    Legal copies of the book by Lasdon, 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 needed.

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

  • Simple/difficult problems (2 lectures)

    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 (Updated version 100901)

    Downloads for Lecture 2 (Updated version 100903)

    Questions on the network design problem

  • Lagrangian relaxation (3 lectures)

    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 (Updated version 100906)

    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 (Updated version 100908)

    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);
    • Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.5.
    Downloads for Lecture 5 (Updated version 100908)

  • Column generation (2 lectures)

    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 7 (Updated version, afternoon 100915)
    Downloads for Lecture 8 (Monday 20/9) (Updated and extended version, evening 100920) (Updated version, 101007)

  • Optimality conditions with applications (1 lecture)

    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 9 (Friday 17/9)

  • Benders decomposition (1 lecture)

    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 10

  • Presentation of project 2 (1 lecture)

    Downloads for Lecture 11
    Article describing the multitask cell

    ---

    • 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 should be made electronically by e-mail to Ann-Brith and Michael.

      • Project 1 (updated 23 August 2010)

        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 20 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 23 September. On 29 September and 1 October, 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 7 October 2010)

        The second project is described here.

        AMPL-files for solving the engineer's model: MTC3_fix_y.mod, MTC3_fix_y.run, datfiles_MTC3.zip

        AMPL-files for solving the time-discrete model: MTC4_v3_1_proj_course.mod, MTC4_v3_1_proj_course.run, datfiles_MTC4.zip

        AMPL CPLEX 12.1 Users Guide

        Important dates (updated 7 October 2010):

        • The deadline for sending the preliminary report to the teachers and the respective opponents is Monday morning, October 11.
        • The competition tasks will then be published on Monday afternoon, October 11.
        • The deadline for sending the computer program to the teachers is Wednesday morning, October 13.
        • The oral presentations, oppositions and the competition will take place on Thursday, October 14, at 8-10 in MV:L14.
        • The deadline for sending the final report to the teachers is Sunday evening, October 17.

      Good luck!

      <body> </body>