2012.3.21 Grades up until now are here.

Assignment 3 will be optional

It will cover all exercises up to and including the March 28 class. Due April 16 (Gary will pick up in MC320 at 10am)

If you do Ass. 3, each assignment will count 10 pts. If you do not do Ass. 3 then Ass. 1 and 2 count 15 pts each.

2012.3.14 A fast 8-core computer that runs the latest version of CPLEX 12 is cgm-server.cs.mcgill.ca

It is on a secure power supply, so is good for long runs.

2012.2.29 Class test on Monday March 19, ARTS 145. It covers all material in reading assignments on lecture summaries page up to and including Mar 12, and the first two assignments.

2012.2.26 Assignment 2: Exercises for the lectures on Jan 23,25,30, Feb 1,6,8 due on March 5 in class.(Note new date!)

2012.1.20 Please read Gary's excellent tutorial on using CPLEX remotely.

2012.1.18 Assignment 1: Exercises for the lectures on Jan 9,11,16,18 due on January 25 in class.

2012.1.18 The TA for the course will be Gary Roumanis. Please check out his web page:

http://www.cs.mcgill.ca/~grouma/567.html

Gary will be your main resource for questions about the assignments and especially issues with cplex and other course software.

Questions about the lectures should generally be addressed to me.

Please read carefully the case study information

http://cgm.cs.mcgill.ca/~avis/courses/567/2012/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.

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.

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/

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

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.