FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

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


(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 */
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();
p.newCtr("DefX", lr[s].eql(x[s]) );
}

/* The convexity constraint (lam sum to 1) */
for(s=0;s<NS;s++) {
lc = new XPRBexpr();
p.newCtr("Conv", lc.eql(1) );
}

/* The minimum quantity that must be bought */
lc = new XPRBexpr();

/****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++) {
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 ****/
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 {
StreamTokenizer st;
int i=0;

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;
StreamTokenizer st;
int i=0;

/* Read the parameter file */
val = new double[2];
NS = (int)val[0];
NB = (int)val[1];
NB2 = 2*NB;

/* Now define the tables that we will use, using the sizes we
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;
}

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 */

/* Read the required amount data file */
REQ = val[0];

/* We now pick out the data from the tables into which they have
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 */
}
}

`