/********************************************************
* Xpress-BCL Java Example Problems
* ================================
*
* file xbpurch.java
* `````````````````
* Purchasing problem using SOS-2.
*
* (c) 2008-2024 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 com.dashoptimization.*;
import java.io.*;
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() {
try (XPRBprob p = new XPRBprob("Purchase"); /* Initialize BCL and create a new problem */
XPRBexprContext context =
new XPRBexprContext() /* Release XPRBexpr instances at end of block. */) {
XPRBexpr lobj, lc;
XPRBexpr[] lr;
int s, b;
XPRBvar[] x;
XPRBvar[][] lam;
/****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 */
}
}
|
