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.cs

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

  file xbpurch.cs
  ```````````````
  Purchasing problem using SOS-2.

  (c) 2008 Fair Isaac Corporation
      authors: S.Heipcke, D.Brett.
********************************************************/

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

using System;
using System.Text;
using System.IO;
using BCL;


namespace Examples
{
    public class TestProduction
    {
    
        //Define XPRBDATAPATH to whatever folder you wish.
        const string XPRBDATAPATH = "../../data";
        string PARAMSFILE = XPRBDATAPATH + "/purchase/params.dat";
        string MAXPERCFILE = XPRBDATAPATH + "/purchase/maxperc.dat";
        string REQFILE = XPRBDATAPATH + "/purchase/required.dat";
        string 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 */

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

        public static void Main()
        {
            System.Console.WriteLine("Started Production Test.\n");
            XPRB.init();

            TestProduction InitClassInstance = new TestProduction();

            /* Data input from file */
            InitClassInstance.readData();            
            
            /* Formulate and solve the problem */
            InitClassInstance.modPurchase();         
             
            return;
        } 
 
        /*********************************************************************/

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

        /****OBJECTIVE****/
         //Init lobj
         lobj = new XPRBexpr();
         
         /* Minimize the sum of costs*weights */
         for(s=0;s<NS;s++)          
          for(b=0;b<NB2;b++)  lobj += C[s,b]*lam[s,b];
         
         /* Set objective function */ 
         p.setObj(p.newCtr("OBJ", lobj));   

         /****CONSTRAINTS****/  
         /* Define x, also order the lam variables by breakpoint quantities */
         lr = new XPRBexpr[NS];
         for(s=0;s<NS;s++)
         {
            lr[s] = new XPRBexpr(0);
            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 = new XPRBexpr();
          for (b = 0; b < NB2; b++) lc += lam[s, b];
          p.newCtr("Conv", lc == 1);
         }

         /* The minimum quantity that must be bought */
         lc = new XPRBexpr();
         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", BCLconstant.XPRB_S2, lr[s]);
         } 
           
        /****SOLVING + OUTPUT****/
         /* Output to MPS file */
         p.exportProb(BCLconstant.XPRB_MPS,"TestResult.matrix");    
         
         /* Choose the sense of the optimization */
         p.setSense(BCLconstant.XPRB_MINIM);           
         
         /* Solve the MIP-problem */
         p.mipOptimize();                     

         /* Get objective value */
         System.Console.WriteLine("Objective: " + p.getObjVal() + "\n");  
            
         /* Print out the solution values */
         for(s=0;s<NS;s++)                 
            System.Console.Write(x[s].getName() + ":" + x[s].getSol() + " ");  
         System.Console.WriteLine("\n");
         for(s=0;s<NS;s++)      
            for(b=0;b<NB2;b++)
               System.Console.Write(lam[s,b].getName() + ":" + 
                               lam[s,b].getSol() + " ");
         System.Console.WriteLine("\n");
 
        }

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

        /**** Read data from files ****
         * Need to do this via StreamReader as per XPRBreadline C# method
         ******************************/
        public void readData()
        {

         //public int XPRBreadline(StreamReader fileStreamIn, int maxlen,
         //			   string format, out object[] output)
         FileStream file = new FileStream(PARAMSFILE, FileMode.Open, 
                           FileAccess.Read);
         StreamReader fileStreamIn = new StreamReader(file);
         
         int s,b;  
         
         /* Read the parameter file */
         //Part of XPRBprob: public int XPRBreadline(StreamReader fileStreamIn,
         //int maxlen, string format, out object[] output)
         object[] objRead;
         
         p.XPRBreadline(fileStreamIn, 200, "{i}", out objRead);
         NS = (int)objRead[0];
         p.XPRBreadline(fileStreamIn, 200, "{i}", out objRead);
         NB = (int)objRead[0];
         
         fileStreamIn.Close();
         file.Close();
         
         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;
            }

         file = new FileStream(PRICEFILE, FileMode.Open, FileAccess.Read);
         fileStreamIn = new StreamReader(file);
         while (p.XPRBreadline(fileStreamIn, 200, "{i}, {i}, {g}, {g}", 
                                 out objRead)==4)
         {
             s = (int)objRead[0];
             b = (int)objRead[1];
             UC[s - 1, b - 1] = (double)objRead[2];
             BR[s - 1, b - 1] = (double)objRead[3];
         }
         fileStreamIn.Close();
         file.Close();


                /* Read the percentages data file */
         file = new FileStream(MAXPERCFILE, FileMode.Open, FileAccess.Read);
         fileStreamIn = new StreamReader(file);
         p.XPRBreadarrline(fileStreamIn, 200, "{g}, ", out MAXPERC, NS);
         fileStreamIn.Close();
         file.Close();
         
                /* Read the required amount data file */
         file = new FileStream(REQFILE, FileMode.Open, FileAccess.Read);
         fileStreamIn = new StreamReader(file);
         p.XPRBreadline(fileStreamIn, 200, "{g}", out objRead);
         REQ = (double)objRead[0];
         fileStreamIn.Close();
         file.Close();

     /* We now pick out the data from the tables into which they have
	   been read. */
         for(s=0;s<NS;s++) 
         {
            /* First total cost and (new) breakpoint are (0,0) */
            C[s,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 */
            }
         }
        }

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

    }

}
Back to examples browserPrevious exampleNext example