Delivery - Data input from file; infeasibility analysis
|
|
|
| Type: | Network flow |
| Rating: | 2 (easy-medium) |
| Description: | A simple supply and demand network example showing data input from file and the use of "views": incremental definition of arrays of variables. Also uses constraint templates with the arrays of variables. A second version of this model (file xbdlvriis) has modified data making the problem infeasible. This example shows how to analyze infeasibility with the help of IIS (irreducible infeasible sets), it retrieves the IIS and prints out their contents. It is possible to retrieve more detailed information on the IIS, such as isolation rows or bounds, using Xpress Optimizer functions (file xbdlvriis2iso) or to use the infeasibility repair functionality of the Optimizer (file xbdlvriis2rep) with models defined in BCL. |
| File(s): | xbdelvr.c, xbdlvriis.c, xbdlvriis2iso.c, xbdlvriis2rep.c |
| Data file(s): | ifvan.dat, cost.dat |
|
|
|
| xbdelvr.c |
/********************************************************
BCL Example Problems
====================
file xbdelivr.c
```````````````
Transportation problem.
Use of arrays.
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, Jan. 2000, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include "xprb.h"
/* define or undefine ARRAY in order to switch between model formulations
with or without variable arrays in constraint definition */
#define ARRAY
#define NSupp 10 /* Number of suppliers */
#define NCust 7 /* Number of customers */
#define MaxArcs 100 /* Max. num. of non-zero cost values */
#define VANFILE XPRBDATAPATH "/delivery/ifvan.dat" /* Van data file */
#define COSTFILE XPRBDATAPATH "/delivery/cost.dat" /* Cost data file */
/****DATA****/
/* Supplier: London Luton B'ham Bristl Derby Stckpt York */
double SUPPLY[] = {140.0, 600.0, 50.0, 10.0, 400.0, 200.0, 20.0,
/* Supplier: Derby Soton Scnthp */
90.0, 30.0, 12.0};
/* Customer: London Livpol Doncst York Hull Manchr Shffld */
double DEMAND[] = {123.3, 56.4, 17.1, 192.8, 310.0, 47.0, 86.0};
double COST[NSupp][NCust]; /* Cost per supplier-customer pair */
double IFVAN[NSupp][NCust]; /* Non-zero if route uses vans instead
of lorries */
double VANCAP=40.0; /* Capacity on routes that use vans */
/***********************************************************************/
void moddelivery(XPRBprob prob)
{
XPRBctr ctr;
int s,c;
XPRBvar x[NSupp][NCust];
/****VARIABLES****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
x[s][c]=XPRBnewvar(prob,XPRB_PL,XPRBnewname("x_s%d",s), 0, XPRB_INFINITY);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
for(s=0;s<NSupp;s++) /* Objective: Minimize total cost */
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], COST[s][c]);
XPRBsetobj(prob,ctr); /* Set objective function */
/****CONSTRAINTS****/
for(c=0; c<NCust; c++) /* Satisfy demand of each customer */
{
ctr = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=0;s<NSupp;s++) XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, DEMAND[c]);
}
for(s=0;s<NSupp;s++) /* Keep within supply at each supplier*/
{
ctr = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, SUPPLY[s]);
}
/****BOUNDS****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) XPRBsetub(x[s][c], VANCAP);
/****SOLVING + OUTPUT****/
XPRBexportprob(prob,XPRB_MPS,"delivery"); /* Write out an MPS file */
XPRBsetsense(prob, XPRB_MINIM); /* Set objective sense to minimization */
XPRBlpoptimize(prob, ""); /* Solve the LP-problem */
printf("Objective: %g\n", XPRBgetobjval(prob)); /* Get objective value */
for(s=0;s<NSupp;s++) /* Print out the solution values */
for(c=0; c<NCust; c++)
printf("%s:%g ", XPRBgetvarname(x[s][c]), XPRBgetsol(x[s][c]));
printf("\n");
}
/***********************************************************************/
/**** Array-based constraint formulation ****/
void moddelivery_array(XPRBprob prob)
{
int s,c;
XPRBvar x[NSupp][NCust];
XPRBarrvar va;
XPRBctr ctr;
/****VARIABLES****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
x[s][c]=XPRBnewvar(prob,XPRB_PL,XPRBnewname("x_s%d",s), 0, XPRB_INFINITY);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
for(s=0;s<NSupp;s++) /* Objective: Minimize total cost */
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], COST[s][c]);
XPRBsetobj(prob,ctr); /* Select objective function */
/****CONSTRAINTS****/
for(c=0; c<NCust; c++) /* Satisfy demand of each customer */
{
va = XPRBstartarrvar(prob,NSupp,"arr"); /* Define an array of size NSupp */
for(s=0;s<NSupp;s++)
XPRBapparrvarel(va, x[s][c]); /* Add a variable to the array */
XPRBendarrvar(va); /* Terminate definition of the array */
XPRBnewsum(prob,"Demand", va, XPRB_G, DEMAND[c]);
}
for(s=0;s<NSupp;s++) /* Keep within supply at each supplier */
{
ctr = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, SUPPLY[s]);
}
/****BOUNDS****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) XPRBsetub(x[s][c], VANCAP);
/****SOLVING + OUTPUT****/
XPRBexportprob(prob,XPRB_MPS,"delivery"); /* Write out an MPS file */
XPRBsetsense(prob,XPRB_MINIM); /* Set objective sense to minimization */
XPRBsolve(prob,""); /* Solve the LP-problem */
printf("Objective: %g\n", XPRBgetobjval(prob)); /* Get objective value */
for(s=0;s<NSupp;s++) /* Print out the solution values */
for(c=0; c<NCust; c++)
printf("%s:%g ", XPRBgetvarname(x[s][c]), XPRBgetsol(x[s][c]));
printf("\n");
}
/***********************************************************************/
/**** Read data from files ****/
void readdata(void)
{
FILE *datafile;
int s,c;
/* Initialize data tables to 0: in the van data file some entries that are
* zero are simply left out, but the function XPRBreadarrline only initializes
* those elements to 0 that have been read, e.g. a data line ",,," results
* in the first 4 elements of the array to be set to zero, even if the
* maximum number of elements to be read (=last parameter of XPRBreadarrline)
* has a much larger value */
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
{
COST[s][c] = 0;
IFVAN[s][c] = 0;
}
/* Read the demand data file */
datafile=fopen(COSTFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", COST[s], NCust);
fclose(datafile);
/* Read the van data file */
datafile=fopen(VANFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", IFVAN[s], NCust);
fclose(datafile);
}
/***********************************************************************/
int main(int argc, char **argv)
{
XPRBprob prob;
prob=XPRBnewprob("Delivery"); /* Initialize a new problem in BCL */
readdata(); /* Data input from file */
#ifdef ARRAY
moddelivery_array(prob); /* Constraint formulation using arrays */
#else
moddelivery(prob); /* Straight-forward problem formulation */
#endif
return 0;
}
|
| xbdlvriis.c |
/********************************************************
BCL Example Problems
====================
file xbdlvriis.c
````````````````
Transportation problem (infeasible data).
Retrieving and printing IIS.
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, 2005, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "xprb.h"
#define NSupp 10 /* Number of suppliers */
#define NCust 7 /* Number of customers */
#define MaxArcs 100 /* Max. num. of non-zero cost values */
#define VANFILE XPRBDATAPATH "/delivery/ifvan.dat" /* Van data file */
#define COSTFILE XPRBDATAPATH "/delivery/cost.dat" /* Cost data file */
/****DATA****/
/* Supplier: London Luton B'ham Bristl Derby Stckpt York */
double SUPPLY[] = {140.0, 200.0, 50.0, 10.0, 400.0, 200.0, 20.0,
/* Supplier: Derby Soton Scnthp */
90.0, 30.0, 12.0};
/* Customer: London Livpol Doncst York Hull Manchr Shffld */
double DEMAND[] = {1230.3, 560.4, 117.1, 592.8, 310.0, 1247.0, 86.0};
double COST[NSupp][NCust]; /* Cost per supplier-customer pair */
double IFVAN[NSupp][NCust]; /* Non-zero if route uses vans instead
of lorries */
double VANCAP=40.0; /* Capacity on routes that use vans */
/***********************************************************************/
void moddelivery(XPRBprob prob)
{
XPRBctr ctr;
int s,c,i;
XPRBvar x[NSupp][NCust];
XPRBctr *iisctr;
XPRBvar *iisvar;
int numv, numc, numiis, ct;
/****VARIABLES****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
x[s][c]=XPRBnewvar(prob,XPRB_PL,XPRBnewname("x_s%d",s), 0, XPRB_INFINITY);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
for(s=0;s<NSupp;s++) /* Objective: Minimize total cost */
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], COST[s][c]);
XPRBsetobj(prob,ctr); /* Set objective function */
/****CONSTRAINTS****/
for(c=0; c<4; c++) /* Satisfy demand of each customer */
{
ctr = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=0;s<5;s++) XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, DEMAND[c]);
}
for(c=4; c<NCust; c++) /* Satisfy demand of each customer */
{
ctr = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=5;s<NSupp;s++) XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, DEMAND[c]);
}
for(s=0;s<5;s++) /* Keep within supply at each supplier*/
{
ctr = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=0; c<4; c++)
XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, SUPPLY[s]);
}
for(s=5;s<NSupp;s++) /* Keep within supply at each supplier*/
{
ctr = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=4; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], 1);
XPRBaddterm(ctr, NULL, SUPPLY[s]);
}
/****BOUNDS****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) XPRBsetub(x[s][c], VANCAP);
/****SOLVING + OUTPUT****/
XPRBsetsense(prob,XPRB_MINIM); /* Set objective sense to minimization */
XPRBlpoptimize(prob,""); /* Solve the LP-problem */
printf("LP status: %d\n", XPRBgetlpstat(prob));
if (XPRBgetlpstat(prob)==XPRB_LP_OPTIMAL)
{
printf("Objective: %g\n",XPRBgetobjval(prob)); /* Get objective value */
}
else if (XPRBgetlpstat(prob)==XPRB_LP_INFEAS) /* Get the IIS */
{
numiis=XPRBgetnumiis(prob); /* Get the number of independent IIS */
printf("Number of IIS: %d\n", numiis);
for(s=1;s<=numiis;s++)
{
XPRBgetiis(prob, &iisvar, &numv, &iisctr, &numc, s);
printf("IIS %d: %d variables, %d constraints\n", s, numv, numc);
if (numv>0)
{ /* Print all variables in the IIS */
printf(" Variables: ");
for(i=0;i<numv;i++) printf("%s ", XPRBgetvarname(iisvar[i]));
printf("\n");
XPRBfreemem(iisvar); /* Free the array of variables */
}
if (numc>0)
{ /* Print all constraints in the IIS */
printf(" Constraints: ");
for(i=0;i<numc;i++) printf("%s ", XPRBgetctrname(iisctr[i]));
printf("\n");
XPRBfreemem(iisctr); /* Free the array of constraints */
}
}
/* Alternative way of enumerating IIS: */
XPRBgetiis(prob, NULL, &numv, NULL, &numc, 0);
printf("IIS approximation: %d variables, %d constraints with non-zero reduced cost/dual values\n", numv, numc);
ct=0;
while(numv+numc>0)
{
if(ct>0)
printf("IIS %d: %d variables, %d constraints\n", ct, numv, numc);
ct++;
XPRBgetiis(prob, NULL, &numv, NULL, &numc, ct);
}
/* Retrieve variables only */
for(s=1;s<=numiis;s++)
{
XPRBgetiis(prob, &iisvar, &numv, NULL, NULL, s);
printf("IIS %d: %d variables ( ", s, numv);
if (numv>0)
{
for(i=0;i<numv;i++) printf("%s ", XPRBgetvarname(iisvar[i]));
XPRBfreemem(iisvar); /* Free the array of variables */
}
printf(")\n");
}
/* Retrieve constraints only */
for(s=1;s<=numiis;s++)
{
XPRBgetiis(prob, NULL, NULL, &iisctr, &numc, s);
printf("IIS %d: %d constraints ( ", s, numc);
if (numc>0)
{
for(i=0;i<numc;i++) printf("%s ", XPRBgetctrname(iisctr[i]));
XPRBfreemem(iisctr); /* Free the array of constraints */
}
printf(")\n");
}
}
}
/***********************************************************************/
/**** Read data from files ****/
void readdata(void)
{
FILE *datafile;
int s,c;
/* Initialize data tables to 0 */
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
{
COST[s][c] = 0;
IFVAN[s][c] = 0;
}
/* Read the demand data file */
datafile=fopen(COSTFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", COST[s], NCust);
fclose(datafile);
/* Read the van data file */
datafile=fopen(VANFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", IFVAN[s], NCust);
fclose(datafile);
}
/***********************************************************************/
int main(int argc, char **argv)
{
XPRBprob prob;
prob=XPRBnewprob("Delivery"); /* Initialize a new problem in BCL */
readdata(); /* Data input from file */
moddelivery(prob); /* Problem formulation & solving */
return 0;
}
|
| xbdlvriis2iso.c |
/********************************************************
BCL Example Problems
====================
file xbdlvriis2iso.c
````````````````````
Transportation problem (infeasible data).
Retrieving and printing IIS.
- Using Optimizer functions to retrieve detailed
IIS information including isolation rows/bounds -
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, Jan. 2008, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "xprb.h"
#include "xprs.h"
#define NSupp 10 /* Number of suppliers */
#define NCust 7 /* Number of customers */
#define MaxArcs 100 /* Max. num. of non-zero cost values */
#define VANFILE XPRBDATAPATH "/delivery/ifvan.dat" /* Van data file */
#define COSTFILE XPRBDATAPATH "/delivery/cost.dat" /* Cost data file */
/****DATA****/
/* Supplier: London Luton B'ham Bristl Derby Stckpt York */
double SUPPLY[] = {140.0, 200.0, 50.0, 10.0, 400.0, 200.0, 20.0,
/* Supplier: Derby Soton Scnthp */
90.0, 30.0, 12.0};
/* Customer: London Livpol Doncst York Hull Manchr Shffld */
double DEMAND[] = {1230.3, 560.4, 117.1, 592.8, 310.0, 1247.0, 86.0};
double COST[NSupp][NCust]; /* Cost per supplier-customer pair */
double IFVAN[NSupp][NCust]; /* Non-zero if route uses vans instead
of lorries */
double VANCAP=40.0; /* Capacity on routes that use vans */
/***********************************************************************/
void moddelivery(XPRBprob prob)
{
XPRBctr ctr, CSupply[NSupp], CDemand[NCust];
int s,c,i;
XPRBvar x[NSupp][NCust];
int numv, numc, numiis, len, ncol, nrow, namelength;
double bnd, rhs;
char *vnames, *cnames;
int *viis,*ciis;
char **vindex,**cindex;
char *ctrtype = NULL;
char *bndtype = NULL;
double *duals = NULL;
double *rdcs = NULL;
char *isolationrows = NULL;
char *isolationbnds = NULL;
char *isotype[] = {"N/A", "No ", "Yes"};
XPRSprob op;
/****VARIABLES****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
x[s][c]=XPRBnewvar(prob,XPRB_PL,XPRBnewname("x_s%d_%d",s,c), 0, XPRB_INFINITY);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
for(s=0;s<NSupp;s++) /* Objective: Minimize total cost */
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], COST[s][c]);
XPRBsetobj(prob,ctr); /* Set objective function */
/****CONSTRAINTS****/
for(c=0; c<4; c++) /* Satisfy demand of each customer */
{
CDemand[c] = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=0;s<5;s++) XPRBaddterm(CDemand[c], x[s][c], 1);
XPRBaddterm(CDemand[c], NULL, DEMAND[c]);
}
for(c=4; c<NCust; c++) /* Satisfy demand of each customer */
{
CDemand[c] = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=5;s<NSupp;s++) XPRBaddterm(CDemand[c], x[s][c], 1);
XPRBaddterm(CDemand[c], NULL, DEMAND[c]);
}
for(s=0;s<5;s++) /* Keep within supply at each supplier*/
{
CSupply[s] = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=0; c<4; c++)
XPRBaddterm(CSupply[s], x[s][c], 1);
XPRBaddterm(CSupply[s], NULL, SUPPLY[s]);
}
for(s=5;s<NSupp;s++) /* Keep within supply at each supplier*/
{
CSupply[s] = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=4; c<NCust; c++)
XPRBaddterm(CSupply[s], x[s][c], 1);
XPRBaddterm(CSupply[s], NULL, SUPPLY[s]);
}
/****BOUNDS****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) XPRBsetub(x[s][c], VANCAP);
/****SOLVING + OUTPUT****/
XPRBsetsense(prob,XPRB_MINIM); /* Set objective sense to minimization */
/* XPRBexportprob(prob, XPRB_LP, "infeasible"); */
XPRBlpoptimize(prob,""); /* Solve the LP-problem */
printf("LP status: %d\n", XPRBgetlpstat(prob));
if (XPRBgetlpstat(prob)==XPRB_LP_OPTIMAL)
{
printf("Objective: %g\n", XPRBgetobjval(prob)); /* Get objective value */
}
else if (XPRBgetlpstat(prob)==XPRB_LP_INFEAS) /* Get the IIS */
{
op = XPRBgetXPRSprob(prob); /* Retrieve the Optimizer problem */
/**** Get all IIS ****/
XPRSiisall(op); /* Generate all IIS */
/* Get the number of independent IIS */
XPRSgetintattrib(op, XPRS_NUMIIS, &numiis);
/**** Obtain variable and constraint names for later use in printout ****/
/* Retrieve variable names */
XPRSgetintattrib(op, XPRS_ORIGINALCOLS, &ncol);
XPRSgetnamelist(op, 2, NULL, 0, &len, 0, ncol-1);
/* Get number of bytes required for retrieving names */
vnames = (char *)malloc(len * sizeof(char));
vindex = (char **)malloc(ncol * sizeof(char *));
XPRSgetnamelist(op, 2, vnames, len, NULL, 0, ncol-1);
vindex[0]=vnames;
for(i=1; i<ncol; i++) vindex[i] =vindex[i-1]+strlen(vindex[i-1])+1;
namelength = 0;
for(i=1; i<ncol; i++)
if (strlen(vindex[i])>namelength) namelength=strlen(vindex[i]);
/* Retrieve constraint names */
XPRSgetintattrib(op, XPRS_ORIGINALROWS, &nrow);
XPRSgetnamelist(op, 1, NULL, 0, &len, 0, nrow-1);
cnames = (char *)malloc(len * sizeof(char));
cindex = (char **)malloc(nrow * sizeof(char *));
XPRSgetnamelist(op, 1, cnames, len, NULL, 0, nrow-1);
cindex[0]=cnames;
for(i=1; i<nrow; i++) cindex[i] =cindex[i-1]+strlen(cindex[i-1])+1;
for(i=1; i<nrow; i++)
if (strlen(cindex[i])>namelength) namelength=strlen(cindex[i]);
/**** Retrieve detailed IIS info (incl. isolations) ****/
for(s=1;s<=numiis;s++)
{
XPRSgetiisdata(op, s, &numc, &numv, NULL, NULL, NULL, NULL,
NULL, NULL, NULL, NULL);
XPRSiisisolations(op, s); /* Find isolations */
ciis = (int *)malloc(numc * sizeof(int));
viis = (int *)malloc(numv * sizeof(int));
ctrtype = (char *)malloc(numc*sizeof(char));
bndtype = (char *)malloc(numv*sizeof(char));
duals = (double *)malloc(numc*sizeof(double));
rdcs = (double *)malloc(numv*sizeof(double));
isolationrows = (char *)malloc(numc*sizeof(char));
isolationbnds = (char *)malloc(numv*sizeof(char));
XPRSgetiisdata(op, s, &numc, &numv, ciis, viis, ctrtype, bndtype,
duals, rdcs, isolationrows, isolationbnds);
printf("IIS %d: %d variables, %d constraints\n", s, numv, numc);
printf(" %-*s Type Sense Bound Dual values In iso. \n", namelength, "Name");
if (numv>0)
{ /* Print all variables in the IIS */
for(i=0;i<numv;i++)
{
if (bndtype[i] == 'L') XPRSgetlb(op, &bnd, viis[i], viis[i]);
else XPRSgetub(op, &bnd, viis[i], viis[i]);
printf(" %-*s %s %c %10g %10g %s\n", namelength,
vindex[viis[i]], "column", bndtype[i], bnd, rdcs[i],
isotype[1+(int)isolationbnds[i]] );
}
free(viis); /* Free the array of variables */
free(bndtype);
free(rdcs);
free(isolationbnds);
}
if (numc>0)
{ /* Print all constraints in the IIS */
for(i=0;i<numc;i++)
{
XPRSgetrhs(op, &rhs, ciis[i], ciis[i]);
printf(" %-*s %s %c %10g %10g %s\n", namelength,
cindex[ciis[i]], "row ", ctrtype[i], rhs, duals[i],
isotype[1+(int)isolationrows[i]]);
}
free(ciis); /* Free the array of constraints */
}
}
free(vnames);
free(cnames);
free(vindex);
free(cindex);
}
}
/***********************************************************************/
/**** Read data from files ****/
void readdata(void)
{
FILE *datafile;
int s,c;
/* Initialize data tables to 0 */
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
{
COST[s][c] = 0;
IFVAN[s][c] = 0;
}
/* Read the demand data file */
datafile=fopen(COSTFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", COST[s], NCust);
fclose(datafile);
/* Read the van data file */
datafile=fopen(VANFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", IFVAN[s], NCust);
fclose(datafile);
}
/***********************************************************************/
int main(int argc, char **argv)
{
XPRBprob prob;
prob=XPRBnewprob("Delivery"); /* Initialize a new problem in BCL */
readdata(); /* Data input from file */
moddelivery(prob); /* Problem formulation & solving */
return 0;
}
|
| xbdlvriis2rep.c |
/********************************************************
BCL Example Problems
====================
file xbdlvriis2rep.c
````````````````````
Transportation problem (infeasible data).
Repairing infeasibility.
- Using Optimizer functions -
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, Jan. 2008, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "xprb.h"
#include "xprs.h"
#define NSupp 10 /* Number of suppliers */
#define NCust 7 /* Number of customers */
#define MaxArcs 100 /* Max. num. of non-zero cost values */
#define VANFILE XPRBDATAPATH "/delivery/ifvan.dat" /* Van data file */
#define COSTFILE XPRBDATAPATH "/delivery/cost.dat" /* Cost data file */
void printsolution(XPRBprob prob, int scode, XPRBvar x[][NCust]);
void printsolution2(XPRSprob op, int scode, XPRBvar x[][NCust]);
/****DATA****/
/* Supplier: London Luton B'ham Bristl Derby Stckpt York */
double SUPPLY[] = {140.0, 200.0, 50.0, 10.0, 400.0, 200.0, 20.0,
/* Supplier: Derby Soton Scnthp */
90.0, 30.0, 12.0};
/* Customer: London Livpol Doncst York Hull Manchr Shffld */
double DEMAND[] = {1230.3, 560.4, 117.1, 592.8, 310.0, 1247.0, 86.0};
double COST[NSupp][NCust]; /* Cost per supplier-customer pair */
double IFVAN[NSupp][NCust]; /* Non-zero if route uses vans instead
of lorries */
double VANCAP=40.0; /* Capacity on routes that use vans */
/***********************************************************************/
void moddelivery(XPRBprob prob)
{
XPRBctr ctr, CSupply[NSupp], CDemand[NCust];
int s,c;
XPRBvar x[NSupp][NCust];
int ncol, nrow, scode;
double *lrp, *grp, *lbp, *ubp;
XPRSprob op;
/****VARIABLES****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
x[s][c]=XPRBnewvar(prob,XPRB_PL,XPRBnewname("x_s%d_%d",s,c), 0, XPRB_INFINITY);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
for(s=0;s<NSupp;s++) /* Objective: Minimize total cost */
for(c=0; c<NCust; c++)
XPRBaddterm(ctr, x[s][c], COST[s][c]);
XPRBsetobj(prob,ctr); /* Set objective function */
/****CONSTRAINTS****/
for(c=0; c<4; c++) /* Satisfy demand of each customer */
{
CDemand[c] = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=0;s<5;s++) XPRBaddterm(CDemand[c], x[s][c], 1);
XPRBaddterm(CDemand[c], NULL, DEMAND[c]);
}
for(c=4; c<NCust; c++) /* Satisfy demand of each customer */
{
CDemand[c] = XPRBnewctr(prob,"Demand", XPRB_G);
for(s=5;s<NSupp;s++) XPRBaddterm(CDemand[c], x[s][c], 1);
XPRBaddterm(CDemand[c], NULL, DEMAND[c]);
}
for(s=0;s<5;s++) /* Keep within supply at each supplier*/
{
CSupply[s] = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=0; c<4; c++)
XPRBaddterm(CSupply[s], x[s][c], 1);
XPRBaddterm(CSupply[s], NULL, SUPPLY[s]);
}
for(s=5;s<NSupp;s++) /* Keep within supply at each supplier*/
{
CSupply[s] = XPRBnewctr(prob,"Supply",XPRB_L);
for(c=4; c<NCust; c++)
XPRBaddterm(CSupply[s], x[s][c], 1);
XPRBaddterm(CSupply[s], NULL, SUPPLY[s]);
}
/****BOUNDS****/
for(s=0;s<NSupp;s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) XPRBsetub(x[s][c], VANCAP);
/****SOLVING + OUTPUT****/
XPRBsetsense(prob,XPRB_MINIM); /* Set objective sense to minimization */
/* XPRBexportprob(prob, XPRB_LP, "infeasible"); */
XPRBlpoptimize(prob,""); /* Solve the LP-problem */
printf("LP status: %d\n", XPRBgetlpstat(prob));
if (XPRBgetlpstat(prob)==XPRB_LP_OPTIMAL)
{
printf("Objective: %g\n", XPRBgetobjval(prob)); /* Get objective value */
}
else if (XPRBgetlpstat(prob)==XPRB_LP_INFEAS)
{
op = XPRBgetXPRSprob(prob); /* Retrieve the Optimizer problem */
/**** Trying to fix infeasibilities ****/
/*
lrp: (affects = and <= rows)
ax - aux_var = b
ax - aux_var <= b
grp: (affects = and >= rows)
ax + aux_var = b
ax + aux_var >= b
lbp:
x_i + aux_var >= l
ubp:
x_i - aux_var <= u
*/
/**** Simplified infeasibility repair:
specifying preferences per constraint/bound type ****/
printf("\n**** Repair infeasibility:\n");
XPRSrepairinfeas(op, &scode, 'c', 'o', ' ', 10, 9, 0, 20, 0.001);
printsolution2(op, scode, x); /* Print out the solution values */
/**** Weighted infeasibility repair:
specifying preferences for every constraint/bound separately ****/
XPRSgetintattrib(op, XPRS_ORIGINALCOLS, &ncol);
XPRSgetintattrib(op, XPRS_ORIGINALROWS, &nrow);
lrp = (double *)malloc(nrow*sizeof(double));
grp = (double *)malloc(nrow*sizeof(double));
lbp = (double *)malloc(ncol*sizeof(double));
ubp = (double *)malloc(ncol*sizeof(double));
memset(lrp, 0, nrow*sizeof(double));
memset(grp, 0, nrow*sizeof(double));
memset(lbp, 0, ncol*sizeof(double));
memset(ubp, 0, ncol*sizeof(double));
/* Relax bounds due to van capacity */
/* Repairweightedinfeas for upper bounds of concerned flow variables */
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0) ubp[XPRBgetcolnum(x[s][c])] = 20;
printf("\n**** Relax van capacity:\n");
XPRSrepairweightedinfeas(op, &scode, lrp, grp, lbp, ubp, 'd', 0.001, "");
printsolution2(op, scode, x);
/* Relax supply limits (may buy in additional quantities) */
/* Repairinfeas for 'less or equal' side of Supply constraints */
for(s=0; s<NSupp; s++) lrp[XPRBgetrownum(CSupply[s])] = 10;
printf("\n**** Relax supply limits:\n");
XPRSrepairweightedinfeas(op, &scode, lrp, grp, lbp, ubp, 'd', 0.001, "");
printsolution(prob, scode, x);
/* Relax demand constraints (may not satisfy all customers) */
/* Repairinfeas for 'greater or equal' side of Demand constraints */
for(c=0; c<NCust; c++) grp[XPRBgetrownum(CDemand[c])] = 9;
printf("\n**** Relax demand constraints:\n");
XPRSrepairweightedinfeas(op, &scode, lrp, grp, lbp, ubp, 'd', 0.001, "");
printsolution2(op, scode, x);
free(lrp);
free(grp);
free(lbp);
free(ubp);
}
}
/***********************************************************************/
/**** Read data from files ****/
void readdata(void)
{
FILE *datafile;
int s,c;
/* Initialize data tables to 0 */
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
{
COST[s][c] = 0;
IFVAN[s][c] = 0;
}
/* Read the demand data file */
datafile=fopen(COSTFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", COST[s], NCust);
fclose(datafile);
/* Read the van data file */
datafile=fopen(VANFILE,"r");
for(s=0;s<NSupp;s++)
XPRBreadarrlinecb(XPRB_FGETS, datafile, 99, "g,", IFVAN[s], NCust);
fclose(datafile);
}
/**** Print out the solution values ****/
void printsolution(XPRBprob prob, int scode, XPRBvar x[][NCust])
{
int s,c;
double sup,dem;
char *rstat[] = {"relaxed optimum found", "relaxed problem infeasible",
"relaxed problem unbounded", "solution nonoptimal for original objective",
"error", "numerical instability"};
printf("Status: %s\n", rstat[scode]);
if(scode==0)
{
XPRBsync(prob, XPRB_XPRS_SOL);
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
if(XPRBgetsol(x[s][c])>0.01)
printf("%s:%g ", XPRBgetvarname(x[s][c]), XPRBgetsol(x[s][c]));
printf("\n");
printf("Violations:\n");
for(c=0; c<NCust; c++)
{
sup=0;
for(s=0; s<NSupp; s++) sup+=XPRBgetsol(x[s][c]);
if(sup<DEMAND[c]) printf(" Customer %d: %g\n", c, DEMAND[c]-sup);
}
for(s=0; s<NSupp; s++)
{
dem=0;
for(c=0; c<NCust; c++) dem+=XPRBgetsol(x[s][c]);
if(dem>SUPPLY[s]) printf(" Supplier %d: %g\n", s, dem-SUPPLY[s]);
}
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0 && VANCAP<XPRBgetsol(x[s][c]))
printf(" Van %d-%d: %g\n", s, c, XPRBgetsol(x[s][c])-VANCAP);
}
}
void printsolution2(XPRSprob op, int scode, XPRBvar x[][NCust])
{
int s,c,ncol;
double sup,dem;
char *rstat[] = {"relaxed optimum found", "relaxed problem infeasible",
"relaxed problem unbounded", "solution nonoptimal for original objective",
"error", "numerical instability"};
double *sol;
printf("Status: %s\n", rstat[scode]);
if(scode==0)
{
XPRSgetintattrib(op, XPRS_ORIGINALCOLS, &ncol);
sol = (double *)malloc(ncol * sizeof(double));
XPRSgetlpsol(op, sol, NULL, NULL, NULL); /* Get the solution values */
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
if(XPRBgetcolnum(x[s][c])>=0 && sol[XPRBgetcolnum(x[s][c])]>0.01)
printf("%s:%g ", XPRBgetvarname(x[s][c]), sol[XPRBgetcolnum(x[s][c])]);
printf("\n");
printf("Violations:\n");
for(c=0; c<NCust; c++)
{
sup=0;
for(s=0; s<NSupp; s++)
if(XPRBgetcolnum(x[s][c])>=0) sup+=sol[XPRBgetcolnum(x[s][c])];
if(sup<DEMAND[c]) printf(" Customer %d: %g\n", c, DEMAND[c]-sup);
}
for(s=0; s<NSupp; s++)
{
dem=0;
for(c=0; c<NCust; c++)
if(XPRBgetcolnum(x[s][c])>=0) dem+=sol[XPRBgetcolnum(x[s][c])];
if(dem>SUPPLY[s]) printf(" Supplier %d: %g\n", s, dem-SUPPLY[s]);
}
for(s=0; s<NSupp; s++)
for(c=0; c<NCust; c++)
if(IFVAN[s][c]!=0 && XPRBgetcolnum(x[s][c])>=0 &&
VANCAP<sol[XPRBgetcolnum(x[s][c])])
printf(" Van %d-%d: %g\n", s, c, sol[XPRBgetcolnum(x[s][c])]-VANCAP);
}
}
/***********************************************************************/
int main(int argc, char **argv)
{
XPRBprob prob;
prob=XPRBnewprob("Delivery"); /* Initialize a new problem in BCL */
readdata(); /* Data input from file */
moddelivery(prob); /* Problem formulation & solving */
return 0;
}
|
© 2001-2019 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.