Constraint Integer Programming

For solving Integer Programs and Constraint Programs, a very similar
technique is used: the problem is successively divided into smaller
subproblems (branching) that are solved recursively.

On the other hand, Integer Programming and Constraint Programming have
different strengths: Integer Programming uses LP relaxations and
cutting planes to provide strong dual bounds, while Constraint
Programming can handle arbitrary (non-linear) constraints and uses
propagation to tighten the variable's domains.

In this talk, we discuss the different strengths, and how both
techniques can be integrated to benefit from both, strong dual bounds
and extensive modelling possibilities.

The software package SCIP is introduced, which is a framework for
Constraint Integer Programming oriented towards the needs of
Mathematical Programming experts who want to have total control of the
solution process and access detailed information down to the guts of
the solver. As an example, the "maximal feasible sub-LP" problem is
discussed, and it is shown how the problem can be solved with SCIP.

SCIP has the following features:
- framework for branching, cutting, pricing and propagation
- LP solver support through an LP interface
- highly flexible through many possible user extensions:
- constraint handlers to implement arbitrary constraints
- separators to apply cutting planes on the LP relaxation
- primal heuristics
- node selectors to guide the search
- branching rules to split the problem into subproblems
- presolvers to simplify the solved problem
- file readers to understand different input file formats
- event handlers to get informed each time a node was solved, a specific
variable changed its bounds, a new solution was found, ...
- display handlers to create additional columns in the solver's output
- every existing unit is implemented as a user extension, leading to an
interface flexible enough to meet the needs of most additional user
extensions
- simple preprocessing shell w.r.t. variables: the user may mix preprocessed
and active problem variables arbitrarily in any expression
- possibility of holes in a variable's domain
- cut pool management
- arbitrarily many children per node (arbitrary branching)
- possibility to solve or not to solve the LP relaxation at each single node
- conflict analysis to learn from infeasible subproblems
- dynamic memory management to reduce the number of operation system calls
with automatic memory checking in debug mode