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

Apply a binary fixing heuristic to an unpresolved MIP problem

Description

We take a production plan model and solve its LP relaxation.

Next we fix those binary variables that are very near zero to 0.0, and those that are almost one to 1.0, by changing their respective upper and lower bounds. Finally, we solve the modified problem as a MIP.

This heuristic will speed up solution - though may fail to optimse the problem.

The results are displayed on screen and the problem statistics stored in a log file.

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

FixBV.java

/***********************************************************************
Xpress Optimizer Examples
=========================

file FixBV.java

Apply a binary fixing heuristic to an unpresolved MIP problem.

We take a production plan model and solve its LP relaxation.
Next we fix those binary variables that are very
near zero to 0.0, and those that are almost one to 1.0, by changing
their respective upper and lower bounds. Finally, we solve the
modified problem as a MIP.
This heuristic will speed up solution - though may fail to optimise
the problem.
The results are displayed on screen and the problem statistics
stored in a log file.

(c) 2020-2023 Fair Isaac Corporation
***********************************************************************/

import com.dashoptimization.DefaultMessageListener;
import com.dashoptimization.XPRS;
import com.dashoptimization.XPRSprob;
import static com.dashoptimization.XPRSenumerations.CutStrategy;
import static com.dashoptimization.XPRSenumerations.MIPStatus;
import static com.dashoptimization.XPRSenumerations.ObjSense;

import java.io.File;

public class FixBV {
/** Tolerance on binary variables */
private static final double TOL = 0.0005;
public static void main(String[] args) {
String logName = "FixBV.log";
String problem = args.length == 0 ? "../data/coco" : args[0];

try (XPRSprob prob = new XPRSprob(null)) {
// Delete and define log file
File logFile = new File(logName);
logFile.delete();
prob.setLogFile(logFile.getAbsolutePath());

// Enable output

// Turn off presolve and permit no cuts - to slow down solution
// and allow the effect of the heuristic to be be seen
prob.controls().setPresolve(XPRS.PRESOLVE_NONE);
prob.controls().setCutStrategy(CutStrategy.NONE);

/*** Solve the LP relaxation ***/

// Solve the root node relaxation
prob.chgObjSense(ObjSense.MAXIMIZE);
prob.mipOptimize("l");

// Get LP solution values
double[] x = prob.getLpSolX();

/*** Fix the binary variables that are at their bounds ***/

int nMipEnt = prob.attributes().getMIPEnts();
XPRSprob.MIPEntityInfo info = prob.getDiscreteCols();

// Allocate memory for bound arrays
int[] bndInd = new int[nMipEnt];
double[] bndVal = new double[nMipEnt];
byte[] bndType = new byte[nMipEnt];

// Go through the MIP entities and fix
int nBnd = 0;
for (int k = 0; k < nMipEnt; ++k) {
// Test whether binary variable
if (info.coltype[k] == 'B') {
int j = info.colind[k];

// If the value of the BV is within TOL of zero,
// store its index, set its upper bound to 0, and
// increment the bound counter */
if (x[j] <= TOL) {
bndInd[nBnd] = j;
bndType[nBnd] = 'U';
bndVal[nBnd] = 0.0;
nBnd++;
}
// If the value of the BV is within TOL of one, store
// its index, set its lower bound to 1, and increment
// the bound counter */
else if ((1-x[j]) <= TOL) {
bndInd[nBnd] = j;
bndType[nBnd] = 'L';
bndVal[nBnd] = 1.0;
nBnd++;
}
}
}

// Apply the fixings
prob.chgBounds(nBnd, bndInd, bndType, bndVal);
System.out.println("Solving problem " + problem + " with a binary fixing heuristic:");
System.out.println("   After the LP optimisation " + nBnd + " binary variables were fixed");

/*** Solve the modified problem as a MIP ***/

// Search for an integer solution
prob.mipOptimize("");

// Get the number of nodes solved in the MIP search
int nNodes = prob.attributes().getNodes();

// Get the objective value of the best integer solution
double objVal = prob.attributes().getMIPObjVal();

// Check the MIP status and display the results of the
// MIP search */
MIPStatus status = prob.attributes().getMIPStatus();

System.out.println("   Problem has not been loaded");
else if (status.equals(MIPStatus.LP_NOT_OPTIMAL))
System.out.println("   Search has not begun - LP has not been optimised");
else if (status.equals(MIPStatus.LP_OPTIMAL))
System.out.println("   Search has not begun - LP has been optimised");
else if (status.equals(MIPStatus.NO_SOL_FOUND))
System.out.println("   Search interrupted - No integer solution was found");
else if (status.equals(MIPStatus.SOLUTION))
System.out.println("   Search interrupted - Integer solution found: " + objVal);
else if (status.equals(MIPStatus.INFEAS))
System.out.println("   No integer solution was found");
else if (status.equals(MIPStatus.OPTIMAL))
System.out.println("   Integer solution found: " + objVal);

System.out.println("   The MIP optimisation took " + nNodes + " nodes");
}
}
}