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.

1. 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)
   To obtain an automatic relaxation of the whole problem, Xpress Kalis forms the intersection of the relaxations of the constraints of the CP model. This relaxation can be retrieved by a call to the function cp_get_linrelax. An optional argument to this function lets you specify the (set of) constraint types to relax. The relaxation for a specific constraint—as opposed to constraint type—is obtained with get_linrelax.
2. 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).

3. Defining relaxation solvers
   

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

   1. an objective variable,
   2. an optimization sense (either minimization or maximization),
   3. a configuration of when and what to do with the relaxation,
   4. 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.

   In addition to the predefined schemes, the user can take full control of the relaxation solver by means of callbacks (see Xpress Kalis reference manual for details).

   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).

4. 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): 4^th 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")