Linear relaxations

Topics covered in this chapter:

Some parts of an optimization problem may be best expressed and solved in the declarative (solver-independent) manner of Mathematical Programming (MP). Other parts benefit from constraint propagation and search directions provided by a CP solver. So why not trying to get the best of both worlds by combining the MP and CP approaches?

Xpress Kalis allows you to benefit from CP and MIP hybridization in a clean and easy way by means of linear relaxations of the CP model. Xpress Kalis can build automatically several linear (or mixed integer linear) relaxations of the CP problem and use Xpress Optimizer to solve them.

This process can be fully configured ranging from a complete user definition of the relaxation and choice of when to launch the relaxation to a fully automatic relaxation.

Xpress Kalis uses a double modeling approach by exchanging automatically and in bidirectional way, informations such as objective bounds, infeasibility, optimal relaxed solutions and reduced costs between the cp solver and the linear relaxations solver(s) during the search for a solution.

Note: the linear relaxation functionality of Xpress Kalis can only be used if Xpress Optimizer is installed and licensed.

Automatic relaxations

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 takes the intersection of the relaxations of the constraints of the constraint programming model. Such a relaxation is obtained by a simple call to the function cp_get_linrelax

Note that this method is parameterized with an integer parameter since Xpress Kalis offers several relaxations for each constraint. In the present case, 0 means an LP oriented relaxation and 1 means a MIP oriented relaxation.

User defined relaxations

Xpress Kalis allows the user to define his own relaxation for the problem and provides several operators, functions and methods for this purpose:

• Overloaded operators for the specification of linear inequalities in a linear relaxation.
• The method get_linrelax(ctr: cpctr) returns the automatic relaxation for a constraint.
• The set_integer method turns variables in the relaxation into discrete variables (by default all relaxation variables are considered as continuous).
• Variables can be defined either in both, CP model and relaxation, or only in the CP model, or only in the relaxation (auxiliary variables).

Auxiliary variables (of the type cpauxvar) are additional variables that are used only in the definition of the relaxation and not in the formulation of the CP problem. For example, they can be used to linearize non-linear constraints or to express choices in the relaxation.

The CP model will not see these variables (no propagation and no branching) except for one particular kind of auxilliary variables called indicators. These indicator variables are 0-1 integer variables that are linked to cpvar variables. There is one indicator variable per value in the domain of a cpvar, and the indicator takes the value 1 if and only if this cpvar is instantiated to the value associated with the indicator variable. Bounds on indicator variables are automatically propagated by Xpress Kalis and reduced costs provided by the relaxation are retro-propagated to the CP variables by the means of reduced costs fixing (a kind of propagation reasoning on optimality).

Indicator variables are created and retrieved by a call to the get_indicator function.

The following examples show some expressions that can be used in the definition of custom relaxations:

 declarations		
  myrelax: cplinrelax               ! A linear relaxation	
  a1,a2  : cpauxvar                 ! Auxiliary variables for relaxation	
  taux   : array(1..4) of cpauxvar  ! Array of auxiliary variables
	
  x1,x2,x3: cpvar                   ! Finite domain variables	
  z       : cpfloatvar              ! CP variable with continuous domain	
  CAlld   : cpctr                   ! A CP constraint
 end-declarations
	
! Define an 'alldifferent' constraint	
 CAlld := all_different({x1,x2,x3})

! Build an automatic 'LP' oriented linear relaxation
 myrelax1 := cp_get_linrelax(0)

! Setting bounds on the auxiliary variables
 setdomain(a2,0,1)
 setdomain(a1,0.56,18.67)

! Adding linear inequalities to the relaxation
 myrelax += 3*a1      <= 3
 myrelax += a1+a2     >= 3.1
 myrelax += 2*a1-4*a2  = 3
 myrelax += a1-x1      <= 3.4
 myrelax += a1+4*a2-z <= 3
 myrelax += get_linrelax(CAlld,0)
 myrelax +=
   get_indicator(x1,1) + get_indicator(x2,1) + get_indicator(x3,1) <= 1
 myrelax += sum(i in 1..4) taux(i) = 4

! Set integrality condition for variables in the relaxation
 set_integer(myrelax,a2,true)
 set_integer(myrelax,x1,true)
	
! Output the resulting relaxation to the screen
 cp_show_relax(myrelax)

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 principal use of the bi-level configuration is to decompose the CP model simply and automatically into a main problem and a subproblem.

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.

Branching with relaxation

Xpress Kalis defines predefined branching schemes and value and variable selection heuristics based on the optimal solution of a relaxation:

