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

Delivery - Data input from file; infeasibility analysis

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.


Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
xbdelvr.c[download]
xbdlvriis.c[download]
xbdlvriis2iso.c[download]
xbdlvriis2rep.c[download]

Data Files





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;
}



Back to examples browserPrevious exampleNext example