COMP 567 Discrete Optimization - II
Winter 2007
Course
News
Please check at least once a
week!
course home page
Test grades are here.
Solutions to Assignment 3 here.
March 28
class
test covers all material on Lecture notes and summaries web page up to
Mar. 7 (except Jan 8, 15, 17, 31, Feb 14) plus the three assignments.
Solutions
to Assignment 2
Step by step Maple output for question 3 is here
Assignment
3: Question 3 has been added. Due date revised to Wed
March 26. ass3.html
March 26: No classes, election day
Project
2007 page maintained by Conor is up. Please try to decide which
project you would like to be a consultant for by Monday Jan 22.
Assignment 1: Due Jan 29: Ch 1
Wolsey, P.19 #4, P.21 #10,11,12
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=4 or 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/local/pkgs/lrslib-041/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 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.