course
home page
assignments
lecture summaries
2010.7.20 Since Thursday July 22 is on a Monday
schedule, please hand in the paper version of your report in my office,
Engineering #10, Room 342, Thurs July 22, 8:45-10:15.
Otherwise please send by pdf file.
Have a nice summer holiday!
2010.6.3 Final report.
For
your final report I would like you to study a small application of
integer programming to a problem of your choice.
The
lectures on May 20 and May 27 give typical examples. You should
(a)
state the problem clearly in English, without using any formulas if
possible (manager's description of problem)
(b)
give an integer programming formulation, explaining the variables,
objective function and constraints
(c)
prepare a small sample input and solve your problem using lp_solve,
both as a linear program and as an integer program
(d)
study the polyhedron underlying a small version of your problem
(say 10 variables or less if possible) using lrs (like the Exercise for
May 20.)
The report is due on July 22,
either
by pdf file (preferred) or in class on July 22 (hand to Hiroki
Morizumi ). The last lecture will be on July 15.
If
you send the report by email, please send to both myself, avis at i.kyoto-u.ac.jp, and
Hiroki, morizumi at
kuis.kyoto-u.ac.jp
Note
that very large pdf files may be rejected by the mail handler. A typical report would have about 5 pages
or so.
2010.4.20
Mini report: For each class I would like one student to act as
'scribe' and make class notes. These should be sent in latex and pdf
format by email to both myself and Hiroki.
Please
use
the
template
latex
file: lec3.tex
which gives a pdf file
like this. Please use pdflatex and give
all figures as pdf files.
Please submit the notes within 10
days
of the lecture. We will fix the schedule at our next class.
2010.4.15 Hiroki Morizumi ( morizumi at
kuis.kyoto-u.ac.jp ) will be helping me with the course, so please
direct questions to him if you have difficulties.
2010.4.8 First class. Welcome!
Course software.
(Please ask Hiroki Morizumi ( morizumi at
kuis.kyoto-u.ac.jp ) if you have trouble installing the software)
lrs
This program computes all vertices of a polyhedron, given its facets,
or all facets given its vertices.
See the User's guide for instructions.
1. If you use linux, follow instructions in the user's guide, or try
the binaries in
http://cgm.cs.mcgill.ca/~avis/C/lrslib/binaries/linux
2. If you use Windows, there are some binaries in
http://cgm.cs.mcgill.ca/~avis/C/lrslib/binaries/windows
Read the directions here: http://cgm.cs.mcgill.ca/~avis/C/lrslib/binaries/windows/readme
lp_solve
This free 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.
Note all examples are in "lp-format", which I recommend.
The latest reference manual is here.
The full package is available for download from the lp_solve home page.
A nice help page with (an old version) DOS executable is available
at:
http://www.statslab.cam.ac.uk/~rrw1/opt/lp_solve/