Laurence Wolsey (Université catholique de Louvain, Belgium)

Short Biography

Laurence Wolsey is Professor of Applied Mathematics and Operations Research at CORE (Center for Operations Research and Econometrics) fro  the Universite Catholique de Louvain , Belgium . He received a Ph.D. in mathematics from the Massachusetts Institute of Technology in 1969. His main field of research is mixed integer programming, where he has given fundamental contributions both in theory and computations. He is author of fundamental textbooks in the domain: 'Integer Programming and Combinatorial Optimization' 1988 (with G. L. Nemhauser), a reference for researchers in the area; 'Integer Programming' 1998; and the recent 'Production Planning by Mixed Integer Programming' 2006 (with Y. Pochet). He has been visiting researcher in several Universities, and he has worked with research groups at several companies such as  BASF (production planning), France Telecom (multiplexer assignment) and DASH (commercial mixed integer programming systems). He has been editor OR Letters and Mathematical Programming.  He has received the Orchard-Hays prize in 1988 from the Mathematical Programming Society (with T.J. Van Roy), the Lanchester Prize in 1989 from the Operations Research Society of America (with G.L. Nemhauser), and the EURO Gold Medal in 1994.

Lecture to be presented in EWI 2007

Title

Separation and Decomposition in IP and MIP

Abstract

This talk aims to cover first the basic results and questions concerning implementable separation algorithms. This will then be used in the discussion of price and resource decomposition algorithms. Examples will be used to illustrate the main ideas.
In the case of price decomposition the first choice is between a cutting plane approach and a price decomposition approach using the Dantzig-Wolfe reformulation or the Lagrangian dual. In the latter case, once the reformulation/decomposition has been chosen, a second question is the choice of an appropriate algorithm. Finally we discuss briefly recent branch-and-cut-and-price algorithms.
For resource decomposition algorithms we discuss a generic reformulation and branch-and-cut algorithm. Then we specialize to Bender's algorithm and/or some of its variants, such as Branch-and-Check.

back