COMP 566 Autumn 2006
Course Announcements
Please check this page once a
week. New items
at the top of the page.
course home page lecture summaries
project/presentation information
Feeback session at Thomson House (thanks to Nathan Yu)
November 23: Midterm will be held in
Trottier 1080.
Please fill out course evalutations on line at : http://www.mcgill.ca/tls/courseevaluations/mercury/instructions-students/
Assignment 4 is posted, due Dec 5 in class.
Assignment 3 is posted, due Nov
9. (Misprint on page number for problem 3 corrected.)
Assignment 2 handed back in class
on Oct 17. Review sessionon that day.
Please send suggestions to Conor: cmeagh1 at cs.mcgill.ca
October 19: Midterm will be held
in Burnside Hall 1B23 (basement) 08:35-09:55.
Since Tues Oct 10 follows the Monday
schedule, there is no class.
You may hand in Assignment 2 at the next class, Thurs Oct 12.
Assignment 2
is posted, due Tues Oct 10 in class.
(Problem 3 has been added.) For question 2, system 1: only x_1 >=
0.
Teaching Assistant: Conor Meagher
http://www.cs.mcgill.ca/~cmeagh1/
Office: MC232
email: cmeagh1 at cs.mcgill.ca
Mon 10-11 and Wed 11-12 or by
appointment
Course software
In the course we make use of the packages 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-4.cs.mcgill.ca
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
Instructions for cplex can be found here.
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 DOS 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
Zimpl 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.
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.
The SOCS Inside-Out Website is a dynamic student initiative which
aims to
reduce frustration and raise the level of
computing competency at McGill.
It can be found on the web at http://www.cs.mcgill.ca/~guide.
Some pointers for those looking for projects:
http://www.optimization-online.org/
Informs Search of Annual Comprehensive Index Bibliographic Database
http://www.worms.ms.unimelb.edu.au/
ORMS today
http://www.lionhrtpub.com/ORMS.shtml
Prof. Goffin's home
page
Journals to check:
Mathematical Programming, Operations Research, Networks,
INFORS, Interfaces, Management Science