The dates for the oral presentations/reviews are specified in the detailed course plan

The deadline for handing in the report appears from the assignment submission tool (will be published after November 8, when all student groups are created).

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 Lagrangean subproblems and illustrate the solutions, but you will write the code for subgradient optimization, computation of ergodic sequences, and heuristic algorithms in Matlab.

Project description
Problem files (The file gsp.c should be compiled in Matlab ("mex gsp.c") in order to create the gsp command.)
Article by Feo & Hochbaum (1986) (describes the VLSI design problem)
MSc thesis by Juneberg (2001) (includes ideas for adaption of step length parameters in subgradient optimization)
MSc thesis (2015) by Aldenvik & Schierscher (includes ideas for utilizing ergodic sequences of subproblem solutions for finding good feasible (i.e., integer/binary) solutions)
Article by Larsson, Patriksson, & Strömberg (1999) (convergence of ergodic sequences)
Article by Gustavsson, Patriksson, & Strömberg (2015) (convergence of enhanced ergodic sequences)

Template for presentation slides using Latex Beamer

List of groups for presenting the project as well as opponents, on November 22 will be presented here.

In the submission tool, each student must also write an individual collaboration report, stating the contribution of each student to the results and the report. This report should be submitted as a comment to the assignment.