• KALIS_LARGEST_REDUCED_COST variable selection heuristic selects the variable with the largest reduced cost in the optimal solution of the relaxation used by the specified relaxation solver.
• KALIS_NEAREST_RELAXED_VALUE value selection heuristic selects the value in the domain of the variable that is the nearest (in L1) to the value of this variable in the optimal solution of the relaxation used by the specified relaxation solver.

Moreover, the fix_to_relaxed method can be called during the tree search process to instantiate all the continuous variables to their values in the optimal solution of a relaxation.

This can be useful with some specific problem structures and in combination with the KALIS_BILEVEL_RELAX_SOLVER configuration for the relaxation solver to obtain an automatic logical benders decomposition of the solving process.

A simple hybrid example

Consider the following knapsack problem with an additional non linear constraint: all-different

A pure and straightforward CP approach for formulating and solving this problem is shown below:

model "Knapsack with side constraints"
 uses "kalis"

 declarations
  x1,x2,x3: cpvar                   ! Decision variables
  cost: cpvar                       ! The objective to minimize
 end-declarations

! Enable output printing
 setparam("kalis_verbose_level", 1)

! Setting name of variables for pretty printing
 setname(x1,"x1"); setname(x2,"x2"); setname(x3,"x3")
 setname(cost,"cost")

! Set initial domains for variables
 setdomain(x1, {1,3,8,12})
 setdomain(x2, {1,3,8,12})
 setdomain(x3, {1,3,8,12})

! Knapsack constraint
 3*x1 + 5*x2 + 2*x3 >= 30

! Additional global constraint
 all_different({x1,x2,x3})

! Objective function
 cost = 5*x1 + 8*x2 + 4*x3

! Initial propagation
 if not cp_propagate: exit(1)

! Display bounds on objective after constraint propagation
 writeln("Constraint propagation objective ", cost)

! Solve the problem
 if cp_minimize(cost):
   cp_show_sol                    ! Output optimal solution to screen

end-model

This model formulation can be augmented by the definition of a linear relaxation.

We start by getting an automatic relaxation of the problem by a call to the function cp_get_linrelax. The resulting relaxation can be displayed (printed to the standard output) with a call to the procedure cp_show_relax.

From the linear relaxation a linear relaxation solver is built with a call to the get_linrelax_solver method. Note that the KALIS_TOPNODE_RELAX_SOLVER argument passed to the method indicates that we just want to solve the linear relaxation at the top node of the CP search tree.

Having obtained the linear relaxation solver, we need to add it to the search process by a call to cp_add_linrelax_solver. Of course, Xpress Kalis is not limited to one relaxation so several solvers can be defined and added to the search process.

The model definition is completed by specifying 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. The invocation ot the search and solution display remain the same as in the CP model.

This is the full hybrid model:

model "Knapsack with side constraints"
 uses "kalis"

 declarations
  x1,x2,x3: cpvar                   ! Decision variables
  cost: cpvar                       ! The objective to minimize
 end-declarations

! Enable output printing
 setparam("kalis_verbose_level", 1)

! Setting name of variables for pretty printing
 setname(x1,"x1"); setname(x2,"x2"); setname(x3,"x3")
 setname(cost,"cost")

! Set initial domains for variables
 setdomain(x1, {1,3,8,12})
 setdomain(x2, {1,3,8,12})
 setdomain(x3, {1,3,8,12})

! Knapsack constraint
 3*x1 + 5*x2 + 2*x3 >= 30

! Additional global constraint
 all_different({x1,x2,x3})

! Objective function
 cost = 5*x1 + 8*x2 + 4*x3

! Initial propagation
 if not cp_propagate: exit(1)

! Display bounds on objective after constraint propagation
 writeln("Constraint propagation objective ", cost)


 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, cost, KALIS_MINIMIZE,
                KALIS_SOLVE_AS_MIP, KALIS_TOPNODE_RELAX_SOLVER)

! Define the linear relaxation
 cp_add_linrelax_solver(mysolver)

! Define a 'MIP' style branching scheme using the solution of the
! optimal relaxation
 br1 := KALIS_LARGEST_REDUCED_COST(mysolver)
 br2 := KALIS_NEAREST_RELAXED_VALUE(mysolver)
 cp_set_branching(assign_var(br1, br2))

! Solve the problem
 if cp_minimize(cost):
   cp_show_sol                  ! Output optimal solution to screen

end-model

You will find below the list of relaxation related functions and procedures defined by the kalis module: