| |||||||||||||||||
Linear relaxations Description This set of examples requires Xpress Optimizerin addition to Xpress Kalis.
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
knapsackalld3b.mos (!**************************************************************** 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, rev. Jun. 2023 *****************************************************************!) 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 if not cp_propagate: exit(1) ! Display bounds on objective after constraint propagation writeln("Constraint 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) + 5*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 | |||||||||||||||||
© Copyright 2023 Fair Isaac Corporation. |