Department of Systems Engineering
Operations Research
INFT 882: Advanced Topics in Combinatorial
Optimization
Wednesdays,
7:20-10:00p.m.
Research I:
Room 202
Professor Karla L. Hoffman
Office: SciTech
Building II, Room 123
Phone: (703)993-1679(direct) or 993-1670 (office)
Homepage: http://iris.gmu.edu/~khoffman/hoffman.html
Homepage for Course:
http://iris.gmu.edu/~khoffman/it882/it882_syllabus_f06.html
All materials for the course will be located at:
webct41.gmu.edu
To access these course materials, you will need to have registered for the course and have an active email account at GMU. You will log onto the webct site by using your email address name and password.
Office hours: Wednesdays: 1:00-3:00p.m.and by appointment
I am
usually on Mondays and Wednesdays from 9:30 to 6:30. I can also be available
after class on Wednesdays.
Text: Laurence A. Wolsey Integer Programming, John
Wiley & Sons 1999.
Alternative text: Nemhauser and Wolsey Integer and Combinatorial Optimization John Wiley and Sons, 1985
This course is designed to cover advanced topics in combinatorial optimization. The course will stress the explosion of new algorithmic results and their relationships to solving very large-scale integer programming problems. We will use the advanced routines within the CPLEX optimization package to implement some of these ideas. Other topics to be discussed will be recent heuristics developed for difficult combinatorial problems (e.g. linear-programming-based algorithms, tabu search, genetic algorithms and simulated annealing), new decomposition and variable splitting techniques, column generation techniques and the importance of new linear-programming technologies as they impact combinatorial problems. The course will require each student to read current research papers on a specific application area and provide both a written and oral presentation on the results of this literature survey.
In addition, we will use the Optimization Programming Language (OPL) to model some constraint generation methods, heuristic approaches and other new approaches for solving combinatorial optimization problems. This software can be downloaded from the ILOG web site at: www.ilog.com.
Proposed Topics:
Understanding Options of Optimizers
Combinatorial Auctions
Details of the traveling salesman problem and related routing problems
Decomposition techniques for solving difficult optimization problems
A. Benders decomposition
B. Dantzig-Wolfe Decomposition
C. Lagrangian Decomposition, Variable-splitting and Duality
D. Relationships of decomposition techniques to column generation
Recent advances in constraint programming and its effects on solvability of integer programming problems
Topics chosen by class.
For a view of a recent dissertation in combinatorial optimization, you can download Martin Durbin's dissertation: The Dance of the 30 Ton Trucks here: The Dance of the 30 Ton Trucks