/********************************************************
  Xpress-BCL Java Example Problems
  ================================

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

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

import java.lang.*;
import com.dashoptimization.*;

public class xbcutstk {
    static final int NWIDTHS = 5;
    static final int MAXWIDTH = 94;

    static final double EPS = 1e-6;
    static final int MAXCOL = 10;

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

    static XPRBvar[] pat;              /* Rolls per pattern */
    static XPRBctr[] dem;              /* Demand constraints */
    static XPRBctr cobj;               /* Objective function */

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

    static void modCutStock(XPRBprob p) throws XPRSexception {
        int i,j;
        XPRBexpr le;

        PATTERNS = new int[NWIDTHS][NWIDTHS];
        for(j=0;j<NWIDTHS;j++) PATTERNS[j][j]=(int)Math.floor((double)MAXWIDTH/WIDTH[j]); pat=new for(j=0;j<NWIDTHS;j++) pat[j]=p.newVar("pat_"+(j+1), le=new cobj=p.newCtr("OBJ", Minimize total number of rolls dem=new for(i=0;i<NWIDTHS;i++) Satisfy the demand per width dem[i]=p.newCtr("Demand", Column generation loop at top node: solve LP and save basis get solution values generate new (=cutting load modified problem saved static void XPRBprob throws XPRSexception double objval=0; Objective value int Counters for columns passes Solution variables Dual constraints XPRBbasis x=new solpat=new dualdem=new starttime=XPRB.getTime(); npatt=NWIDTHS; for(npass=0;npass<MAXCOL;npass++) Solve Save current Get objective values: solpat[j]=pat[j].getSol(); dualdem[i]=dem[i].getDual(); integer knapsack z=min{cx : ax<=r, in with r=MAXWIDTH, n=NWIDTHS Force garbage collection to clean up subproblem: +=" sec) Pass " profitable column No need keep any longer else Print pattern: pattern found marginal cost=" + (z-1) );
                System.out.print(" Widths distribution:=");
                dw=0;
                for(i=0;i<NWIDTHS;i++) {
                    System.out.print(WIDTH[i] +" +"=");
                    dw += WIDTH[i]*x[i];
                }
                System.out.println(" Total width:=" + dw);

                /* Create a new variable for this pattern: */
                pat[npatt]=p.newVar(" Add var. dw=0;> EPS) {
                        dem[i].add(pat[npatt].mul(x[i]));
                        if((int)Math.ceil((double)DEMAND[i]/x[i]) > dw)
                            dw = (int)Math.ceil((double)DEMAND[i]/x[i]);
                    }
                pat[npatt].setUB(dw);           /* Change the upper bound on the new var.*/
                npatt++;

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

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

        System.out.println("(" + (XPRB.getTime()-starttime)/1.000 +
                           " sec) Optimal solution: " + p.getObjVal() + " rolls, " + npatt +
                           " patterns");
        System.out.print("   Rolls per pattern: ");
        for(i=0;i<npatt;i++) System.out.print(pat[i].getSol() + ", ");
        System.out.println();
    }

    /**************************************************************************/
    /* Integer Knapsack Algorithm for solving the integer knapsack problem    */
    /*    z = max{cx : ax <= R, x <= d, x in Z^N}                             */
    /*                                                                        */
    /* 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                                  */
    /**************************************************************************/
    static double knapsack(XPRB bcl, int N, double[] c, double[] a, double R, int[] d, int[] xbest) {
        /*
          System.out.println("Solving z = max{cx : ax <= b; x in Z^n}");
          System.out.print("   c   =");
          for(j = 0; j < N; j++)  System.out.print(" " + c[j] + ",");
          System.out.println();
          System.out.print("   a   =");
          for(j = 0; j < N; j++)  System.out.print(" " + a[j] + ",");
          System.out.println();
          System.out.print("   c/a =");
          for (j = 0; j < N; j++)  System.out.print(" " + c[j]/a[j] + ",");
          System.out.println();
          System.out.print("   b   = " + R);
        */

        try (XPRBprob pk = bcl.newProb("Knapsack")) {
            XPRBvar[] x = new XPRBvar[N];
            for(int j=0;j<N;j++) x[j]=pk.newVar("x", XPRB.UI, 0, d[j]);

            XPRBexpr klobj = new XPRBexpr();
            for(int j=0;j<N;j++) klobj.add(x[j].mul(c[j]));
            pk.setObj(klobj);
            XPRBexpr knap = new XPRBexpr();
            for(int j=0;j<N;j++) knap.add(x[j].mul(a[j]));
            pk.newCtr("KnapXPRBctr", knap.lEql(R) );
            pk.setSense(XPRB.MAXIM);
            pk.mipOptimize("");

            double zbest = pk.getObjVal();
            for(int j=0;j<N;j++) xbest[j]=(int)Math.floor(x[j].getSol() + 0,5);
            /*
              System.out.println("   z = " + zbest);
              System.out.print("   x =");
              for(j=0; j<N; j++) System.out.print(" " + xbest[j] + ",");
              System.out.println();
            */

            return (zbest);
        }
    }

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

    public static void main(String[] args) throws XPRSexception {
        try (XPRB bcl = new XPRB();            /* Initialize BCL */
             XPRBprob p = bcl.newProb("Els");  /* Create a new problem */
             XPRS xprs = new XPRS()) {         /* Initialize Xpress-Optimizer */
            modCutStock(p);                    /* Model the problem */
            solveCutStock(bcl, p);             /* Solve the problem */
        }
    }
}