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
  benefit : 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(benefit,"benefit")

! 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
 benefit = 5*x1 + 8*x2 + 4*x3

! Initial propagation
 res := cp_propagate

! Display bounds on objective after constraint propagation
 writeln("Constraints propagation objective ", benefit)

! Solve the problem
 if (cp_minimize(benefit)) then
  cp_show_sol                      ! Output optimal solution to screen
 end-if

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
  benefit : 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(benefit,"benefit")

! 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
 benefit = 5*x1 + 8*x2 + 4*x3

! Initial propagation
 res := cp_propagate

! Display bounds on objective after constraint propagation
 writeln("Constraints propagation objective ", benefit)


 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_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
 cp_set_branching(assign_var(KALIS_LARGEST_REDUCED_COST(mysolver),
                             KALIS_NEAREST_RELAXED_VALUE(mysolver)))

! Solve the problem
 if (cp_minimize(benefit)) then
  cp_show_sol                      ! Output optimal solution to screen
 end-if

end-model

You will find below the list of relaxation related functions and procedures defined within Xpress Kalis: