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

Data Files

xbpurch.c

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

file xbpurch.c
``````````````
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++)
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++)
}

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

/* The minimum quantity that must be bought */
for(s=0;s<NS;s++)

/****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++)
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 ****/
{
FILE *datafile;
int s,b;
double val1,val2;

/* Read the parameter file */
datafile=fopen(PARAMSFILE,"r");
fclose(datafile);
NB2 = 2*NB;

/* Now define the tables that we will use, using the sizes we
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");
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");
fclose(datafile);

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

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

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;
}

```