/********************************************************/
/* 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]);
/****VARIABLES****/
for(j=0;j<NWIDTHS;j++)
pat[j]=p.newVar("pat_" + (j+1), BCLconstant.XPRB_UI, 0,
(int)Math.Ceiling((double)DEMAND[j]/PATTERNS[j,j]));
/****OBJECTIVE****/
le = new XPRBexpr();
for(j=0;j<NWIDTHS;j++)
le += pat[j]; /* Minimize total number of rolls */
cobj = p.newCtr("OBJ", le);
p.setObj(cobj);
/****CONSTRAINTS****/
/* Satisfy the demand per width */
for(i=0;i<NWIDTHS;i++)
{
le = new XPRBexpr(0);
for(j=0;j<NWIDTHS;j++)
le += PATTERNS[i,j] * pat[j];
dem[i] = p.newCtr("Demand", le >= 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++)
{
p.lpOptimize(); /* Solve the LP */
basis = p.saveBasis(); /* Save the current basis */
objval = p.getObjVal(); /* Get the objective value */
/* Get the solution values: */
for(j=0;j<npatt;j++) solpat[j]=pat[j].getSol();
for(i=0;i<NWIDTHS;i++) dualdem[i]=dem[i].getDual();
/* Solve integer knapsack problem z = min{cx : ax<=r, x in Z^n}
with r=MAXWIDTH, n=NWIDTHS */
z = knapsack(NWIDTHS, dualdem, WIDTH, (double)MAXWIDTH, DEMAND, x);
System.Console.Write("(" + (XPRB.getTime()-starttime)/1000.0 +
" sec) Pass " + (npass+1) + ": ");
if(z < 1+EPS)
{
System.Console.WriteLine("no profitable column found.");
System.Console.WriteLine();
basis.reset(); /* No need to keep basis any longer */
break;
}
else
{
/* Print the new pattern: */
System.Console.WriteLine("new pattern found with marginal"+
" cost " + (z-1));
System.Console.Write(" Widths distribution: ");
dw=0;
for(i=0;i<NWIDTHS;i++)
{
System.Console.Write(WIDTH[i] + ":" + x[i] + " ");
dw += WIDTH[i]*x[i];
}
System.Console.WriteLine("Total width: " + dw);
/* Create a new variable for this pattern: */
pat[npatt]=p.newVar("pat_"+(npatt+1), BCLconstant.XPRB_UI);
/* Add new var. to the objective */
cobj += pat[npatt];
/* Add new var. to demand constraints*/
dw=0;
for(i=0; i<NWIDTHS; i++)
if(x[i] > 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<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;
}
}
}
|
