Configuring automatic relaxations
This section and the remainder of the chapter are addressed at more expert readers who, besides experience with CP, also have some knowledge of LP/MIP modeling and solving techniques.
Configuration choices
The formulation of a linear relaxation (sub)problem with Xpress Kalis has several components, namely the problem definition (=statement of variables and constraints), the configuration of a linear relaxation solver, and its insertion into the search strategy of the original CP problem. Here is a summary of the different steps and configuration choices.
- Choosing the constraint type
The following constraints can be relaxed automatically with Xpress Kalis:
- linear constraints
- all-different
- occurrence
- distribute
- min/max
- absolute value
- distance
- element
- cycle
- logical (implies, or, and, equiv)
- Choosing the relaxation type
Xpress Kalis generally provides several distinct relaxations for a given constraint. Methods cp_get_linrelax and get_linrelax take an integer parameter to choose the type of the relaxation (0 for an LP oriented relaxation and 1 for a MIP oriented relaxation). Besides the automatic relaxations, the user can also freely define his own relaxations of these or other constraints of his CP models (see Section User-defined relaxations below).
- Defining relaxation solvers
To solve a linear relaxation, Xpress Kalis uses relaxation solvers (model objects of the type cplinrelaxsolver) that define for the relaxation:
- an objective variable,
- an optimization sense (either minimization or maximization),
- a configuration of 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.
The following predefined configurations are implemented within Xpress Kalis:
- KALIS_TOPNODE_RELAX_SOLVER
- This configuration solves the relaxation only at the top node and provides bound for the objective variable.
- KALIS_TREENODE_RELAX_SOLVER
- This configuration solves the relaxation at each node of the search tree and 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 the resolution of the relaxation, all the other variables are instantiated to the optimal value of the relaxation. The main use of the bilevel configuration is to decompose simply and automatically the CP model in a master problem and a slave problem.
Note: a model can contain several linear relaxations solvers, e.g., for solving different subproblems or with different configuration options (such as one solver for the top node and a different relaxation solver for the tree nodes of the CP search).
- Branching with relaxation information
Certain predefined branching schemes and value and variable selection heuristics in Xpress Kalis are based on the optimal solution of a relaxation. The information obtained from the relaxations can be used to explore quickly the most promising portions of the search space. For example, a MIP style branching scheme is defined by
cp_set_branching(assign_and_forbid(KALIS_LARGEST_REDUCED_COST(mysolver), KALIS_NEAREST_RELAXED_VALUE(mysolver)))where the KALIS_LARGEST_REDUCED_COST variable selection heuristic selects the variable with the largest reduced cost in the optimal solution of the relaxation in the specified relaxation solver, and the KALIS_NEAREST_RELAXED_VALUE value selection heuristic selects the value in the domain of the variable that is the nearest (using L1-Norm) to the value of this variable in the optimal solution of the relaxation in the relaxation solver passed in the argument.
Implementation
The model shown below implements a similar relaxation as the automatic version in the previous section. This model has two parts: in the beginning we define a standard CP model for our Knapsack problem and trigger constraint propagation to display the initial bounds on the objective function. The second part shows how to define and configure a linear relaxation solver. At first, the model generates the automatic relaxation (and displays it on screen). The argument value 0 in cp_get_linrelax indicates that we want an LP-oriented relaxation (use 1 for a MIP-oriented relaxation). The relaxation solver defined with get_linrelax_solver is configured to maximize the objective benefit, solving the problem as a MIP, and this only once, at the first node of the CP search. The linear relaxation solver is added to the search process by a call to cp_add_linrelax_solver (there may be several solvers in a search process). The model definition is completed by a `MIP style' branching scheme that branches first on the variables with largest reduced cost, and tests first the values nearest to the optimal solution of the relaxation.
model "Knapsack with side constraints"
uses "kalis", "mmsystem"
declarations
VALUES = {1,3,8,9,12}
R = 1..4
x: array(R) of cpvar ! Decision variables
benefit: cpvar ! The objective to minimize
end-declarations
! Enable output printing
setparam("kalis_verbose_level", 1)
! Setting name of variables for pretty printing
forall(i in R) setname(x(i),"x"+i)
setname(benefit,"benefit")
! Set initial domains for variables
forall(i in R) setdomain(x(i), VALUES)
! Knapsack constraints
3*x(1) + 5*x(2) + 2*x(3) <= 50
2*x(1) + x(3) + 5*x(4) <= 75
! Additional global constraint
all_different(union(i in R) {x(i)})
! Objective function
benefit = 5*x(1) + 8*x(2) + 4*x(3) + x(4)
! Initial propagation
res := cp_propagate
! Display bounds on objective after constraint propagation
writeln("Constraints propagation objective ", benefit)
! **** Linear relaxation ****
declarations
myrelaxall: cplinrelax
end-declarations
! Build an automatic 'LP' oriented linear relaxation
myrelaxall:= cp_get_linrelax(0)
! Output the relaxation to the screen
cp_show_relax(myrelaxall)
mysolver:= get_linrelax_solver(myrelaxall, benefit, KALIS_MAXIMIZE,
KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)
! Define the linear relaxation
cp_add_linrelax_solver(mysolver)
! Define a 'MIP' style branching scheme using the solution of the relaxation
cp_set_branching(assign_var(KALIS_LARGEST_REDUCED_COST(mysolver),
KALIS_NEAREST_RELAXED_VALUE(mysolver)))
! Solve the problem
starttime:= gettime
if (cp_maximize(benefit)) then
write(gettime-starttime, "sec. ")
cp_show_sol ! Output optimal solution to screen
end-if
end-model
Results
The formulation of a CP model for this problem is straightforward. However, solving this type of problems with pure CP search methods tends to be very time consuming due to the poor quality of the bounds on the objective variable derived through constraint propagation. Formulating a MIP model for this problem is a perhaps somewhat more complicated task due to the need to linearize the 'all_different' relation. Here the automatic reformulation provided by Xpress Kalis is certainly helpful. The LP relaxation provides valuable bounds and insight on how to direct the search. Combining both makes the CP search go straight to the optimal solution and optimality is proven immediatly by the relaxation bounds. The configuration options allow you to tune the behavior of the combined solution algorithm.
Try to experiment with other settings:
- LP or MIP style relaxations (first parameter of cp_get_linrelax),
- relax only certain constraints, e.g., by specifying KALIS_LINEAR_CONSTRAINTS in cp_get_linrelax:
cp_get_linrelax(0, {KALIS_LINEAR_CONSTRAINTS}) - solving frequency (tree nodes or top node): last argument of get_linrelax_solver,
- subproblem type (LP or MIP): 4th argument of get_linrelax_solver.
Note: Instead of displaying the linear relaxation on screen you may also choose to export it to a file in LP format using procedure export_prob, specifying a linear relaxation solver and a matrix filename (the extension ".lp" will be appended to the name) as arguments.
export_prob(mysolver, "mymatfile")