Initializing help system before first use

Automatic relaxation

When developing a CP model we recommend that you always try the effect of using the automatic relaxation. Indeed, in many of the examples presented in the previous chapters (such as examples a4sugar_ka.mos from Section occurrence: Sugar production or j5tax_ka.mos from Section equiv: Location of income tax offices) we can simplify the model formulation by removing the definition of the search strategy and enabling the automated relaxation by adding the following line before the start of the optimization: 

 setparam("kalis_auto_relax",true)

whereby in many cases you will observe that the time to the first or optimal solution is shortened, or that optimality is proven faster than with CP-only search.

Integer knapsack problem with side constraint

The following integer knapsack problem with an additional 'all_different' constraint on its variables will serve us in this and the following sections to show how to work with linear relaxations:

maximize 5·x1 + 8·x2 + 4·x3 + x4
s.t. xj ∈ {1,3,8,9,12} for j = 1,2,3,4
3·x1 + 5·x2 + 2·x3 ≤ 50
2·x1 + x3 + 5·x4 ≤ 75
all-different(x1, x2, x3, x4)

Implementation

The model implementation shown below is fairly straightforward, with the exception of the setting of the control parameter KALIS_AUTO_RELAX. 

model "Knapsack with side constraints"
 uses "kalis"

 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 ****

! Enable automatic linear relaxations
 setparam("kalis_auto_relax", true)

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

end-model

Results

Enabling the automatic relaxation for this problem reduces the number of nodes spent by the search from 17 to 4. However, more time is spent in every node due to the overhead incurred by the LP solving. As solving times in this small problem are negligible in all formulations time measurements are not really meaningful; in larger problems the effect of using linear relaxations needs to be tested carefully.

Parent Topic Hybridization of CP and MP

© 2001-2019 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.