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 for Course: 

All materials for the course will be located at:

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:

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