| |||||||||||||
Els - An economic lot-sizing problem solved by cut-and-branch and branch-and-cut heuristics Description The version 'xbels' of this example shows how to implement cut-and-branch (= cut
generation at the root node of the MIP search) and 'xbelsc' implements a
branch-and-cut (= cut generation at the MIP search tree nodes)
algorithm using the cut manager.
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
xbels.java /******************************************************** Xpress-BCL Java Example Problems ================================ file xbels.java ``````````````` Economic lot sizing, ELS, problem, solved by adding (l,S)-inequalities) in several rounds looping over the root node. ELS considers production planning over a horizon of T periods. In period t, t=1,...,T, there is a given demand DEMAND[t] that must be satisfied by production prod[t] in period t and by inventory carried over from previous periods. There is a set-up up cost SETUPCOST[t] associated with production in period t. The unit production cost in period t is PRODCOST[t]. There is no inventory or stock-holding cost. (c) 2008-2024 Fair Isaac Corporation author: S.Heipcke, 2001, rev. Mar. 2011 ********************************************************/ import com.dashoptimization.*; public class xbels { static final double EPS = 1e-6; static final int T = 6; /* Number of time periods */ /****DATA****/ static final int[] DEMAND = { 1, 3, 5, 3, 4, 2}; /* Demand per period */ static final int[] SETUPCOST = {17,16,11, 6, 9, 6}; /* Setup cost / period */ static final int[] PRODCOST = { 5, 3, 2, 1, 3, 1}; /* Prod. cost / period */ static int[][] D; /* Total demand in periods t1 - t2 */ static XPRBvar[] prod; /* Production in period t */ static XPRBvar[] setup; /* Setup in period t */ /***********************************************************************/ static void modEls(XPRBprob p) throws XPRSexception { int s,t,k; XPRBexpr cobj,le; D = new int[T][T]; for(s=0;s<T;s++) for(t=0;t<T;t++) for(k=s;k<=t;k++) D[s][t] += DEMAND[k]; /****VARIABLES****/ prod = new XPRBvar[T]; setup = new XPRBvar[T]; for(t=0;t<T;t++) { prod[t]=p.newVar("prod" + (t+1)); setup[t]=p.newVar("setup" +(t+1), XPRB.BV); } /****OBJECTIVE****/ cobj = new XPRBexpr(); for(t=0;t<T;t++) /* Minimize total cost */ cobj .add(setup[t].mul(SETUPCOST[t]) .add(prod[t].mul(PRODCOST[t])) ); p.setObj(cobj); /****CONSTRAINTS****/ /* Production in period t must not exceed the total demand for the remaining periods; if there is production during t then there is a setup in t */ for(t=0;t<T;t++) p.newCtr("Production", prod[t] .lEql(setup[t].mul(D[t][T-1])) ); /* Production in periods 0 to t must satisfy the total demand during this period of time */ for(t=0;t<T;t++) { le = new XPRBexpr(); for(s=0;s<=t;s++) le .add(prod[s]); p.newCtr("Demand", le.gEql(D[0][t]) ); } } /**************************************************************************/ /* Cut generation loop at the top node: */ /* solve the LP and save the basis */ /* get the solution values */ /* identify and set up violated constraints */ /* load the modified problem and load the saved basis */ /**************************************************************************/ static void solveEls(XPRBprob p) throws XPRSexception { double objval; /* Objective value */ int t,l; int starttime; int ncut, npass, npcut; /* Counters for cuts and passes */ double[] solprod, solsetup; /* Solution values for var.s prod & setup */ double ds; XPRSprob op; XPRBbasis basis; XPRBexpr le; starttime=XPRB.getTime(); op=p.getXPRSprob(); op.setIntControl(XPRS.CUTSTRATEGY, 0); /* Disable automatic cuts - we use our own */ op.setIntControl(XPRS.PRESOLVE, 0); /* Switch presolve off */ ncut = npass = 0; solprod = new double[T]; solsetup = new double[T]; do { npass++; npcut = 0; p.lpOptimize("p"); /* Solve the LP */ basis = p.saveBasis(); /* Save the current basis */ objval = p.getObjVal(); /* Get the objective value */ /* Get the solution values: */ for(t=0;t<T;t++) { solprod[t]=prod[t].getSol(); solsetup[t]=setup[t].getSol(); } /* Search for violated constraints: */ for(l=0;l<T;l++) { for(ds=0.0, t=0; t<=l; t++) { if(solprod[t] < D[t][l]*solsetup[t] + EPS) ds += solprod[t]; else ds += D[t][l]*solsetup[t]; } /* Add the violated inequality: the minimum of the actual production prod[t] and the maximum potential production D[t][l]*setup[t] in periods 0 to l must at least equal the total demand in periods 0 to l. sum(t=1:l) min(prod[t], D[t][l]*setup[t]) >= D[0][l] */ if(ds < D[0][l] - EPS) { le = new XPRBexpr(); for(t=0;t<=l;t++) { if (solprod[t] < D[t][l]*solsetup[t] + EPS) le .add(prod[t]); else le .add(setup[t].mul(D[t][l])); } p.newCtr("cut" +(ncut+1), le.gEql(D[0][l]) ); ncut++; npcut++; } } System.out.println("Pass " +npass + " (" +(XPRB.getTime()-starttime)/1000.0 + " sec), objective value " + objval + ", cuts added: " + npcut + " (total " + ncut +")"); if(npcut==0) System.out.println("Optimal integer solution found:"); else { p.loadMat(); /* Reload the problem */ p.loadBasis(basis); /* Load the saved basis */ basis = null; /* No need to keep the basis any longer */ } } while(npcut>0); /* Print out the solution: */ for(t=0;t<T;t++) System.out.println("Period " + (t+1) + ": prod " + prod[t].getSol() + " (demand: " + DEMAND[t] + ", cost: " + PRODCOST[t] + "), setup " + setup[t].getSol() + " (cost: " + SETUPCOST[t] + ")"); } /***********************************************************************/ public static void main(String[] args) throws XPRSprobException, XPRSexception { try (XPRBprob p = new XPRBprob("Els"); /* Initialize BCL and create a new problem */ XPRS xprs = new XPRS()) { /* Initialize Xpress-Optimizer */ modEls(p); /* Model the problem */ solveEls(p); /* Solve the problem */ } } } | |||||||||||||
© Copyright 2023 Fair Isaac Corporation. |