* Here "most infeasible" means the variable with the biggest fractionality, * i.e., the integer variable that is farthest away from an integral value. *
* *
* In order to find the variable with the biggest fractionality, we need the
* variable types (so that we don't end up branching on a fractional variable)
* and the values of the variables in the current relaxation. This data is
* typically queried into arrays cType and x at each
* node at which we have to find a branching variable.
* Allocation of these arrays may take time, so it is desirable to cache those
* arrays so that we don't have to (re)allocate them at each and every node.
* However, when caching these arrays a number of things have to be considered,
* most of which are implemented in this example:
*
x array since otherwise
* multiple threads might read into the same array from different nodes.
* The cType array can be shared between threads since this is
* a read-only array.
* By default Xpress optimizer serializes the execution of callbacks
* using a mutex. That is, by default callbacks will not be executed
* simultaneously. In that case the threads can share the same
* x array. You can tell the XPress optimizer to not
* serialize callbacks by setting the MUTEXCALLBACKS control
* to 0. In that case, the threads cannot share the same x
* array and each thread has to allocate its own array.
* cType an x arrays one
* has to be careful that they are setup for the right model.
* cType
* and x have to be resetup at a restart.
* cType and x
* arrays in a way that is safe in the given context.
*
*
* * Note that in this example we always go through the whole list of variables * and check for each variable whether it is integer or not. This is for * illustrative purposes and to keep things simple. In a production code you * may want to consider using {@link XPRSprob#getMIPEntities()} or * {@link XPRSprob#getDiscreteCols()} to get a list of integer variables. *
*/ public class MostViolated { /** Branch callback that branches on the most fractional variable. * * The actual branching happens in function * {@link #changeBranchObjectEvent(XPRSprob, XPRSbranchobject)} * This function uses the two abstract functions {@link #getCType(XPRSprob)} * and {@link #getX(XPRSprob)} to get the arrays of variable types and * current relaxation values. * We provide different subclasses ofBranchBase that have
* different implementations of these functions, depending on the context
* in which the class can be used.
*/
private abstract static class BranchBase extends AbstractChangeBranchObjectListener {
/** Tolerance used for checking fractionality. */
private final double tolerance;
/** Flag to indicate whether branches are created in terms of
* the original model.
* If they are not created in terms of the original model, they are
* created in terms of the presolved model.
*/
private final boolean isOriginal;
/** Create a new branching callback for prob.
* @param prob The problem on which this callback will be invoked.
* @param isOriginal Flag that indicates whether the data returned
* by {@link #getX(XPRSprob)} and
* {@link #getCType(XPRSprob)} is in terms of the
* original problem.
*/
protected BranchBase(XPRSprob prob, boolean isOriginal) {
tolerance = prob.controls().getMatrixTol();
this.isOriginal = isOriginal;
}
/** Get the relaxation at the current node.
* @param prob The problem on which the callback is invoked.
* @return the relaxation vector for the current node.
*/
protected abstract double[] getX(XPRSprob prob);
/** Get the variable types at the current node.
* @param prob The problem on which the callback is invoked.
* @return the variable type vector at the current node.
*/
protected abstract byte[] getCType(XPRSprob prob);
/** Get the number of MIP threads available for use when solving a problem
* @param prob The problem to query.
* @return the number of MIP threads that may be used when solving the problem.
*/
protected int getNumThreads(XPRSprob prob)
{
int threads = prob.controls().getMIPThreads();
if (threads == -1)
// MIP threads set to -1 means use the Threads control
threads = prob.controls().getThreads();
if (threads == -1)
// If still at the default then optimizer will use as many
// threads as there are cores
threads = prob.attributes().getCoresDetected();
return threads;
}
/** Branch on the most fractional integer.
* This is the function that gets invoked by the optimizer whenever
* a branching decision has to be made.
* @param prob The problem on which the callback is invoked.
* @param oBranch The branch that the optimizer plans to perform.
* @return the branch we want the optimizer to perform (may be
* oBranch or null in which case the
* optimizer will perform oBranch).
*/
public XPRSbranchobject changeBranchObjectEvent(XPRSprob prob, XPRSbranchobject oBranch)
{
// Get the current relaxation
byte[] cType = getCType(prob);
double[] x = getX(prob);
// This is just a safeguard. The two arrays should always have the
// same length.
if (x.length != cType.length)
throw new IllegalArgumentException("Mismatch: " + cType.length + " vs. " + x.length);
if (oBranch == null)
return null;
// Default branch is the original branch.
XPRSbranchobject newBranch = oBranch;
// Find the most fractional variable.
double maxDist = 0.0;
int branchCol = -1;
double branchUp = 0;
double branchDown = 0;
for (int j = 0; j < x.length; ++j) {
if (cType[j] == 'I' || cType[j] == 'B') {
double upDist = Math.ceil(x[j]) - x[j];
double downDist = x[j] - Math.floor(x[j]);
double dist = Math.min(upDist, downDist);
if (downDist > tolerance && upDist > tolerance) {
if (dist > maxDist) {
branchCol = j;
branchUp = Math.ceil(x[j]);
branchDown = Math.floor(x[j]);
maxDist = dist;
}
}
}
}
// If we found a branching candidate then create the new branch
// object for branching on that candidate.
if (branchCol != -1) {
// Create a branch object for the presolved space.
// Wrap registering of the branch into try-catch so that
// we properly delete the object in case of any error.
// If there is no error then the optimizer will take care
// of cleaning up the branch object.
XPRSbranchobject bo = prob.createBranchObject(isOriginal);
try {
// Create the two branches.
bo.addBranches(2);
bo.addBounds(0, 1, new byte[]{'L'}, new int[]{branchCol},
new double[]{branchUp});
bo.addBounds(1, 1, new byte[]{'U'}, new int[]{branchCol},
new double[]{branchDown});
// Prefer the up branch.
bo.setPreferredBranch(0);
// Set a small priority so that the branch is actually used.
bo.setPriority(100);
// Submit the new branch to the solver and clear the
// bo reference since the object is now owned (and cleaned
// up) by the optimizer.
newBranch = bo;
bo = null;
}
finally {
if (bo != null)
bo.close();
}
}
return newBranch;
}
}
/** Branch callback implementation that branches in the original space.
* Instances of this class cache the cType array since the
* types of variables never change in the original model. They also cache
* the x array since the size of the original model never
* changes. The x array is shared between threads, so the
* the class cannot be used for parallel execution of callbacks.
*/
private static final class BranchOriginal extends BranchBase {
private final byte[] cType;
private final double[] x;
/** Create a new instance.
* @param prob The problem that this callback will be used for.
* @param origCType Column types in the original model.
*/
public BranchOriginal(XPRSprob prob, byte[] origCType) {
super(prob, true);
if (prob.controls().getMutexCallBacks() == 0)
throw new IllegalArgumentException("this implementation cannot be used for parallel execution");
cType = origCType;
x = new double[cType.length];
}
/** Get the current relaxation in terms of the original model.
*/
@Override
protected double[] getX(XPRSprob prob) {
prob.getLpSol(x, null, null, null);
return x;
}
/** Get column types in terms of the original model. */
@Override
protected byte[] getCType(XPRSprob prob) {
return cType;
}
}
/** Branch callback implementation that branches in the original space.
* Instances of this class cache the cType array since the
* types of variables never change in the original model. They also cache
* the x array since the size of the original model never
* changes. Each thread has its own x array, so the class
* can be used when callbacks are allowed to run in parallel.
*/
private static final class BranchOriginalMT extends BranchBase {
private final byte[] cType;
private final double[][] threadX;
/** Create a new instance.
* @param prob The problem that this callback will be used for.
* @param origCType Column types in the original model.
*/
public BranchOriginalMT(XPRSprob prob, byte[] origCType) {
super(prob, true);
cType = origCType;
int threads = getNumThreads(prob);
threadX = new double[threads][];
}
/** Get an x vector buffer for the invoking thread. */
private synchronized double[] getThreadX(XPRSprob prob) {
// Get the thread id from the optimizer
int myId = prob.attributes().getMIPThreadID();
// Create (and cache) an x vector buffer
if (threadX[myId] == null)
threadX[myId] = new double[cType.length];
// Return the buffer for this thread
return threadX[myId];
}
/** Get the current relaxation in terms of the original model.
*/
@Override
protected double[] getX(XPRSprob prob) {
double[] x = getThreadX(prob);
prob.getLpSol(x, null, null, null);
return x;
}
/** Get column types in terms of the original model. */
@Override
protected byte[] getCType(XPRSprob prob) {
return cType;
}
}
/** Branch callback implementation that branches in the presolved space.
* Instances of this class assume that there will be no restarts and thus
* cache the cType array. They also cache
* the x array since without restarts the size of the presolved
* model does not change. The x vector is shared between
* threads, so this class cannot be used if callbacks are invoked in
* parallel.
*/
private static final class BranchPresolved extends BranchBase {
private final byte[] cType;
private final double[] x;
/** Create a new callback.
* @param prob Problem for which the callback will be used. The active
* problem referenced by this must be the presolved problem.
*/
public BranchPresolved(XPRSprob prob) {
super(prob, false);
if (prob.controls().getMipRestart() != 0)
throw new IllegalArgumentException("this class is not compatible with restarts");
if (prob.controls().getMutexCallBacks() == 0)
throw new IllegalArgumentException("this implementation cannot be used for parallel execution");
int cols = prob.attributes().getCols();
cType = new byte[cols];
prob.getColType(cType, 0, cols - 1);
x = new double[cols];
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected double[] getX(XPRSprob prob) {
prob.getPresolveSol(x, null, null, null);
return x;
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected byte[] getCType(XPRSprob prob) {
return cType;
}
}
/** Branch callback implementation that branches in the presolved space.
* Instances of this class assume that there will be no restarts and thus
* cache the cType array. They also cache
* the x array since without restarts the size of the presolved
* model does not change. The class uses a different x array
* for each thread and is thus safe to use for parallel callback execution.
*/
private static final class BranchPresolvedMT extends BranchBase {
private final byte[] cType;
private final double[][] threadX;
/** Create a new callback.
* @param prob Problem for which the callback will be used. The active
* problem referenced by this must be the presolved problem.
*/
public BranchPresolvedMT(XPRSprob prob) {
super(prob, false);
if (prob.controls().getMipRestart() != 0)
throw new IllegalArgumentException("this class is not compatible with restarts");
int cols = prob.attributes().getCols();
cType = new byte[cols];
prob.getColType(cType, 0, cols - 1);
int threads = getNumThreads(prob);
threadX = new double[threads][];
}
/** Get an x vector buffer for the invoking thread. */
private synchronized double[] getThreadX(XPRSprob prob) {
// Get the thread id from the optimizer
int myId = prob.attributes().getMIPThreadID();
// Create (and cache) an x vector buffer
if (threadX[myId] == null)
threadX[myId] = new double[cType.length];
// Return the buffer for this thread
return threadX[myId];
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected double[] getX(XPRSprob prob) {
double[] x = getThreadX(prob);
prob.getPresolveSol(x, null, null, null);
return x;
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected byte[] getCType(XPRSprob prob) {
return cType;
}
}
/** Callback implementation that does not cache any arrays.
* The class recreates the cType and x arrays
* at every node and is thus safe to use in any context.
*/
private static final class BranchPresolvedUncached extends BranchBase {
/** Create a new callback.
* @param prob Problem for which the callback will be used.
*/
public BranchPresolvedUncached(XPRSprob prob) {
super(prob, false);
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected double[] getX(XPRSprob prob) {
int cols = prob.attributes().getCols();
double[] x = new double[cols];
prob.getPresolveSol(x, null, null, null);
return x;
}
/** Get the current relaxation in terms of the presolved model.
*/
@Override
protected byte[] getCType(XPRSprob prob) {
int cols = prob.attributes().getCols();
byte[] cType = new byte[cols];
prob.getColType(cType, 0, cols - 1);
return cType;
}
}
/** Run this example.
* Command line arguments are:
*