Usage of relaxations

Xpress Kalis can create several distinct relaxations of a CP problem and solve them.

The optimal solution of these relaxations provides bounds for the CP branch-and-bound process and prunes the search tree with reduced costs propagation (optimality reasoning).

To solve a linear relaxation, Xpress Kalis uses relaxation solvers (of the type cplinrelaxsolver) that define for the relaxation:

• An objective variable for the relaxation
• An optimization sense (either KALIS_MINIMIZE or KALIS_MAXIMIZE)
• A configuration defining when and what to do with the relaxation.
• A flag indicating whether to solve the relaxation as a pure LP problem or as a MIP.(either KALIS_SOLVE_AS_LP or KALIS_SOLVE_AS_MIP

Several predefined configurations are implemented within Xpress Kalis:

• KALIS_TOPNODE_RELAX_SOLVER: This configuration solves the relaxation only at the top node and provides bounds for the objective variable.
• KALIS_TREENODE_RELAX_SOLVER: This configuration solves the relaxation at each node of the search tree. It provides bounds for the objective variable and performs reduced costs propagation.
• KALIS_BILEVEL_RELAX_SOLVER: This configuration solves the relaxation whenever all the variables (by default all the discrete variables such as cpvar) of a user defined set are instantiated. After solving of the relaxation, all the other variables are instantiated to their optimal value in the relaxation. The main use of the bi-level configuration is to decompose the CP model simply and automatically into a master problem and a slave problem.

The user can also take full control over the relaxation solver by the means of callbacks.

A relaxation solver is obtained by specifying three callbacks functions:

• must_relax: This function with no argument and returning a Boolean must return true whenever the users wants to solve the relaxation
• before_relax: This procedure with no argument is called just before the relaxation is performed
• after_relax(status: integer): This procedure with one argument is called after the relaxation has been solved. The status parameter indicates whether the relaxation is optimal (0) or infeasible (1). This callback can be used, for example, to instantiate some variables to their values in the optimal solution of the relaxation.

In addition to the user-configurable relaxations, Xpress Kalis provides a fully automated mode for using linear relaxations, enabled by the control parameter KALIS_AUTO_RELAX.