TMA521/MAM340 Project course: Optimization
TM, 5 credits, second quarter 2003
Examiners
Ann-Brith Strömberg <Ann-Brith.Stromberg@fcc.chalmers.se>,
tel.: 772 4297, Fraunhofer-Chalmers Research Centre, Industrial Mathematics
Ann-Brith's home page
Michael Patriksson <mipat@math.chalmers.se>,
tel.: 772 3529, room 5218,
Michael's home page
-
Course start: 17 March, 13.15-15.00, MD10.
-
A schedule has been set for MD10 at Fridays 10.00-11.45, not counting
the project related seminars which will be scheduled individually
at either of the following times: Thursday 13.15-15.00 or Friday
10.00-11.45.
The small number of students will make it necessary to turn
this into a reading course. Reading material will be provided in the
following areas, with roughly two areas being covered each week:
- Simple/difficult problems, example relaxations;
- Matroids and matroid intersections, network design;
- Lagrangian relaxation: strength of relaxations, dual methods,
primal recovery;
- Strictly convex optimization and regularization, with
applications to structural optimization;
- Optimality conditions for non-convex problems: heuristics and
core problems;
- Column generation: Dantzig-Wolfe decomposition, branch & price;
- Benders decomposition and integer programming heuristics, with
applications to financial computations
-
Projects in these and possibly also other areas should be chosen
within the first two weeks of the course. Discussions on the
projects, modelling and methodology selections, etctera, will be
discussed at special seminars. The examination is defined by a
successfully completed project work, oral and written presentations
of the work, active participation at the seminars, and an oral and
written opposition of another group's work. For marks higher than
"pass" on the course, an oral exam can be given individually.
Hand outs:
March 17: The paper [BFJ91], together with
slides; Chapter 3 (on well-solved problems) of [Wol98]; Chapter 2
(on 0-1 knapsack problems) of [MaT90]
March 21: Chapter 7 (on matroids) of [Law76]; Chapter 10 (on
Lagrangian duality) of [Wol98]; notes
on the network design problem
March 28: Paper [LPS98] on primal recovery; Paper [LaP93] on
global optimality conditions
April 4: Chapter 3 (on Dantzig--Wolfe and column generation)
of [Las70]; notes [Tak00] on column generation; notes
on column generation
April 11: Notes
on branch and price