Fall 2012 Seminar Series

DATE: December 13th
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following

SPEAKER:
Juan Pablo Vielma

TITLE
Encodings in Mixed Integer Linear Programming

ABSTRACT
In mathematical programming binary variables are commonly used to model alternatives, disjunctions or unions of polyhedra. Recent interest in this area has concentrated in formulations that model n alternatives with log n binary variables as they can provide a significant computational advantage. In this talk we show how a simple procedure can be used to construct both traditional and logarithmic formulations from different encodings of the alternatives. In this setting, traditional formulations are associated to unary encodings and logarithmic formulations are associated to binary encodings. We also show how other encodings lead to formulations that can outperform existing approaches.