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

Burglar - Use of index sets, formulating logical constraints

Description
Several versions of a simple knapsack problem:
  • xbburg: standard formlation
  • xbburgi: shows how to index an array of variables by an index set
  • xbburgl: adds several indicator constraints to state logical conditions
Further explanation of this example: Quick reference guide 'MIP formulations and linearizations', Section 4 Indicator constraints


Source Files





xbburgl.cs

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

  file xbcatena.cs
  ````````````````
  QCQP test problem
  Based on AMPL model catenary.mod
  (Source: http://www.orfe.princeton.edu/~rvdb/ampl/nlmodels/ )
 
  This model finds the shape of a hanging chain.
  The solution is known to be y = cosh(a*x) + b
  for appropriate a and b.
   
  (c) 2008 Fair Isaac Corporation
      authors: S.Heipcke, D.Brett, June 2008
****************************************************************/

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


namespace Examples
{

    public class TestBBurgl
    {
        double[] VALUE  = {15,100, 90, 60, 40, 15, 10,  1}; // Value of items
        double[] WEIGHT = { 2, 20, 20, 30, 40, 30, 60, 10}; // Weight of items
        const double WTMAX    = 102;           // Max weight allowed for haul

        string[] ITEMNAMES = {"camera", "necklace", "vase", "picture", "tv", "video", 
            "chest", "brick"};
            
        int NItems;                      // Number of items

        public static void Main()
        {
            XPRB.init();
            XPRBvar[] x;     
            XPRBindexSet ITEMS;             /* Set of items */
            int i;
            XPRBexpr lobj, kn;  
            XPRBctr Log3a,Log3b;
            XPRBprob p = new XPRBprob("BurglarL");         /* Initialize a new problem in BCL */

            TestBBurgl TestInstance = new TestBBurgl();

            /****INDICES****/
            ITEMS = p.newIndexSet("Items",8);   /* Create the index set */
            for (i = 0; i < 8; i++) 
                ITEMS.addElement(TestInstance.ITEMNAMES[i]);

            TestInstance.NItems = ITEMS.getSize();         /* Get the size of the index set */

            /****VARIABLES****/
            x = new XPRBvar[TestInstance.NItems];
            for (i = 0; i < TestInstance.NItems; i++)
                x[i] = p.newVar(("x_"+ITEMS.getIndexName(i)), BCLconstant.XPRB_BV);    
                                         /* 1 if we take item i; 0 otherwise */

            /****OBJECTIVE****/
            lobj = new XPRBexpr();
            for (i = 0; i < TestInstance.NItems; i++) lobj += TestInstance.VALUE[i] * x[i]; 
            p.setObj(p.newCtr("OBJ",lobj)); /* Set objective: maximize total value */ 

            /****CONSTRAINTS****/
            kn = new XPRBexpr();
            for (i = 0; i < TestInstance.NItems; i++) kn += TestInstance.WEIGHT[i] * x[i];  
            p.newCtr("WtMax", kn <= WTMAX); /* Weight restriction */

            /** Logic constraint:
            ** Either take "vase" and "picture" or "tv" and "video" (but not both pairs). */

            /* Values within each pair are the same */
            p.newCtr("Log1", x[ITEMS.getIndex("vase")] == x[ITEMS.getIndex("picture")]);
            p.newCtr("Log2", x[ITEMS.getIndex("tv")] == x[ITEMS.getIndex("video")]);

            /* Choose exactly one pair */
            Log3a = p.newCtr("Log3a", x[ITEMS.getIndex("tv")] + x[ITEMS.getIndex("video")] <= 0);
            Log3b = p.newCtr("Log3b", x[ITEMS.getIndex("tv")] + x[ITEMS.getIndex("video")] >= 2);

            /* Turn the 2 constraints into indicator constraints */
            Log3a.setIndicator(1, ref x[ITEMS.getIndex("vase")]);
                                           // x["vase"]=1 -> x["tv"]+x["video"]=0
            Log3b.setIndicator(-1, ref x[ITEMS.getIndex("vase")]);
                                           // x["vase"]=0 -> x["tv"]+x["video"]=2

            /* Alternative MIP formulation (instead of Log3a and Log3b) */
            // p.newCtr("Log3", x[ITEMS["tv"]] = 1 - x[ITEMS["vase"]]);


            /****SOLVING + OUTPUT****/
            p.setSense(BCLconstant.XPRB_MAXIM);         /* Choose the sense of the optimization */
            p.mipOptimize();                   /* Solve the MIP-problem*/
            System.Console.WriteLine("Objective: " + p.getObjVal());  /* Get objective value */

            for (i = 0; i < TestInstance.NItems; i++)           /* Print out the chosen items */
            if(x[i].getSol()>0)
                System.Console.WriteLine(ITEMS.getIndexName(i) + ": " + x[i].getSol());  

            return;
        }

    }
}

Back to examples browserPrevious exampleNext example