Cutstk - Column generation for a cutting stock problem

/********************************************************
  BCL Example Problems
  ====================

  file xbcutstk.c
  ```````````````
  Cutting stock problem, solved by column (= cutting
  pattern) generation heuristic looping over the root 
  node.

  (c) 2008 Fair Isaac Corporation
      author: S.Heipcke, 2001, rev. Mar. 2014
********************************************************/

#include 
#include 
#include 
#include "xprb.h"
#include "xprs.h"

#define NWIDTHS 5
#define MAXWIDTH 94

#define EPS 1e-6
#define MAXCOL 10

/****DATA****/
double WIDTH[] = {17, 21, 22.5,  24, 29.5};  /* Possible widths */
int DEMAND[] =  {150, 96,   48, 108,  227};  /* Demand per width */
int PATTERNS[NWIDTHS][NWIDTHS];              /* (Basic) cutting patterns */

XPRBvar use[NWIDTHS+MAXCOL];               /* Rolls per pattern */
XPRBctr dem[NWIDTHS];                      /* Demand constraints */
XPRBctr cobj;                              /* Objective function */

double knapsack(int N, double *c, double *a, double R, int *d, int *xbest);

/***********************************************************************/

void modcutstock(XPRBprob prob)
{
 int i,j;

 for(j=0;j EPS)
    {
     XPRBaddterm(dem[i], use[npatt], x[i]);
     if((int)ceil((double)DEMAND[i]/x[i]) > dw)
      dw = (int)ceil((double)DEMAND[i]/x[i]);
    }
   XPRBsetub(use[npatt],dw);         /* Change the upper bound on the new var.*/  

   npatt++;

   XPRBloadmat(prob);                /* Reload the problem */
   XPRBloadbasis(basis);             /* Load the saved basis */
   XPRBdelbasis(basis);              /* No need to keep the basis any longer */
  }
 }

 XPRBmipoptimize(prob,"c");          /* Solve the MIP */
  
 printf("(%g sec) Optimal solution: %g rolls, %d patterns\n   ", 
   (XPRBgettime()-starttime)/1000.0, XPRBgetobjval(prob), npatt);
 printf("Rolls per pattern: ");
 for(i=0;i