Solving Constraint Integer Programs

DATE: June 3, 2009

TIME: 2:00 PM – 3:00 PM

LOCATION: Executive Classroom

FEES: none

EVENT CONTACT:

Anita Race, H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race

TITLE: Solving Constraint Integer Programs

SPEAKER: Timo Berthold

ABSTRACT:

Constraint integer programming (CIP) is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. It is a generalization of MIP that supports the notion of general constraints as in CP. We introduce the software SCIP which is a solver and framework for constraint integer programming that also features SAT solving techniques.

We describe the various types of plugins which turn the basic CIP framework into a fully-fledged MIP solver and explain their role in the solving process. A special focus is put on branching rules, which are in the core of any branch-and-bound algorithm. We present hybrid branching, which combines variable selection rules from CP, MIP and SAT and outperforms state-of-the-art branching rules for MIPs on common MIP benchmark sets.