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)