 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Wagon - MIP start solution heuristic

Description
Load balancing of train wagons. A heuristic solution obtained via a Longest processing time heuristic is loaded as start solution into Xpress Optimizer.

Further explanation of this example: The start solution heuristic is described in the book 'Applications of optimization with Xpress-MP', Section 9.1 Wagon load balancing

Source Files

xbd1wagon2.cs

```/********************************************************
Xpress-BCL C# Example Problems
==============================

file d1wagon2.cs
`````````````````
(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
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();
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();
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 */

/* 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++)
{
{
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;
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 */
}
}

}
}

```   