Cutstk - Column generation for a cutting stock problem

/********************************************************/
/*  Xpress-BCL C# Example Problems                      */
/*  ==============================                      */
/*                                                      */
/*  file xbcutstk.cs                                    */
/*  ````````````````                                    */
/*  Example for the use of Xpress-BCL                   */
/*  (Cutting stock problem, solved by column (= cutting */
/*   pattern) generation heuristic looping over the     */
/*   root node)                                         */
/*                                                      */
/*  (c) 2008 Fair Isaac Corporation                     */
/*      authors: S.Heipcke, D.Brett, rev. Mar. 2014     */
/********************************************************/

using System;
using System.Text;
using System.IO;
using Optimizer;
using BCL;


namespace Examples
{
    public class TestAdvCutstk
    {
        const int NWIDTHS = 5;
        const int MAXWIDTH = 94;

        const double EPS = 1e-6;
        const int MAXCOL = 10;

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

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

        /* Initialize a new problem in BCL */
        XPRBprob p = new XPRBprob("CutStock");                    

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

        public void modCutStock()
        {
            int i,j;
            XPRBexpr le;

            for(j=0;j= DEMAND[i]);
            }
        }

        /*********************************************************************/
        /*  Column generation loop at the top node:                          */
        /*    solve the LP and save the basis                                */
        /*    get the solution values                                        */
        /*    generate new column(s) (=cutting pattern)                      */
        /*    load the modified problem and load the saved basis             */
        /*********************************************************************/
        public void solveCutStock()
        {
            double objval;                /* Objective value */
            int i,j;
            int starttime;
            int npatt, npass;             /* Counters for columns and passes */
            
            /* Solution values for variables pat */
            double[] solpat = new double[NWIDTHS+MAXCOL];  
            
            /* Dual values of demand constraints */
            double[] dualdem = new double[NWIDTHS]; 
            
            XPRBbasis basis;
            double dw,z;
            int[] x = new int[NWIDTHS];
            XPRSprob xprs = p.getXPRSprob();

            starttime=XPRB.getTime();
            npatt = NWIDTHS;

            for(npass=0;npass EPS)
                        {
                            dem[i] += (x[i]*pat[npatt]);
                            if((int)Math.Ceiling((double)DEMAND[i]/x[i]) > dw)
                            dw = (int)Math.Ceiling((double)DEMAND[i]/x[i]);
                        }
                    
                    /* Change the upper bound on the new var.*/
                    pat[npatt].setUB(dw);             

                    npatt++;

                    p.loadMat();         /* Reload the problem */
                    p.loadBasis(basis);  /* Load the saved basis */
                    basis.reset();       /* No need to keep basis any longer */
                }
            }

            p.mipOptimize();                     /* Solve the MIP */

            System.Console.WriteLine("(" + (XPRB.getTime()-starttime)/1000.0 + 
            	" sec) Optimal solution: " + p.getObjVal() + " rolls, " + 
            	npatt + " patterns"); 
            System.Console.Write("   Rolls per pattern: ");
            for(i=0;i