| |||||||||||||||||
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.
knapsackalld3a.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 *****************************************************************!) 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 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 | |||||||||||||||||
© Copyright 2024 Fair Isaac Corporation. |