![]() | |||||||||||
| |||||||||||
Purchase - Definition of SOS-2 Description A model for optimal purchasing with price-breaks featuring a
complex MIP model, data input from file and using SOS-2. Further explanation of this example: Quick reference guide 'MIP formulations and linearizations', Section 3.3 Price breaks
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
Data Files xbpurch.java /******************************************************** Xpress-BCL Java Example Problems ================================ file xbpurch.java ````````````````` Purchasing problem using SOS-2. (c) 2008 Fair Isaac Corporation author: S.Heipcke, Jan. 2000, rev. Mar. 2011 ********************************************************/ /* WARNING. This model is not for the novice, but it does contain many * * useful ideas. * * The formulation is tricky because the discounts are all-quantity, * * so the graph of cost against quantity purchased is discontinuous. * * To maintain sanity in the special ordered set formulation, we must * * coarsen the discontinuity by stopping purchases just at the break * * point. */ import java.io.*; import com.dashoptimization.*; public class xbpurch { static final String PARAMSFILE = System.getProperty("XPRBDATA") + "/purchase/params.dat"; static final String MAXPERCFILE= System.getProperty("XPRBDATA") + "/purchase/maxperc.dat"; static final String REQFILE = System.getProperty("XPRBDATA") + "/purchase/required.dat"; static final String PRICEFILE = System.getProperty("XPRBDATA") + "/purchase/pricebk.dat"; /****TABLES****/ static int NS; /* Number of suppliers */ static int NB; /* Number of price breaks */ static int NB2; /* Useful parameter */ static double[][] UC; /* Unit cost */ static double[][] BR; /* Breakpoints (quantities at which unit cost changes) */ static double[][] X; /* Coarsened break points */ static double[][] C; /* Total cost at break points */ static double[] DELTA; /* Coarsening factors */ static double[] MAXPERC; /* Maximum percentage from each supplier */ static double REQ; /* Total quantity required */ static final double delta = 0.10; /* Base coarsening factor */ /***********************************************************************/ static void modPurchase() { XPRBexpr lobj, lc; XPRBexpr[] lr; int s,b; XPRBvar[] x; XPRBvar[][] lam; try (XPRBprob p = new XPRBprob("Purchase")) { /* Initialize BCL and create a new problem */ /****VARIABLES****/ x = new XPRBvar[NS]; /* Quantity to purchase from supplier s */ for(s=0;s<NS;s++) x[s] = p.newVar("x"); lam = new XPRBvar[NS][NB2]; for(s=0;s<NS;s++) for(b=0;b<NB2;b++) lam[s][b] = p.newVar("lam_" + (s+1)); /* Weights at breakpoint b for supplier s */ /****OBJECTIVE****/ lobj = new XPRBexpr(); for(s=0;s<NS;s++) /* Minimize the sum of costs*weights */ for(b=0;b<NB2;b++) lobj.add(lam[s][b].mul(C[s][b])); p.setObj(lobj); /* Set objective function */ /****CONSTRAINTS****/ /* Define x and also order the lam variables by breakpoint quantities */ lr = new XPRBexpr[NS]; for(s=0;s<NS;s++) { lr[s] = new XPRBexpr(); for(b=0;b<NB2;b++) lr[s].add(lam[s][b].mul(X[s][b])); p.newCtr("DefX", lr[s].eql(x[s]) ); } /* The convexity constraint (lam sum to 1) */ for(s=0;s<NS;s++) { lc = new XPRBexpr(); for(b=0;b<NB2;b++) lc.add(lam[s][b]); p.newCtr("Conv", lc.eql(1) ); } /* The minimum quantity that must be bought */ lc = new XPRBexpr(); for(s=0;s<NS;s++) lc.add(x[s]); p.newCtr("MustBuy", lc.gEql(REQ) ); /****BOUNDS****/ /* No more than the maximum percentage from each supplier */ for(s=0;s<NS;s++) x[s].setUB(MAXPERC[s]*REQ/100.0); /****SETS****/ /* Define the lam as SOS2 as we can linearly interpolate between the * breakpoints. The weights are the DefX coefficients augmented by 1 because BCL does not accept the weight 0. */ for(s=0;s<NS;s++) { for(b=0;b<NB2;b++) lr[s].add(lam[s][b]); p.newSos("SetLam", XPRB.S2, lr[s]); } /****SOLVING + OUTPUT****/ try { p.exportProb(XPRB.MPS,"purc"); /* Output to MPS file */ } catch(IOException e) { System.err.println(e.getMessage()); System.exit(1); } p.setSense(XPRB.MINIM); /* Choose the sense of the optimization */ p.mipOptimize(""); /* Solve the MIP-problem */ System.out.println("Objective: " + p.getObjVal()); /* Get objective value */ for(s=0;s<NS;s++) /* Print out the solution values */ System.out.print(x[s].getName() +":"+ x[s].getSol() +" "); System.out.println(); for(s=0;s<NS;s++) for(b=0;b<NB2;b++) System.out.print(lam[s][b].getName() +":"+ lam[s][b].getSol() +" "); System.out.println(); } } /***********************************************************************/ /**** Initialize the stream tokenizer ****/ static StreamTokenizer initST(FileReader file) { StreamTokenizer st=null; st= new StreamTokenizer(file); /* Initialize the stream tokenizer */ st.commentChar('!'); /* Use the character '!' for comments */ st.eolIsSignificant(true); /* Return end-of-line character */ st.ordinaryChar(','); /* Use ',' as separator */ st.parseNumbers(); /* Read numbers as numbers (not strings)*/ return st; } /**** Read single line data file ****/ static void readOneLineFile(String filename, double[] data) throws IOException { FileReader datafile=null; StreamTokenizer st; int i=0; datafile = new FileReader(filename); st = initST(datafile); do { do { st.nextToken(); } while(st.ttype==st.TT_EOL); /* Skip empty lines */ while(st.ttype == st.TT_NUMBER) { data[i++] = st.nval; if(st.nextToken() != ',') break; st.nextToken(); } } while( st.ttype == st.TT_EOL ); datafile.close(); } /**** Read data from files ****/ static void readData() throws IOException { int s,b; double[] val; FileReader datafile=null; StreamTokenizer st; int i=0; /* Read the parameter file */ val = new double[2]; readOneLineFile(PARAMSFILE,val); NS = (int)val[0]; NB = (int)val[1]; NB2 = 2*NB; /* Now define the tables that we will use, using the sizes we have just read. */ UC= new double[NS][NB]; BR = new double[NS][NB]; X=new double[NS][NB2]; C=new double[NS][NB2]; DELTA=new double[NB2]; MAXPERC=new double[NS]; /* Define coarsening factors */ DELTA[0]=0; DELTA[1] = -1*delta; for(b=2;b<NB2;b++) DELTA[b] = -1*DELTA[b-1]; /* Read the price and breakpoint data file */ for(s=0;s<NS;s++) for(b=0;b<NB;b++) { UC[s][b]=0; BR[s][b]=0; } datafile = new FileReader(PRICEFILE); st = initST(datafile); do { do { st.nextToken(); } while(st.ttype==st.TT_EOL); /* Skip empty lines */ if(st.ttype != st.TT_NUMBER) break; s=(int)st.nval; if(st.nextToken() != ',') break; if(st.nextToken() != st.TT_NUMBER) break; b=(int)st.nval; if(st.nextToken() != ',') break; if(st.nextToken() != st.TT_NUMBER) break; UC[s-1][b-1]=st.nval; if(st.nextToken() != ',') break; if(st.nextToken() != st.TT_NUMBER) break; BR[s-1][b-1]=st.nval; } while( st.nextToken() == st.TT_EOL ); datafile.close(); /* Read the percentages data file */ readOneLineFile(MAXPERCFILE,MAXPERC); /* Read the required amount data file */ readOneLineFile(REQFILE,val); REQ = val[0]; /* We now pick out the data from the tables into which they have been read. */ for(s=0;s<NS;s++) { C[s][0] = 0; /* First total cost and (new) breakpoint are (0,0) */ X[s][0] = 0; for(b=1;b<NB2;b++) { /* Rest calculated... */ C[s][b] = UC[s][b/2] * BR[s][(b-1)/2]; /* ...unit price*quantity */ X[s][b] = BR[s][(b-1)/2] + DELTA[b]; /* ...coarsened grids */ } } } /***********************************************************************/ public static void main(String[] args) { try { readData(); /* Data input from file */ } catch(IOException e) { System.err.println(e.getMessage()); System.exit(1); } modPurchase(); /* Formulate and solve the problem */ } }
| |||||||||||
© Copyright 2023 Fair Isaac Corporation. |