Solving Constraint Integer Programs 0.90 review
DownloadSolving Constraint Integer Programs is a framework for constraint integer programming
|
|
Solving Constraint Integer Programs is a framework for 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.
SCIP 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. SCIP can also be used as pure MIP solver or as framework for branch-cut-and-price.
Here are some key features of "Solving Constraint Integer Programs":
It is a framework for branching, cutting, pricing, and propagation.
It is highly flexible through many possible user plugins:
constraint handlers to implement arbitrary constraints,
variable pricers to dynamically create problem variables,
domain propagators to apply constraint independent propagations on the variables' domains,
cut separators to apply cutting planes on the LP relaxation,
relaxators to provide relaxations and dual bounds in addition to the LP relaxation,
primal heuristics to search for feasible solutions with specific support for probing and diving,
node selectors to guide the search,
branching rules to split the problem into subproblems,
presolvers to simplify the solved problem,
file readers to parse different input file formats,
event handlers to be informed on specific events, e.g., when a node was solved, a specific variable changed its bounds, or a new primal solution was found,
display handlers to create additional columns in the solver's output.
dialog handlers to extend the included command shell.
Every existing unit is implemented as a plugin, leading to an interface flexible enough to meet the needs of most additional user extensions.
A dynamic cut pool management is included.
The user may mix preprocessed and active problem variables in expressions: they are automatically transformed to corresponding active problem variables.
Arbitrarily many children per node can be created, and the different children can be arbitrarily defined.
It has an open LP solver support (currently supporting ILOG CPLEX, Dash XPress-MP, SoPlex, and CLP.
The LP relaxation need not to be solved at every single node (it can even be turned off completely, mimicing a pure constraint solver).
Additional relaxations (e.g., semidefinite relaxations or Lagrangian relaxations) can be included, working in parallel or interleaved.
Conflict analysis can be applied to learn from infeasible subproblems.
Dynamic memory management reduces the number of operation system calls with automatic memory leakage detection in debug mode.
What's New in This Release:
The new heuristics "RENS", "mutation", "veclendiving", and "intshifting", were included.
The existing ones were improved.
Presolving and c-MIR cut generation were improved.
A few bugs were fixed.
Solving Constraint Integer Programs 0.90 keywords