Cost Based Filtering

Constraint Programming global constraints are very effective tools enabling concise modeling. From an operational perspective they can be seen as software components embedding powerful filtering algorithms able to remove provably infeasible portions of the search  space.

In optimization problems, beside feasibility reasoning global constraints can perform optimality reasoning and prune the search space by removing provably sub-optimal parts.

Optimization global constraints embed, beside the traditional filtering algorithm, an optimization component modeling a relaxation of the constraint itself and providing three pieces of information:

1. the optimal solution of the relaxed problem - x*
2. the optimal value of the objective function - LB
3. a set of reduced costs - grad(X,v)

These pieces of information can be used to filter the domain of variables involved in the constraint.

The optimization component can be either a linear relaxation possibly tighted with cutting planes or a combinatorial relaxation.