/********************************************************
Xpress-BCL C# Example Problems
==============================
file d1wagon2.cs
`````````````````
Load balancing of train wagons
(second version, using heuristic solution as
start solution for MIP)
(c) 2014 Fair Isaac Corporation
author: L.Bertacco, 2014
J.Farmer, 2014
********************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BCL;
using Optimizer;
namespace Examples
{
class TestD1Wagon2
{
/* Box weights */
static int[] WEIGHT = { 34, 6, 8, 17, 16, 5, 13, 21, 25, 31, 14, 13, 33, 9, 25, 25 };
static int NBOXES = WEIGHT.Length; /* Number of boxes */
static int NWAGONS = 3; /* Number of wagons */
static int WMAX = 100; /* Weight limit of the wagons */
static int[] HeurSol = new int[NBOXES]; /* Heuristic solution: for each box */
/* Problem object & variables */
static XPRBprob prob;
static XPRBvar[,] load = new XPRBvar[NBOXES, NWAGONS];
static XPRBvar maxweight;
/// <summary>
/// Model the problem
/// </summary>
static void d1w2_model()
{
// VARIABLES
/* Create load[box,wagon] (binary) */
for (int b = 0; b < NBOXES; b++)
for (int w = 0; w < NWAGONS; w++)
load[b, w] = prob.newVar("load_" + (b + 1) + "_" + (w + 1), BCLconstant.XPRB_BV);
/* Create maxweight (continuous with lb=ceil((sum(b in BOXES) WEIGHT(b))/NBOXES */
double sum_weights = 0;
for (int b = 0; b < NBOXES; b++)
sum_weights += WEIGHT[b];
maxweight = prob.newVar("maxweight", BCLconstant.XPRB_PL, Math.Ceiling(sum_weights / NBOXES), BCLconstant.XPRB_INFINITY);
// CONSTRAINTS
/* Every box into one wagon; forall (b in BOXES) sum(w in WAGONS) load(b,w)=1 */
for (int b = 0; b < NBOXES; b++)
{
XPRBexpr eq = new XPRBexpr();
for (int w = 0; w < NWAGONS; w++) eq.add(load[b, w]);
prob.newCtr(eq == 1);
}
/* Limit the weight loaded into every wagon: forall(w in WAGONS) sum(b in BOXES) WEIGHT(b)*load(b,w)<=maxweight */
for (int w=0;w<NWAGONS;w++) {
XPRBexpr le = new XPRBexpr();
for (int b=0;b<NBOXES;b++) le.add(load[b,w]*WEIGHT[b]);
prob.newCtr( le <= maxweight );
}
// OBJECTIVE
prob.setObj(maxweight+0);
prob.setSense( BCLconstant.XPRB_MINIM );
}
/// <summary>
/// Solve the problem
/// </summary>
static void d1w2_solve()
{
XPRSprob oprob = prob.getXPRSprob(); /* Get Optimizer problem */
/* Alternative to lower bound on maxweight: adapt the Optimmizer cutoff value */
//oprob.MIPAddCutoff = -0.99999;
/* Comment out the following line to enable the optimizer log */
oprob.OutputLog = 0;
/* Create a BCL solution from the heuristic solution we've found */
XPRBsol sol = prob.newSol();
/* Set the solution varlues for all discrete variables that are non-zero */
for (int b = 0; b < NBOXES; b++) sol.setVar(load[b, HeurSol[b]], 1);
/* It is possible, but not necessary, to set values for ALL discrete vars */
/* by uncommenting the following line. In this case, the usersolnotify */
/* callback would return status requal to 2 (instead of 3), as the solution */
/* would be feasible without the need of a local search. */
// for (int b=0;b<NBOXES;b++) for (int w=0;w<NWAGONS;w++) sol.setVar(load[b,w], (w==HeurSol[b])?1:0));
prob.addMIPSol(sol, "heurSol"); /* Send the solution to the optimizer */
/* Request notification of solution status after processing */
oprob.UserSolNotifyCallbacks += new UserSolNotifyCallback(XPRSuserSolNotifyEvent);
/* Set Optimizer controls to make use of loaded solution */
oprob.HeurSearchEffort = 2;
oprob.HeurSearchRootSelect = 31;
oprob.HeurSearchTreeSelect = 19;
prob.mipOptimize("c"); /* Solve the problem */
int statmip = prob.getMIPStat(); /* Get the problem status */
if (statmip == BCLconstant.XPRB_MIP_SOLUTION || statmip == BCLconstant.XPRB_MIP_OPTIMAL)
{ /* An integer solution has been found */
/* Print solution */
if (statmip == BCLconstant.XPRB_MIP_OPTIMAL) Console.Write("Optimal ");
Console.WriteLine("Solution");
Console.WriteLine(" Max weight: {0}", prob.getObjVal());
for (int w = 0; w < NWAGONS; w++)
{
int tot_weight = 0;
Console.Write(" {0}:", (w + 1));
for (int b = 0; b < NBOXES; b++)
{
if (load[b, w].getSol() > .5)
{
Console.Write(" {0}", (b + 1));
tot_weight += WEIGHT[b];
}
}
Console.WriteLine(" (total weight: {0})", tot_weight);
}
}
}
/// <summary>
/// LPT (Longest processing time) heuristic;
/// One at a time, place the heaviest unassigned
/// box onto the wagon with the least load.
/// </summary>
/// <returns></returns>
static double solve_heur()
{
int[] ORDERW = new int[NBOXES]; /* Box indices sorted in decreasing weight order */
int[] CurNum = new int[NWAGONS]; /* For each wagon w, this is the number of boxes currently loaded */
int[] CurWeight = new int[NWAGONS]; /* For each wagon 2, this is the current weight; ie the sum of weights of loaded boxes */
int[,] Load = new int[NWAGONS, NBOXES]; /* Load[w,i] (for i=0..CurNum[w]-1) contains the box index of the i-th box loaded on wagon 2 */
/* Copy the box indices into array ORDERW and sort them in decreasing */
/* order of box weights (the sorted indices are returned in array ORDERW) */
for (int b = 0; b < NBOXES; b++) ORDERW[b] = b;
Array.Sort(ORDERW, (i1, i2) => ((IComparable)WEIGHT[i2]).CompareTo((IComparable)WEIGHT[i1]));
/* Distribute the load to the wagons using the LPT heuristic */
for (int b = 0; b < NBOXES; b++)
{
int v = 0; /* Find wagon v with the smallest load */
for (int w = 0; w < NWAGONS; w++) if (CurWeight[w] <= CurWeight[v]) v = w;
Load[v,CurNum[v]] = ORDERW[b]; /* Add current box to wagon v */
CurNum[v]++; /* Increase the counter of boxes on v */
CurWeight[v] += WEIGHT[ORDERW[b]]; /* Update current weight of the wagon */
}
/* Calculate the solution value */
double heurobj = 0;
for (int w = 0; w < NWAGONS; w++) if (CurWeight[w] > heurobj) heurobj = CurWeight[w];
/* Print solution */
Console.WriteLine("Heuristic solution:");
Console.WriteLine(" Max weight: {0}", heurobj);
for (int w = 0; w < NWAGONS; w++)
{
Console.Write(" {0}:", w + 1);
for (int i = 0; i < CurNum[w]; i++) Console.Write(" {0}", (Load[w, i] + 1));
Console.WriteLine(" (total weight: {0}", CurWeight[w]);
}
/* Save the heuristic solution into the HeurSol array */
for (int w = 0; w < NWAGONS; w++) for (int i = 0; i < CurNum[w]; i++) HeurSol[Load[w, i]] = w;
return heurobj;
}
/// <summary>
/// Delegate function reporting loaded solution status
/// </summary>
static void XPRSuserSolNotifyEvent(XPRSprob oprob, object data, string name, int status)
{
Console.WriteLine("Optimizer loaded solution {0} with status={1}", name, status);
}
/// <summary>
/// Run the example
/// </summary>
static void Main()
{
if (solve_heur() <= WMAX)
{
Console.WriteLine("Heuristic solution fits capacity limits");
}
else
{
XPRB.init(); /* Initialize Xpress-BCL */
prob = new XPRBprob("d1wagon2"); /* Create a new problem in BCL */
d1w2_model(); /* Model the problem */
d1w2_solve(); /* Solve the problem */
}
}
}
}
|
