FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

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

xbpurchjava.zip[download all files]

Source Files

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 XPRB bcl;
 static XPRBprob p;
                    
/***********************************************************************/

 static void modPurchase()
 {
  XPRBexpr lobj, lc;
  XPRBexpr[] lr;
  int s,b;
  XPRBvar[] x;
  XPRBvar[][] lam; 

  bcl = new XPRB();             /* Initialize BCL */
  p = bcl.newProb("Purchase");  /* Create a new problem in BCL */
 
/****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 */
 }
} 

Back to examples browserPrevious exampleNext example