| |||||||||||||||||||||
Burglar - Use of index sets, formulating logical constraints Description Several versions of a simple knapsack problem:
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
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-2024 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; } } } | |||||||||||||||||||||
© Copyright 2023 Fair Isaac Corporation. |