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

Apply a primal heuristic to a knapsack problem


The program demonstrates the use of the global log callback.

We take the knapsack problem stored in burglar.mat and instigate a global search. At each node, so long as the current solution is both LP optimal and integer infeasible, we truncate the solution values to create a feasible integer solution. We then update the cutoff, if the new objective value has improved it, and continue the search.[download all files]

Source Files

Data Files


using System;
using Optimizer;

namespace XPRSExamples
    class Knapsack
        public static void Main(string[] args)
            Knapsack example = new Knapsack();

        private void Run()
            string sLogFile = "knapsack.log";
            string sProblem = @"..\..\..\Data\burglar";
                // initialise optimizer

                prob = new XPRSprob();

                // define log file

                // Tell Optimizer to call OptimizerMsg whenever a message is output
                prob.MessageCallbacks += new MessageCallback (this.OptimizerMsg);

                // Get and display the Optimizer version number

                //Turn off presolve and disallow cuts - to slow solution and allow the
                // effect of the heuristic to be seen
                prob.Presolve = 0;
                prob.CutStrategy = 0;

                // Read the problem file
        prob.MPSFormat = -1;

                // Prepare to apply the heuristic

                // Get the number of columns
                gnCol = prob.Cols;

                // Allocate memory to the coefficient and solution arrays
                gpObjCoef = new double[gnCol];
                x = new double[gnCol];
                // Get the objective function coefficients
                prob.GetObj(gpObjCoef, 0,gnCol-1);

                // Get integer feasibility tolerance
                gdIntTol = prob.MIPTol;

                // Tell Optimizer to print global information to the log file at each node
                prob.MIPLog = 3;

                // Tell Optimizer to call truncsol at each node and apply the heuristic
                prob.GloballogCallbacks += new GloballogCallback(this.TruncSol);

                // Perform the global search - in the course of which the heuristic will
                // be applied
                Console.WriteLine("Applying a primal heuristic to problem {0}",sProblem);
            catch (XPRSException e)
        throw e;

        public void OptimizerMsg (XPRSprob prob, object data, string message, int len, int msglvl)
            Console.WriteLine ("{0}" + message, data);

        public int TruncSol(XPRSprob prob, object data)

            int nNodeNum;               // Number of nodes solved
            double dObjVal;            // Objective value
            double dCutoff;            // Cutoff value
            LPStatus nLPStatus;        // LP solution status
            int nIntInf;               // Number of integer infeasibilities
            int i;                     // Loop counter
            double dHeurObj;           // Objective value after the solution values have been truncated
            string [] sLPStatus = 
                    "Optimal","Infeasible","Objective worse than cutoff",
                    "Unfinished","Unbounded","Cutoff in dual"

            // Get the current node number
            nNodeNum = prob.Nodes;
            // Get objective value at the current node
            dObjVal = prob.LPObjVal;

            // Get the current cutoff value
            dCutoff = prob.MIPAbsCutoff;

            // Get LP solution status and the number of integer infeasibilities
            nLPStatus = prob.LPStatus;
            nIntInf = prob.MIPInfeas;

            // Apply heuristic if nodal solution is LP optimal and integer infeasible
            if (nLPStatus == LPStatus.Optimal && nIntInf>0) 

                // Get LP solution
                // Truncate each solution value - making allowance for the integer
                //	tolerance - and calculate the new "heuristic" objective value
                for (dHeurObj=0, i=0; i<gnCol; i++) 
                    dHeurObj += gpObjCoef[i] * (int) (x[i] + gdIntTol);
                Console.WriteLine("   Node {0}: Objective Value: ORIGINAL {1};  HEURISTIC {2}\n\n",

                // If the "heuristic" objective value is better, update the cutoff -
                //	we assume that all the objective coefficents are integers
                if( dHeurObj > dCutoff) 
                    prob.MIPAbsCutoff = dHeurObj + 0.9999;  
                    Console.WriteLine("              ** Cutoff updated to {0} **\n\n",dHeurObj+1.0);

                /* If the nodal solution is not LP optimal do not apply the heuristic */
            else if (nLPStatus != LPStatus.Optimal) 
                Console.WriteLine("   Node {0}: LP solution not optimal, not applying heuristic\n",nNodeNum);
                Console.WriteLine("           ({0})\n\n",sLPStatus[(int)nLPStatus-1]);

                /* If the nodal solution is integer feasible print the objective value */
            else if (nIntInf == 0)
                Console.WriteLine("   Node {0}: Integer solution found: Objective Value {1}\n\n", 

            return 0;    

        private XPRSprob prob;

        // converted from the C globals
        private double[] x;             // Nodal LP solution values
        private double[] gpObjCoef;     // Objective function coefficients
        private double gdIntTol;        // Integer feasibility tolerance
        private int gnCol;              // Number of columns

Back to examples browserPrevious exampleNext example