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


Source Files

Data Files





xbpurch.c

/********************************************************
  BCL Example Problems
  ====================

  file xbpurch.c
  ``````````````
  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 <stdio.h>
#include <stdlib.h>
#include "xprb.h"

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

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

void modpurchase(XPRBprob prob)
{
 XPRBctr *refrow, cobj,ctr;
 int s,b;
 XPRBvar *x,**lam;
 XPRBsos sos2;

/****VARIABLES****/
 x=(XPRBvar *)malloc(NS*sizeof(XPRBvar));
 for(s=0;s<NS;s++)
  x[s]=XPRBnewvar(prob,XPRB_PL, "x", 0, XPRB_INFINITY);
                         /* Quantity to purchase from supplier s */

 lam=(XPRBvar **)malloc(NS*sizeof(XPRBvar *));
 for(s=0;s<NS;s++)
 {
  lam[s]=(XPRBvar *)malloc(NB2*sizeof(XPRBvar));
  for(b=0;b<NB2;b++)
   lam[s][b]=XPRBnewvar(prob,XPRB_PL, XPRBnewname("lam_%d",s+1), 0, XPRB_INFINITY);
 }                       /* Weights at breakpoint b for supplier s */

/****OBJECTIVE****/
    /* Objective: minimize the sum of costs*weights */
 cobj = XPRBnewctr(prob,"OBJ",XPRB_N);
 for(s=0;s<NS;s++)
  for(b=0;b<NB2;b++)
   XPRBaddterm(cobj, lam[s][b], C[s][b]);
 XPRBsetobj(prob,cobj);       /* Select objective function */

/****CONSTRAINTS****/
    /* Define x and also order the lam variables by breakpoint quantities */
 refrow=(XPRBctr *)malloc(NS*sizeof(XPRBctr));
 for(s=0;s<NS;s++)
 {
  refrow[s]=XPRBnewctr(prob,"DefX", XPRB_E);
  for(b=0;b<NB2;b++)
   XPRBaddterm(refrow[s], lam[s][b], X[s][b]);
  XPRBaddterm(refrow[s], x[s], -1);
 }

    /* The convexity row (lam sum to 1) */
 for(s=0;s<NS;s++)
 {
  ctr=XPRBnewctr(prob,"Conv", XPRB_E);
  for(b=0;b<NB2;b++)
   XPRBaddterm(ctr, lam[s][b], 1);
  XPRBaddterm(ctr, NULL, 1);
 }

    /* The minimum quantity that must be bought */
 ctr=XPRBnewctr(prob,"MustBuy", XPRB_G);
 for(s=0;s<NS;s++)
  XPRBaddterm(ctr, x[s], 1);
 XPRBaddterm(ctr, NULL, REQ);

/****BOUNDS****/
    /* No more than the maximum percentage from each supplier */
 for(s=0;s<NS;s++) XPRBsetub(x[s], 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. */
 for(s=0;s<NS;s++)
 {
  sos2=XPRBnewsos(prob,"SetLam",XPRB_S2);
  for(b=0;b<NB2;b++)
   XPRBaddsosel(sos2,lam[s][b],X[s][b]+1); /* Add 1 to all SOS coefficients
                                              because BCL does not accept 0 */
 }

/****SOLVING + OUTPUT****/
 XPRBexportprob(prob,XPRB_MPS,"purc");  /* Write out an MPS file */

 XPRBsetsense(prob,XPRB_MINIM);         /* Choose the sense of optimization */
 XPRBmipoptimize(prob,"");              /* Solve the MIP-problem */

 printf("Objective: %g\n", XPRBgetobjval(prob));  /* Get objective value */

 for(s=0;s<NS;s++)                      /* Print out the solution values */
  printf("%s:%g ", XPRBgetvarname(x[s]), XPRBgetsol(x[s]));
 for(s=0;s<NS;s++)
  for(b=0;b<NB2;b++)
   printf("%s:%g ", XPRBgetvarname(lam[s][b]), XPRBgetsol(lam[s][b]));
 printf("\n");
}

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

    /**** Read data from files ****/
void readdata(void)
{
 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=(double **)malloc(NS*sizeof(double *));
 for(s=0;s<NS;s++) UC[s]=(double *)malloc(NB*sizeof(double));

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

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

 C=(double **)malloc(NS*sizeof(double *));
 for(s=0;s<NS;s++) C[s]=(double *)malloc(NB2*sizeof(double));

 DELTA=(double *)malloc(NB2*sizeof(double));
 MAXPERC=(double *)malloc(NS*sizeof(double));

        /* 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)
{
 XPRBprob prob;

 prob=XPRBnewprob("Purchase");     /* Initialize a new problem in BCL */
 readdata();                       /* Data input from file */
 modpurchase(prob);                /* Formulate and solve the problem */

 return 0;
}

Back to examples browserPrevious exampleNext example