TDA206/DIT370: Discrete Optimization 2011


Lecturer

Assistants

Course Reps

ANNOUNCEMENTS

Here is the Exam! . Due tomorrow (Tursday) 1600, Good Luck!

Note new extended exam hand in deadline: Thursday 1600 hrs.

The exam will be available on this site at 10.00 a.m. on Wednesday (16 March). Your solution has to be submitted to Vinay's office (EDIT 6453) by 1600 on Thursday (17th March).

Vinay: I'll be available between 10.00-12.00 A.M. on Monday (14 March) for any questions.

Course Description

The course is an introduction to understanding and using linear (LP) and convex programming and its applications. The focus is on what you can do with LP and convex programming and how it impacts computer science and mathematics broadly, rather than in detailed algorithms for optimization themselves, since the latter are well covered in other courses at Chalmers - see below. Our applications include classical topics in mathematics such as Game Theory and Coding theory and also modern currently active research areas such as approximation algorithms for NP-hard problems and support vector machines in machine learning.

Prerequisites

Some basic knowledge of discrete mathematics, linear algebra, probability and elementary calculus is essential. A basic course in algorithms and data structures is also useful.

Evaluation and Exam

Evaluation will be based on

Time and Place

Topics

Books

We will mainly cover material from these two books: Additional supplementary and complementary material will appear below as the course progresses.

Software

Related Courses

Lecture Diary

  1. [Jan. 17] Introduction to Optimization.[MG 1.1, 2.1]
  2. [Jan. 19] LP cont'd. [MG 2.1 - 2.5]
  3. [Jan. 24] Classification etc [MG 2.5 - 2.7], intro to integer LP [MG 3.1 - 3.2].
  4. [Jan, 31] Total unimodularity [MG 8.2] vertex cover [MG 3.3]
  5. [Feb.2] More examples: LP for oled displays and MAXSAT, see What Can't You do with LP? , section 7 where you can find the unfinished calculation from class completed.
  6. [Feb.7] Introduction to convex optimization. See slides for lectures 4 and 8 in Stanford course (above). Michel Goemans' SDP survey has MAXCUT in section 5, see also this talk slides .
  7. [Feb. 9] Convex sets, convex functions and convex opt, see these nice slides from probably the best machine Learning group on Earth. See also the slides from the Stanford course linked above.
  8. [Feb. 16]
    An Overview of Compressed Sensing and Sparse Signal Recovery via L1 Minimization
    Emmanuel Candes
    3 videos
  9. Introduction to LP duality [MG 6.1 - 6.2, 8.2] make sure to remember duality recipe and write down duals to as many LPs wyou have seen as possible!
  10. {Feb. 28] Two person zero sum games and LP [MG 8.1] Book derives the LPs a bit differently than I did in class, but the final LPs are the same. Complexity of computing Nash equilibrium in general games.
  11. [March 2] Primal Dual algorithms, Williamson's survey . the vertex cover algorithm is discussed in scetion 1, but it is a bit different from what we did in class. Teh uncapacitated facility location problem is discussed in section 4.1.
  12. [March 7] Primal dual for facility location and Simplex
  13. [March 9] Interior point methods and course review.

Exercise Diary

