Department of Systems Engineering Operations Research

GEORGE MASON UNIVERSITY

INFT 882: Advanced Topics in Combinatorial Optimization

 

Professor Karla L. Hoffman

Science and Technology Building II, Room 119

(703)993-1679

 

Text: Laurence A. Wolsey Integer Programming, John Wiley & Sons 1999.

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. Decompositiong techniques for solving difficult optimization problems

A. Benders decompositon

B. Dantzig Wolfe Decomposition

C. Lagrangian Decomposition, Variable-splitting and Duality

D. Relationships of decomposition techniques to column generation

 

II. Heuristics for Integer Programming Problems

A. Tabu search

B. Genetic Algorithms

C. Simulated Annealing

D. Geometric-based algorithms 

 

III. Recent advances in constraint programming and its effects on solvability of integer programming problems

IV. Topics chosen by class.