FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

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

xbd1wagoncs.zip[download all files]

Source Files





xbd1wagon2.cs

/********************************************************
  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 */
            }
        }
    
    }
}

Back to examples browserPrevious exampleNext example