IE 518 Discrete Optimization

• Integer Programming by L. Wolsey, 1998, Wiley & Sons.
• An introduction to complexity, polyhedral theory and combinatorial optimization by G. Dahl
• A survey on primal-dual approximation algorithms by M. Goemans and D. Williamson.
• Slides of lecture notes on primal-dual approximation algorithms by D. Williamson.
• A more recent survey on primal-dual approximation algorithms by D. Williamson.
• Slides of more recent lecture notes on primal-dual approximation algorithms by D. Williamson.
• Slides of introductory lecture notes on primal-dual approximation algorithms by E. Bauer and M. Zinkevitch.
• Lecture notes on approximation algorithms by Vazirani.

The students are expected to acquire basic skills in using the AMPL modeling language. For general information see AMPL's site. You can find a library of  ampl solution models here.

We will also be using the GAMS modeling language. The students will be asked to familiarize themselves with GAMS through homework exercises.  Feel free to visit the GAMS homepage  and browse the large collection of models.

The syllabus is available here.

 

Homeworks:	60 % Hw1: Due  Hw2: Due  Hw3: Due  Hw4: Due
Term Paper:	0 %
Final:	40 % Take home due date: June 4, 2001 The two toy problems for you to check your algorithms I. 5 clients, 4 potential facilities, p=2         2  5  9  7  d_ij = 3  7  6  1         5  8  3  7         4  3  9  1         6  1  3  7 II. 5 clients, 4 potential facilities, p=2         2  3  5  4  d_ij = 3  7  5  1         6  5  4  1         6  7  3  6         1  6  8  4
Participation:	0 %