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

xbpurchcpp.zip[download all files]

Source Files

Data Files





xbpurch.cxx

/********************************************************
  Xpress-BCL C++ Example Problems
  ===============================

  file xbpurch.cxx
  ````````````````
  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. */
 
#include <iostream>
#include <cstdio>
#include "xprb_cpp.h"

using namespace std;
using namespace ::dashoptimization;

#define PARAMSFILE  XPRBDATAPATH "/purchase/params.dat"
#define MAXPERCFILE XPRBDATAPATH "/purchase/maxperc.dat"
#define REQFILE     XPRBDATAPATH "/purchase/required.dat"
#define PRICEFILE   XPRBDATAPATH "/purchase/pricebk.dat"

/****TABLES****/
int NS;             /* Number of suppliers */
int NB;             /* Number of price breaks */
int NB2;            /* Useful parameter */

double **UC;        /* Unit cost */
double **BR;        /* Breakpoints (quantities at which unit cost changes) */
double **X;         /* Coarsened break points */
double **C;         /* Total cost at break points */
double *DELTA;      /* Coarsening factors */
double *MAXPERC;    /* Maximum percentage from each supplier */
double REQ;         /* Total quantity required */

double delta = 0.10;        /* Base coarsening factor */

XPRBprob p("Purchase");     /* Initialize a new problem in BCL */
                    
/***********************************************************************/

void modPurchase()
{
 XPRBexpr lobj, *lr, lc;
 int s,b;
 XPRBvar *x,**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];
 for(s=0;s<NS;s++)
 {
  lam[s] = new XPRBvar[NB2];
  for(b=0;b<NB2;b++)
   lam[s][b] = p.newVar(XPRBnewname("lam_%d",s+1));
 }                          /* Weights at breakpoint b for supplier s */

/****OBJECTIVE****/
 for(s=0;s<NS;s++)          /* Minimize the sum of costs*weights */
  for(b=0;b<NB2;b++)  lobj += C[s][b]*lam[s][b];
 p.setObj(p.newCtr("OBJ",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++)
 {
  for(b=0;b<NB2;b++)  lr[s] += X[s][b]*lam[s][b];
  p.newCtr("DefX", lr[s] == x[s]);
 }

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

    /* The minimum quantity that must be bought */
 lc=0;
 for(s=0;s<NS;s++) lc += x[s];
 p.newCtr("MustBuy", lc >= 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] += lam[s][b];
  p.newSos("SetLam", XPRB_S2, lr[s]);
 } 
   
/****SOLVING + OUTPUT****/
 p.exportProb(XPRB_MPS,"purc");    /* Output to MPS file */
 p.setSense(XPRB_MINIM);           /* Choose the sense of the optimization */
 p.mipOptimize("");                /* Solve the MIP-problem */

 cout << "Objective: " << p.getObjVal() << endl;  /* Get objective value */
    
 for(s=0;s<NS;s++)                 /* Print out the solution values */
  cout << x[s].getName() << ":" << x[s].getSol() << " ";  
 cout << endl;
 for(s=0;s<NS;s++)      
  for(b=0;b<NB2;b++)
   cout << lam[s][b].getName() << ":" << lam[s][b].getSol() << " ";
 cout << endl;
 
 delete [] BR;
 delete [] UC;
 delete [] lr;
 for(s=0;s<NS;s++) delete [] lam[s];
 delete [] lam;
 delete [] x;
}

/***********************************************************************/

    /**** Read data from files ****/
void readData()
{
 FILE *datafile;
 int s,b;  
 double val1,val2;
 
        /* Read the parameter file */
 datafile=fopen(PARAMSFILE,"r");
 XPRBreadlinecb(XPRB_FGETS, datafile, 200, "i", &NS);
 XPRBreadlinecb(XPRB_FGETS, datafile, 200, "i", &NB);
 fclose(datafile);
 NB2 = 2*NB;

        /* Now define the tables that we will use, using the sizes we 
           have just read. */
 UC= new double*[NS];
 for(s=0;s<NS;s++) UC[s]=new double[NB];

 BR = new double*[NS];
 for(s=0;s<NS;s++) BR[s]=new double[NB];

 X=new double*[NS];
 for(s=0;s<NS;s++) X[s]=new double[NB2];

 C=new double*[NS];
 for(s=0;s<NS;s++) C[s]=new double[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=fopen(PRICEFILE,"r");
 while(XPRBreadlinecb(XPRB_FGETS, datafile, 200, "i,i,g,g", &s, &b, 
       &val1, &val2)==4)
 {
  UC[s-1][b-1]=val1;
  BR[s-1][b-1]=val2;
 }
 fclose(datafile);

        /* Read the percentages data file */
 datafile=fopen(MAXPERCFILE,"r");
 XPRBreadarrlinecb(XPRB_FGETS, datafile, 200, "g,", MAXPERC, NS);
 fclose(datafile); 
 
        /* Read the required amount data file */
 datafile=fopen(REQFILE,"r");
 XPRBreadlinecb(XPRB_FGETS, datafile, 200, "g", &REQ);
 fclose(datafile); 

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

/***********************************************************************/

int main(int argc, char **argv)
{
 readData();            /* Data input from file */
 modPurchase();         /* Formulate and solve the problem */
 
 return 0;
} 

Back to examples browserPrevious exampleNext example