/********************************************************/
/*  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<NWIDTHS;j++) PATTERNS[j,j]=(int)Math.Floor(MAXWIDTH/WIDTH[j]); for(j=0;j<NWIDTHS;j++) pat[j]=p.newVar("pat_" le=new +=pat[j]; Minimize total number of rolls cobj=p.newCtr("OBJ", Satisfy the demand per width for(i=0;i<NWIDTHS;i++) dem[i]=p.newCtr("Demand",>= 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<MAXCOL;npass++) Solve the LP basis=p.saveBasis(); Save current objval=p.getObjVal(); Get objective value solution values: for(j=0;j<npatt;j++) solpat[j]=pat[j].getSol(); for(i=0;i<NWIDTHS;i++) dualdem[i]=dem[i].getDual(); integer knapsack problem z=min{cx : ax<=r, x in with r=MAXWIDTH, n=NWIDTHS +=" sec) Pass " profitable column No need to keep any longer else Print new pattern: pattern found marginal"+=" cost " Widths distribution:=");
                    dw=0;
                    for(i=0;i<NWIDTHS;i++)
                    {
                        System.Console.Write(WIDTH[i] + " dw width:=" + dw);

                    /* Create a new variable for this pattern: */
                    pat[npatt]=p.newVar(" Add var. cobj demand> 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)/1.000 +
            	" sec) Optimal solution: " + p.getObjVal() + " rolls, " +
            	npatt + " patterns");
            System.Console.Write("   Rolls per pattern: ");
            for(i=0;i<npatt;i++) System.Console.Write(pat[i].getSol() + ", ");
            System.Console.WriteLine();;
        }

        /*********************************************************************/
        /* Integer Knapsack Algorithm for solving the integer knapsack       */
        /* problem:                                                          */
        /*    z = max{cx : ax <= R, x <= d, x in Z^N}                        */
        /* where there is an unlimited number of each type of item available.*/
        /*                                                                   */
        /* Input data:                                                       */
        /*   N:        Number of item types                                  */
        /*   c[i]:     Unit profit of item type i, i=1..n                    */
        /*   a[i]:     Unit resource use of item type i, i=1..n              */
        /*   R:        Total resource available                              */
		/*   d[i]:     Demand for item type i, i=1..n                        */
        /* Return values:                                                    */
        /*   xbest[i]: Number of items of type i used in optimal solution    */
        /*   zbest:    Value of optimal solution                             */
        /*********************************************************************/
        public double knapsack(int N, double[] c, double[] a, double R,
        		       int[] d, int[] xbest)
        {
            int j;
            double zbest = 0.0;
            XPRBvar[] x;
            XPRBexpr klobj, knap;
            XPRBprob pk = new XPRBprob("Knapsack");

            x = new XPRBvar[N];
            if(x==null)
            	System.Console.WriteLine("Allocating memory for variables "
            				  +"failed.");
            for(j=0;j<N;j++) x[j]=pk.newVar("x", BCLconstant.XPRB_UI, 0, d[j]);

            klobj = new XPRBexpr();
            knap = new XPRBexpr();
            for(j=0;j<N;j++) klobj += c[j]*x[j];
            pk.setObj(pk.newCtr("OBJ",klobj));
            for(j=0;j<N;j++) knap += a[j]*x[j];
            pk.newCtr("KnapXPRBctr", knap <= R);
            pk.setSense(BCLconstant.XPRB_MAXIM);
            pk.mipOptimize();

            zbest = pk.getObjVal();
            for(j=0;j<N;j++) xbest[j]=(int)Math.Floor(x[j].getSol() + 0,5);

            return (zbest);
        }

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

        public static void Main()
        {
            XPRB.init();
            TestAdvCutstk TestInstance = new TestAdvCutstk();

            TestInstance.modCutStock();                 /* Model the problem */
            TestInstance.solveCutStock();               /* Solve the problem */

            return;
        }
    }
}