User-defined relaxations

As an alternative or in addition to the built-in relaxation definitions, linear relaxations (or parts thereof) can be built up from scratch, similarly to the definition of linear constraints in a pure CP model. For the representation of linear relaxations, Xpress Kalis provides the types cpauxvar and cpauxlinexp (for variables and linear expressions that do not occur in the original CP model). The linearization of certain global constraints requires a mapping from integer-valued CP decision variables to sets of 0-1 indicator variables in the LP/MIP formulation, where each indicator variable is associated with a value in the domain of the CP variable. These indicator variables (of type cpauxvar) are obtained with function get_indicator. Besides these special variable types, linear relaxation constraints can also contain variables of type cpvar or cpfloatvar.

Implementation

The implementations below replace the configured definition of a relaxation by a relaxation built up 'manually' by stating the constraints one by one. Just like the previous model version, a relaxation solver is defined with get_linrelax_solver. This linear relaxation solver is then added to the search process by a call to cp_add_linrelax_solver and 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.

This model extract selects one by one the constraints to be added to the relaxation:

 declarations
  myrelax: cplinrelax
 end-declarations

! Build an 'LP' oriented linear relaxation
 myrelax:= get_linrelax(all_different(union(i in R) {x(i)}), 0)
 myrelax += get_linrelax(3*x(1) + 5*x(2) + 2*x(3) <= 50, 0)
 myrelax += get_linrelax(2*x(1) + x(3) + 5*x(4) <= 75, 0)
 myrelax += get_linrelax(benefit - (5*x(1) + 8*x(2) + 4*x(3) + x(4)) = 0, 0)

 mysolver:= get_linrelax_solver(myrelax, benefit, KALIS_MAXIMIZE,
                KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)

! Output the relaxation to the screen (after creation of solver to see all!)
 cp_show_relax(myrelax)

! 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

When adding linear constraints to the relaxation we have the choice to add them directly, or by using the function get_linrelax as in the model extract above. When using this function we can specify through its second argument whether to disregard the integrality condition on any variables the linear constraint.

If we do not want to use any of the built-in relaxation functionality, we can also state the relaxations 'manually'. In the example below the linear relaxation is formulated entirely with the binary indicators for domain values, leaving out the variables x_i that are present in all the automated relaxation versions we have seen so far.

 declarations
  myrelax: cplinrelax
 end-declarations

! Build a user-defined linear relaxation

! Formulation of 'alldifferent':
 forall(val in VALUES)
  myrelax += sum(i in R | contains(x(i),val)) get_indicator(x(i), val) <= 1
 forall(i in R)
  myrelax += sum(val in VALUES | contains(x(i),val)) get_indicator(x(i), val) = 1

! Reformulation of linear constraints
 myrelax +=
  3*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +
  5*sum(val in VALUES | contains(x(2),val)) val*get_indicator(x(2), val) +
  2*sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) <= 50
 myrelax +=
   2*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +
   sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) +
   2*sum(val in VALUES | contains(x(4),val)) val*get_indicator(x(4), val) <= 75
 myrelax += benefit -
  (5*sum(val in VALUES | contains(x(1),val)) val*get_indicator(x(1), val) +
   8*sum(val in VALUES | contains(x(2),val)) val*get_indicator(x(2), val) +
   4*sum(val in VALUES | contains(x(3),val)) val*get_indicator(x(3), val) +
   sum(val in VALUES | contains(x(4),val)) val*get_indicator(x(4), val)) = 0

 mysolver:= get_linrelax_solver(myrelax, benefit, KALIS_MAXIMIZE,
                KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)

Results

When comparing the program output obtained from the two formulations above, it appears that the automatic formulation provides better guidance to the CP search (that is, less nodes are required to terminate the enumeration) than the 'manual' formulation that works exclusively with the binary indicator variables. There often are different possibilities for formulating linear relaxations and some experimentation is required to determine which is the best choice.

General recommendations for the formulation of linear relaxations are (a) to be careful to define a relaxation that makes sense and (b) to make sure that the relaxation is connected to the original problem (through variables shared by both formulations) so to obtain the desired benefits from information exchange between the two views of the problem.

Note: Xpress Kalis also makes accessible additional configuration options for the underlying LP/MIP solver; the interested reader is referred to the documentation of set_linrelax_solver_attribute in the the Xpress Kalis Reference manual.