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:
I. Understanding Options of Optimizers
II. Combinatorial Auctions
III. Details of the traveling salesman problem and related routing problems
IV. 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
V. Recent advances in constraint programming and its effects on solvability of integer programming problems
VI. 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