(!****************************************************************
CP example problems
===================
file knapsackalld.mos
`````````````````````
Knapsack problem with additional alldifferent
constraint solved using linear relaxations.
- Using default settings for relaxation -
(c) 2009 Artelys S.A. and Fair Isaac Corporation
Creation: 2009, rev. Mar. 2013
*****************************************************************!)
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
|
(!****************************************************************
CP example problems
===================
file knapsackalld2.mos
``````````````````````
Knapsack problem with additional alldifferent
constraint solved using linear relaxations.
- Configuring a linear relaxation -
(c) 2009 Artelys S.A. and Fair Isaac Corporation
Creation: 2009, rev. Mar. 2013
*****************************************************************!)
model "Knapsack with side constraints"
uses "kalis", "mmsystem"
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 ****
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_MAXIMIZE,
KALIS_SOLVE_AS_LP, KALIS_TREENODE_RELAX_SOLVER)
! 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
end-model
|
(!****************************************************************
CP example problems
===================
file knapsackalld3.mos
``````````````````````
Knapsack problem with additional alldifferent
constraint solved using linear relaxations.
- User-defined linear relaxation -
(c) 2009 Artelys S.A. and Fair Isaac Corporation
Creation: 2009, rev. Mar. 2013
*****************************************************************!)
model "Knapsack with side constraints"
uses "kalis", "mmsystem"
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 ****
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
end-model
|
(!****************************************************************
CP example problems
===================
file knapsackalld3.mos
``````````````````````
Knapsack problem with additional alldifferent
constraint solved using linear relaxations.
- User-defined linear relaxation -
(c) 2009 Artelys S.A. and Fair Isaac Corporation
Creation: 2009, rev. Mar. 2013
*****************************************************************!)
model "Knapsack with side constraints"
uses "kalis", "mmsystem"
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 ****
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)
! 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
end-model
|
