COMP 567   Discrete Optimization - II            Winter 2010

Course News                                 Please check at least once a week!        course home page

2010.3.29   Assignment 3 is posted in Assignments , due Due: Friday April 16, 2010, McConnell 232 (Conor’s office)

2010.3.25  Class presentations on March 29,31 follow the same schedule as we used for the proposals.
Remember attendance is compulsory.

2010.3.12 Solutions to Assignment 2 are here.

Mar 17 Class test. Based all material above except Jan 11, 13, Feb 15, 17, Mar 12 lectures and mixed integer cuts (section 8.7)

Mar 12 Special lecture on travelling salesman problem by Bill Cook. Please attend if at all possible!
Note time and location: 10:35 AM, Trottier Building 2100

2010.2.9   Project proposals schedule available from home page Projects  2010

2010.2.3   Solutions to Ass. 1 are here.

2010.2.2  The case studies problems are given here.

Your next task is to choose a problem and form a consultant group.
Since there are 20 students in the class, there will be 4 groups of 3 students and 2 groups of 4.
You could chat on WebCT or meet after class to set up the groups. This should be done this week !

2010.1.19  Assignment 1 is posted in Assignments, due Jan 27 in class. You will need to use cplex or lp_solve in the assignment, So read the notes below carefully.



Please read carefully the case study information

http://cgm.cs.mcgill.ca/~avis/courses/567/2010/casestudy.html

To open an account:
 Login to any SOCS machine at Trottier 3rd floor (or McConnell 110) with “newuser” as user name and “newuser” as password.
Then, follow the instructions to open an account.

Course software

In the course we make use of the packages cplex and zimpl, and to some extent maple, lp_solve, cplex and lrs. All are installed on lab
machines in Trottier:     labi-j.cs.mcgill.ca,         1<=i<=9 and 1<=j<=30      (Try i= 6 first).

You can connect remotely by ssh:   eg:    ssh lab6-10.cs.mcgill.ca

(if it does not work, try rebooting the local machine:    ctrl+alt+F1 -> ctrl+alt+delete   )

A full list of machine names in labs is here: http://www.cs.mcgill.ca/socsinfo/labs/

If you do not find the software,  try typing: %source /usr/socs/Cshrc
You will need to set the path for some of the software.

cplex     path: /usr/local/bin/cplex-10
Usage: cplex-10         gives you the cplex  command line prompt

Instructions for cplex can be found here
(It may be necessary to set an environment variable, see instructions above.)

zimpl    path: /usr/local/bin/zimpl

Usage:  zimpl [options] file ...

Free modelling tool for LPs and ILPs (constraint
generator to lp or mps formats).
http://www.zib.de/koch/zimpl/
It is easy to learn and use. On page 16 of the documentation
(http://www.zib.de/koch/zimpl/download/zimpl.pdf) you will find Chvatal's
diet problem as an example.


maple        path: /usr/local/bin/maple
A maple session that shows how to solve systems of equations is here.

lp_solve         path: /usr/local/pkgs/lp_solve_4.0/lp_solve
This program can be used to solve linear or integer linear programs.
Usage: lp_solve -S4 < input_file       (-S4 option gives dual variables)
Some examples input and output files are here.
The man page is here.

The full package is available for download from the lp_solve  home page.

A nice help page with windows executable is available at:
http://www.statslab.cam.ac.uk/~rrw1/opt/lp_solve/

lrs         path: /usr/bin/lrs
This program computes all of the extreme points (and extreme rays if any) of the
feasible region of an LP. Home page is: http://cgm.cs.mcgill.ca/~avis/C/lrs.html



Coin-Or   Computational Infrastructure for Operations Research
http://www.coin-or.org/
-->"an open-source community for operations research software in order
to speed development and deployment of models, algorithms, and cutting-edge
computational research." It has some neat cut generators for solving ILPs.


Symphony    Open source Mixed ILP solver that implements branch and cut
http://www.branchandcut.org/SYMPHONY/
-->it s very customizable and is part of COIN-OR. If you tweak things
right, you will solve tough ILPs faster than CPLEX can. You can even
implement your own cuts.


 Here is some information on some alternate texts:

Integer Programming and Combinatorial Optimization , W. Cook et al. 2002.
 A fairly recent book with lots of very nice proofs and material supplemental to what we will be studying.

Combinatorial Optimization, Papadimitriou and Steiglitz, 1982
  Despite its age, one of the best all round books on LP, ILP, Combinatorial Optimization and Complexity.

Integer and Combinatorial Optimization, Nemhauser and Wolsey, 1988, revised 1999
  The revised version (paperback) is  similar to the original, which is a good solid theoretical study
   of IP and CO. Lots of examples and exercises.

Combinatorial Optimization, A. Schijver, 2003
  Box set, 3 volumes, 1800 pages all for $140. A tour de force, but covers mostly the polynomial time side of the subject which we are not emphasizing in 567.

Theory of Linear and Integer Programming, A. Schrijver, 1986
 Very dense and comprehensive, best as a reference book.

I have all these in my office if you would like to take a look.