Selected Topics in Large Scale Discrete Optimization


PROGRESS IN LINEAR PROGRAMMING BASED BRANCH-AND-BOUND: MODELING AND METHODOLOGY

George L. Nemhauser

School of Industrial and Systems Engineering Georgia Institute of Technology

Wednesday, December 9, 1998

5:00 PM - 6:30 PM

Thursday, December 10, 1998

10:30 AM - 12:00 PM

DIMACS Center, CoRE Building, Room 431, Rutgers University



In the last decade, the use of mixed-integer programming (MIP) models has increased dramatically. Fifteen years ago, main frame computers were required to solve problems with a hundred integer variables. Now it is possible to solve problems with thousands of integer variables on a pc and to obtain provably good approximate solutions to problems such as set partitioning with millions of binary variables. These advances have been made possible by developments in modeling, algorithms, software and hardware.

In the first of these two expository talks, we will focus on applications, effective modeling and preprocessing.

The second talk will deal with the methodologies of branch-and-cut and branch-and-price, which are the techniques that make it possible to treat problems with either a very large number of constraints or a very large number of variables.