(!******************************************************* Mosel Example Problems ====================== file benders_cont.mos ````````````````````` Benders decomposition for solving a simple MIP. - Solve the continuous problem (primal) for given solution values of the integer variables (Step 2 of the algorithm) *** Not intended to be run standalone - run from benders_decomp.mos *** (c) 2008 Fair Isaac Corporation author: S. Heipcke, Jan. 2006, rev. B. Vieira Oct. 2025 *******************************************************!) model "Benders (continuous problem)" uses "mmxprs", "mmjobs" parameters NINTVAR = 4 ! Number of integer variables NCTVAR = 5 ! Number of continuous variables NC = 5 ! Number of constraints end-parameters declarations ! Event codes exchanged with submodels EVENT_READY=2 EVENT_SOLVED=3 EVENT_INFEAS=4 EVENT_ADDFEASCUT=5 EVENT_ADDOPTCUT=6 EVENT_MAINSOLVED=7 IntVars = 1..NINTVAR ! Discrete variables CtVars = 1..NCTVAR ! Continuous variables Ctrs = 1..NC ! Set of constraints (orig. problem) A1: array(Ctrs,IntVars) of integer ! Coeff.s of continuous variables A2: array(Ctrs,CtVars) of integer ! Coeff.s of discrete variables b: array(Ctrs) of integer ! RHS values c1: array(IntVars) of integer ! Obj. coeff.s of continuous variables c2: array(CtVars) of integer ! Obj. coeff.s of cont variables sol_x: array(IntVars) of real ! Solution of main prob. (integers) sol_y: array(CtVars) of real ! Solution of primal subprob. (cont.) sol_u: array(Ctrs) of real ! Solution of dual subproblem for cuts (cont.) y: array(CtVars) of mpvar ! Decision variables for continuous subproblem constr : set of linctr ! Set of lin constr to associate with dual ray dual_ray : array(constr) of real ! Array to store dual ray, if infeasible obj_z: real ! Objective value Z to compare end-declarations initializations from "bin:shmem:probdata" A1 A2 b c1 c2 end-initializations Obj := sum(i in CtVars) c2(i) * y(i) send(EVENT_READY, 0) ! Model is ready (= running) ! STEP 2: Solve the dual problem for given solution values of x repeat wait ev:= getnextevent status:= getclass(ev) initializations from "bin:shmem:sol" sol_x end-initializations forall(j in Ctrs) Ctr(j):= sum(i in CtVars) A2(j,i) * y(i) <= b(j) - sum(i in IntVars) A1(j,i) * sol_x(i) writeln("\nSolving continuous problem (primal)...") minimize(Obj) ! If infeasible, get dual ray to add the feasibility cut if getprobstat=XPRS_INF then writeln("The primal subproblem is infeasible -> Add feasibility cut!") hasRay := getdualray(dual_ray) if hasRay then ! Extract the components of the dual ray for feasibility cut forall(j in Ctrs) sol_u(j):= dual_ray(Ctr(j)) initializations to "bin:shmem:sol" sol_u end-initializations send(EVENT_ADDFEASCUT, 0) else writeln("ERROR: No dual ray was found") exit(4) end-if elif getprobstat=XPRS_OPT then ! If problem has finite optimum, then there are two cases initializations from "bin:shmem:sol" obj_z end-initializations forall(i in CtVars) sol_y(i):= getsol(y(i)) ! Get values of original vars y writeln("Step 2 solution: obj: ", getobjval, ", sol_y: ", sol_y) if getobjval <= obj_z then ! Case 1) the objective of the subproblem matches z* => ! the point (y*,z*) is optimal and we can recover an optimal ! solution for the original problem by concatenating the ! optimal solution of the subproblem x* with y*. writeln("The primal subproblem has finite optimum with obj <= z*", " -> Optimal solution found!") initializations to "bin:shmem:sol" sol_x sol_y end-initializations send(EVENT_SOLVED, getobjval) else ! Case 2) the objective of the subproblem is > z*. ! Then from the optimal multipliers u* of the dual ! we can derive a violated Benders optimality cut: writeln("The primal subproblem has finite optimum with obj > z*", " -> Add optimality cut!") forall(j in Ctrs) sol_u(j):= getdual(Ctr(j)) ! Get values of dual vars u (from the primal subproblem) initializations to "bin:shmem:sol" sol_u end-initializations send(EVENT_ADDOPTCUT, 0) end-if else writeln("Dual subproblem has unknown status: ", getprobstat) end-if until false end-model