| |||||||||||||||
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.c /******************************************************** BCL Example Problems ==================== file xbburgl.c `````````````` Burglar problem. Binary variable formulation with index sets. -- Formulating logical conditions with indicator constraints -- (c) 2009-2024 Fair Isaac Corporation author: S.Heipcke, June 2009, rev. Mar. 2011 ********************************************************/ #include <stdio.h> #include <stdlib.h> #include "xprb.h" /****DATA****/ /* Item: ca ne va pi tv vi ch br */ 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 */ double WTMAX = 102; /* Max weight allowed for haul */ char *ITEMNAMES[] = {"camera", "necklace", "vase", "picture", "tv", "video", "chest", "brick"}; int NItems; /* Number of items */ int main(int argc, char **argv) { XPRBvar *x; XPRBidxset ITEMS; /* Set of items */ int i; XPRBctr ctr,cobj,Log3a,Log3b; XPRBprob prob; prob=XPRBnewprob("BurglarL"); /* Initialize a new problem in BCL */ /****INDICES****/ ITEMS=XPRBnewidxset(prob,"Items",8); /* Create the index set */ for(i=0;i<8;i++) XPRBaddidxel(ITEMS, ITEMNAMES[i]); NItems=XPRBgetidxsetsize(ITEMS); /* Get the size of the index set */ /****VARIABLES****/ x = (XPRBvar *)malloc(NItems*sizeof(XPRBvar)); for(i=0;i<NItems;i++) x[i]=XPRBnewvar(prob,XPRB_BV, XPRBnewname("x_%s",XPRBgetidxelname(ITEMS,i)), 0, 1); /* 1 if we take item i; 0 otherwise */ /****OBJECTIVE****/ cobj = XPRBnewctr(prob,"OBJ",XPRB_N); /* Maximize the total value */ for(i=0;i<NItems;i++) XPRBaddterm(cobj, x[i], VALUE[i]); XPRBsetobj(prob,cobj); /* Select objective function */ /****CONSTRAINTS****/ ctr=XPRBnewctr(prob,"WtMax", XPRB_L); /* Weight restriction */ for(i=0;i<NItems;i++) XPRBaddterm(ctr, x[i], WEIGHT[i]); XPRBaddterm(ctr, NULL, WTMAX); /** Logic constraint: ** Either take "vase" and "picture" or "tv" and "video" (but not both pairs). */ /* Values within each pair are the same */ ctr = XPRBnewctr(prob, "Log1", XPRB_E); /* x["vase"] == x["picture"] */ XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"vase")], 1); XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"picture")], -1); ctr = XPRBnewctr(prob, "Log2", XPRB_E); /* x["tv"] == x["video"] */ XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"tv")], 1); XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"video")], -1); /* Choose exactly one pair */ Log3a = XPRBnewctr(prob, "Log3a", XPRB_L); /* x["tv"]+x["video"] <= 0 */ XPRBaddterm(Log3a, x[XPRBgetidxel(ITEMS,"tv")], 1); XPRBaddterm(Log3a, x[XPRBgetidxel(ITEMS,"video")], 1); Log3b = XPRBnewctr(prob, "Log3b", XPRB_G); /* x["tv"]+x["video"] >= 2 */ XPRBaddterm(Log3b, x[XPRBgetidxel(ITEMS,"tv")], 1); XPRBaddterm(Log3b, x[XPRBgetidxel(ITEMS,"video")], 1); XPRBaddterm(Log3b, NULL, 2); /* Turn the 2 constraints into indicator constraints */ XPRBsetindicator(Log3a, 1, x[XPRBgetidxel(ITEMS,"vase")]); /* x["vase"]=1 -> x["tv"]+x["video"]=0 */ XPRBsetindicator(Log3b, -1, x[XPRBgetidxel(ITEMS,"vase")]); /* x["vase"]=0 -> x["tv"]+x["video"]=2 */ /* Alternative MIP formulation (instead of Log3a and Log3b) */ /* ctr = XPRBnewctr(prob, "Log3", XPRB_E); // x["tv"] = 1 - x["vase"] XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"tv")], 1); XPRBaddterm(ctr, x[XPRBgetidxel(ITEMS,"vase")], 1); XPRBaddterm(ctr, NULL, 1); */ /****SOLVING + OUTPUT****/ XPRBsetsense(prob,XPRB_MAXIM); /* Choose the sense of optimization */ XPRBmipoptimize(prob,""); /* Solve the MIP-problem */ printf("Objective: %g\n",XPRBgetobjval(prob)); /* Get objective value */ for(i=0;i<NItems;i++) if(XPRBgetsol(x[i])>0) printf("%s : %g\n", XPRBgetidxelname(ITEMS, i), XPRBgetsol(x[i])); /* Print out the chosen items */ return 0; } | |||||||||||||||
© Copyright 2023 Fair Isaac Corporation. |