FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Apply a primal heuristic to a knapsack problem

Description

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.

Source Files

Data Files

Knapsack.cs

using System;
using Optimizer;

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

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

try
{
// initialise optimizer
XPRS.Init("");
Console.WriteLine(XPRS.GetBanner());

prob = new XPRSprob();

// define log file
prob.SetLogFile(sLogFile);

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

// Get and display the Optimizer version number
Console.WriteLine(prob.Version);

//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;

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);
prob.MipOptimize();

}
catch (XPRSException e)
{
Console.WriteLine(e.ToString());
throw e;
}
finally
{
prob.Destroy();
XPRS.Free();
}
}

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
prob.GetSol(x,null,null,null);

// 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",
nNodeNum,dObjVal,dHeurObj);

// 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",
nNodeNum,dObjVal);
}

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