Each week a set of four problems will be posted here. Some of the problems are programming problems on GLPK or CVX while others are written submissions. Programming problems must be submitted using the FIRE system by Tuesday midnight (see detailed instructions below). Written solutions must be handed in by 10 AM on Monday in the lecture.
  1. [Jan. 19]
      Familiarise yourself with the GNU LP kit and follow this Tutorial part 1 . We will discuss basics about GLPK in this tutorial. Then submit the following problems using the FIRE system, see intructions below - for the first week, use LP Wk-1 as the exercise label to submit.

      Problem 1 Look up the examples in the glpk directory and find the programs for the Diet problem from section 2.1 and the Flow problem from section 2.2 in the textbook. Run the programs on the data from the textbook.

      Problem 2 Write a glpk program for the ice-cream problem for ice cream all year round in section2.3 and run it on the data there.

      Problem 3 Write glpk code for fitting a line, section 2.4 in the textbook and run it on the data given there.

      Problem 4 Write glpk code for separating points section 2.5 and run it on the data in the figure given there.

  2. [Jan. 26]
      Read Tutorial part 2 especially the post office example. We shall discuss how to do integer LP in glpk.

      Problem 1 Implement the LP for maximum weight matching [MG 3.2] in glpk. Run the example data on page 32 and check that the LP optimum is the same as the integer optimum by running the integer prog. option in glpk. Is the running time different?

      Problem 2 Implement the LP for minimum vertex cover [MG 3.3] in glpk. Run it on some example graphs to check if the LP optimum is the same as the integer optimum, and if not, what is their ratio? Is there any pattern about the values in the optimal solution? Run the program on the cycle on 10 vertices - what is the optimal integer and LP solution? Run the rounding algorithm in [MG 3.3] and compare the ratio of the resulting solution to the optimum. What improvements can you suggest?

      Problem 3 Same as Problem 2 but for the independent set problem from [MG 3.4].

      Problem 4 Modify the proof for the case of the maximum weight matching when the bipratite graph need not have the two subsets of the same size, as described at the end of sec. 3.2 on p. 36-37 in [MG].)

  3. [Feb. 15] Deadline Feb. 15 because of CHARM.
    1. Problem 0 Read Tutorial part 3

    2. Problem 1 Tintin is descending to the moon in his rocket. At time 0, he is H miles above the surface moving downwards with velocity v. He needs to land on the surface at time T with zero velocity (so no crash). At each time instant i between 0 and T, he can accelerate or decelerate, but this costs amount c in fuel for each unit of acceleration or deceleration. Write a GLPK module to determine the optimal strategy i.e. the plan that allows Tintin to land on the moon using a minimum amount of fuel.

    3. Problem 2 Write a Sudoku solver in GLPK. See this paper . Use it to solve the puzzle in Fig. 1 in that paper. Test it on example 1 , example 2 , example 3 , example 4

    4. Problem 3 A number of bricks of different sizes have to be packed into a large box, in such a way that the sum of all side lengths of the box is minimized. Each brick has to be positioned with its edges parallel to the edges of the whole box and naturally different bricks may not overlap. Model the problem as an integer LP and try to solve it for five cubes of lengths 1..5.
  • [Feb. 22] Exercise 4
    1. More information on CVX is available at: http://www.cvxr.com/cvx_usrguide.pdf

    2. Errata: The dataset exercise1.mat contains the matrices train_data and train_label NOT training_data and training_label

    3. The file graphs.tgz is a gzipped tar file. It can be uncompressed using the command: gunzip graphs.tgz; tar -xvf graphs.tar

    4. CVX example similar to Problem 2 can be found at: http://cvxr.com/cvx/examples/cvxbook/Ch05_duality/html/ex_5_39. Other CVX examples can be found at: http://cvxr.com/cvx/examples/
    5. You can use the commands: "pdist", "linkage" and "cluster" for hierarchical clsutering.
  • [Mar. 1]
    1. Implement a solver for 2 person zero sum games (in CVX). The input is n and m, the number of stratgies for the two players and the n by m payoff matrix. The ouput is the optimal stratgies for the two players. Use it to find the optimal stratgies in the following game: each player selects a number between 1 and 6. if the number are equal, it is a draw. If numbers differ by 1, then the player with the smaller number gets SEK 200. If the numbers differ by 2 or more then the player with the larger number wins SEK 100 from the other player.
    2. Derive and then solve the dual of the max margin classifier from the previous week's exercise (equation (3)). Highlight the points corresponding to non-zero duals.
    3. Study the derivation of the dual to the partitioning problem (equation (6)) in last week's exercise.Impelment in CVX a program to find the dual feasible solution in (5.8) in the textbook [BV]. Use it to derive lower bounds on the primal problems for the data in last week's exercise.

    4. For matrix partial derivatives, see The Matrix Cookbook
    5. Problem 3 (SDP) dual derivation has a deadline of March 7.
    6. SVM dual derivation has to be submitted in a separate doc/pdf file.

    FIRE system and Programming submissions

    Here is a link to the FIRE system for programming assignments submissions. Register yourself on the FIRE system as soon as possible and send email to Azam if there is any problem.

    Following guidelines should be strictly followed for the weekly programming exercises.

    1. Assignments are individual. Each student should submit his own work. You should not copy others work. Be aware of the Chalmers policy about cheating.
    2. Each week's exercise is due by Tuesday midnight next week.
    3. Deadlines are firm.
    4. No resubmission is allowed.
    5. For now, weekly problem sets will be graded out of 40 points and at the end scaled to 50% of total.
    6. To get full credit, write as general an implementation as you can, keeping the model and data part separate.

    Contents of a submission:

    1. General Information : A readme file (text/pdf) with the following contents:
      • Your name and personal number.
      • list of files in the attachment belonging to your submission.
      • Any other useful information for the grader.
    2. Problem description and code : For each problem in the week's problem set, write a separate file of the GLPK code (.mod) that runs on windows or linux. Include the following things as comments in the code:
      • Your name at the first line.
      • Problem statement and simple description of the solution.
      • The command to run the program.
      • Name of data file or any other file required to run the program (if any). Explain the format of input files.
      • With each line of code, give details of your program approach in comments. This description must explain to the grader how your program works, which variables/sets/parameters are used for what purpose, what restrictions different inequalities pose on the problem etc. In this way your code file will actually serve as a complete explanation of the problem at hand and the working logic of your program.
      • Complete answers to all theoretical and experimental questions given as part of the problem statement (if any), should also be answered using comments in your code file. You may use the c style comments /* */ for this purpose at the end of the code file.
    3. Others :
      • Data files required to run the program(s) must be included.
      • Put files (code and data etc) realted to each problem in a separate folder with name like problem 1, problem 2 etc. Then put all these folders into one folder with your NAME, then zip it and upload to the FIRE under appropriate assignment link.
    Last modified: Fri Mar 11 17:41:51 CET 2011