/********************************************************
BCL Example Problems
====================
file xbburg.c
`````````````
Burglar problem, binary variable formulation.
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, Jan. 2000, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include "xprb.h"
#define NItems 8 /* Number of items */
/****DATA****/
/* Item: 1 2 3 4 5 6 7 8 */
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 */
int main(int argc, char **argv)
{
XPRBvar x[NItems];
XPRBctr cobj,ctr;
int i;
XPRBprob prob;
prob=XPRBnewprob("Burglar"); /* Initialize a new problem in BCL */
/****VARIABLES****/
/* 1 if we take item i; 0 otherwise */
for(i=0;i<NItems;i++) x[i]=XPRBnewvar(prob,XPRB_BV, "x", 0, 1);
/****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);
/****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++) /* Print out the solution values */
printf("%s:%g ", XPRBgetvarname(x[i]), XPRBgetsol(x[i]));
printf("\n");
return 0;
}
|
/********************************************************
BCL Example Problems
====================
file xbburgi.c
``````````````
Burglar problem.
Binary variable formulation with index sets.
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, Jan. 2000, 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;
XPRBprob prob;
prob=XPRBnewprob("Burglari"); /* 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);
/****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;
}
|
/********************************************************
BCL Example Problems
====================
file xbburgl.c
``````````````
Burglar problem.
Binary variable formulation with index sets.
-- Formulating logical conditions
with indicator constraints --
(c) 2009 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;
}
|
