Working with cuts in BCL

Topics covered in this chapter:

This chapter describes an extension to BCL that enables the user to define cuts in a similar way to constraints. Although cuts are just additional constraints, they are treated differently by BCL. To start with, they are defined as a separate type (XPRBcut instead of XPRBctr). Besides the type, the following differences between the representation and use of constraints and cuts in BCL may be observed:

• Cuts cannot be non-binding or ranged.
• Cuts are not stored with the problem, this is up to the user.
• Cuts have no names, but they have got an integer indicating their classification or identification number.
• Function XPRBdelcut deletes the cut definition in BCL, but does not influence the problem in Xpress Optimizer if the cut has already been added to it.
• Cuts are added to the problem while it is being solved without having to regenerate the matrix; they can only be added to the matrix (using function XPRBaddcuts) in one of the callback functions of the Xpress Optimizer cut manager (see the `Xpress Optimizer Reference Manual'). Furthermore, they can only be defined on variables that are already contained in the matrix.

The following functions are available in BCL for handling cuts:

Example

The following example shows how the Xpress Optimizer node cut manager callback may be defined to add cuts during the branch and bound search. Function XPRBaddcuts that adds the cuts to the problem in Xpress Optimizer may only be called from one of the cut manager callback functions. Nevertheless, cuts may be defined at any place in the program after BCL has been initialized and the relevant variables have been defined. In order to keep the present example simple, we only create and add cuts at a single node, they are therefore created in the cut manager callback immediately before they are added to the problem. More realistically, cuts may be generated subject to a certain search tree depth or depending on the solution values of certain variables in the current LP-relaxation.

#include <stdio.h>
#include "xprb.h"
#include "xprs.h"

...
XPRBvar start[4];

int XPRS_CC usrcme(XPRSprob oprob, void* vd)
{
 XPRBcut ca[2];
 int num;
 int i=0;
 XPRBprob bprob;

 bprob = (XPRBprob)vd;                   /* Get the BCL problem */
 XPRBbegincb(bprob, oprob);              /* Coordinate BCL and Optimizer */
 XPRSgetintattrib(oprob, XPRS_NODES, &num);
 if(num == 2)                            /* Only generate cuts at node 2 */
 {                                                  /* ca0: s_1+2 <= s_0 */
  ca[0] = XPRBnewcutprec(bprob, start[1], 2, start[0], 2);
  ca[1] = XPRBnewcut(bprob, XPRB_L, 2);  /* ca1: 4*s_2 - 5.3*s_3 <= -17 */
  XPRBaddcutterm(ca[1], start[2], 4);
  XPRBaddcutterm(ca[1], start[3], -5.3);
  XPRBaddcutterm(ca[1], NULL, -17);
  printf("Adding constraints:\n");
  for(i=0;i<2;i++) XPRBprintcut(ca[i]);
  if(XPRBaddcuts(bprob, ca, 2)) printf("Problem with adding cuts.\n");
 }
 XPRBendcb(bprob);                       /* Reset BCL to main problem */
 return 0;                               /* Call this func. once per node */
}

int main(int argc, char **argv)
{
 XPRBprob prob;
 XPRSprob oprob;

 prob=XPRBnewprob("CutExpl");            /* Initialization */
 for(j=0;j<4;j++) start[j] = XPRBnewvar(prob, XPRB_PL, "start", 0, 500);
 ...                      /* Define constraints and an objective function */
 XPRBsetcutmode(prob, 1);                /* Enable the cut mode */
 oprob = XPRBgetXPRSprob(prob);          /* Get the Optimizer problem */
 XPRSsetcbcutmgr(oprob, usrcme, prob);   /* Def. the cut manager callback */
 XPRBmipoptimize(prob, "");              /* Solve the MIP problem */
 ...                                     /* Solution output */
 return 0;
} 

When using the default multi-threaded MIP search it is important to coordinate BCL with the local Optimizer subproblem by surrounding the calls to BCL functions in the cut manager callback by calls to XPRBbegincb and XPRBendcb. Alternatively, you may choose to disable parallelism by setting the XPRS_MIPTHREADS control to 1.

C++ version of the example

With BCL C++, the implementation of the cut example is similar to what we have seen in the previous section since the same Xpress Optimizer functions are used.

#include <iostream>
#include "xprb_cpp.h"
#include "xprs.h"

using namespace std;
using namespace ::dashoptimization;

...
XPRBvar start[NJ];
XPRBprob p("Jobs");                    // Initialize BCL and a new problem

int XPRS_CC usrcme(XPRSprob oprob, void* vd)
{
 XPRBcut ca[2];
 int num;
 int i=0;
 XPRBprob *bprob;

 bprob = (XPRBprob*)vd;                // Get the BCL problem
 bprob->beginCB(oprob);                // Coordinate BCL and Optimizer
 XPRSgetintattrib(oprob, XPRS_NODES, &num);
 if(num == 2)                          // Only generate cuts at node 2
 {
  ca[0] = bprob->newCut(start[1]+2 <= start[0], 2);
  ca[1] = bprob->newCut(4*start[2] - 5.3*start[3] <= -17, 2);
  cout << "Adding constraints:" << endl;
  for(i=0;i<2;i++) ca[i].print();
  if(bprob->addCuts(ca,2)) cout << "Problem with adding cuts." << endl;
 }
 bprob->endCB();                       // Reset BCL to main problem
 return 0;                             // Call this function once per node
}

int main(int argc, char **argv)
{
 XPRSprob oprob;

 for(j=0;j<4;j++) start[j] = p.newVar("start");
 ...                    // Define constraints and an objective function
 oprob = p.getXPRSprob();              // Get Optimizer problem
 p.setCutMode(1);                      // Enable the cut mode
 XPRSsetcbcutmgr(oprob,usrcme,&p);     // Def. the cut manager callback
 p.mipOptimize();                      // Solve the problem as MIP
 ...                                   // Solution output
 return 0;
}

Java version of the example

As is explained in Section Using the Optimizer with BCL Java, before accessing directly the problem held in Xpress Optimizer we need to initialize explicitly the Optimizer Java. The cut manager callback is implemented in Java by the class 'cutMgrListener'.

import java.io.*;
import com.dashoptimization.*;

public class xbcutex
{
 ...
 static XPRBvar[] start;
 static XPRB bcl;

 static class CutMgrCallback implements XPRScutMgrListener
 {
  public int XPRScutMgrEvent(XPRSprob oprob, Object data)
  {
   XPRBprob bprob;
   XPRBcut[] ca;
   int num,i;

   bprob = (XPRBprob)data;             /* Get the BCL problem */

   try
   {
    bprob.beginCB(oprob);              /* Coordinate BCL and Optimizer */
    num = oprob.getIntAttrib(XPRS.NODES);
    if(num == 2)                       /* Only generate cuts at node 2 */
    {
     ca = new XPRBcut[2];
     ca[0] = bprob.newCut(start[1].add(2) .lEql(start[0]), 2);
     ca[1] = bprob.newCut(start[2].mul(4) .add(start[3].mul(-5.3)) .lEql(-17), 2);
     System.out.println("Adding constraints:");
     for(i=0;i<2;i++) ca[i].print();
     bprob.addCuts(ca);
    }
    bprob.endCB();                     /* Reset BCL to main problem */
   }
   catch(XPRSprobException e)
   {
    System.out.println("Error  " + e.getCode() + ": " + e.getMessage());
   }
   return 0;                           /* Call this method once per node */
  }
 }

 public static void main(String[] args) throws XPRSexception
 {
  XPRBprob p;
  XPRSprob oprob;
  CutMgrCallback cb;

  bcl = new XPRB();                    /* Initialize BCL */
  p = bcl.newProb("Jobs");             /* Create a new problem */
  XPRS.init();                         /* Initialize Xpress Optimizer */

  start = new XPRBvar[4];              /* Create 'start' variables */
  for(j=0;j<4;j++) start[j] = p.newVar("start");
  ...                   /* Define constraints and an objective function */

  oprob = p.getXPRSprob();             /* Get Optimizer problem */
  p.setCutMode(1);                     /* Enable the cut mode */
  cb = new CutMgrCallback();
  oprob.addCutMgrListener(cb, p);      /* Def. the cut manager callback */
  p.mipOptimize();                     /* Solve the problem as MIP */
 ...                                   /* Solution output */
 }
}

.NET version of the example

As is explained in Section Using the Optimizer with BCL .NET, before accessing directly the problem held in Xpress Optimizer we need to initialize explicitly the Optimizer .NET. The cut manager callback is implemented in this .NET example by the method usrcme.

using Optimizer;
using BCL;

namespace Examples
{
  public class xbcutex
  {
      static XPRBvar[] start = new XPRBvar[4]; // Start times of jobs

      public static int usrcme(XPRSprob xprsp, object vd)
      {
          XPRBcut[] ca = new XPRBcut[2];
          XPRBprob xprbp = (XPRBprob)vd;       // Get the BCL problem
          xprbp.beginCB(xprsp);                // Coordinate BCL and Optimizer

          int num = xprsp.Nodes;
          if(num == 2)                         // Only generate cuts at node 2
          {
              ca[0] = xprbp.newCut(start[1]+2 <= start[0], 2);
              ca[1] = xprbp.newCut((4*start[2]) - (5.3*start[3]) <= -17, 2);
              System.Console.WriteLine("Adding constraints:");
              for(int i=0;i<2;i++) ca[i].print();
              if(xprbp.addCuts(ca,2) != 0)
                System.Console.WriteLine("Problem with adding cuts.");
          }
          xprbp.endCB();                       // Reset BCL to main problem
          return 0;                            // Call this function once per node
      }

      public static void Main()
      {
         XPRB.init();                          // Initialize BCL
         XPRS.Init();                          // Initialize Optimizer

         XPRBprob xprbp = new XPRBprob("Jobs");// Create a new problem
         for(int j=0;j<4;j++)                  // Create 'start' variables
           start[j] = xprbp.newVar("start");
         ...   // Define constraints and an objective function
         XPRSprob xprsp = p.getXPRSprob();     // Get Optimizer problem
         xprbp.setCutMode(1);                  // Enable the cut mode
         CutmgrCallback del = new CutmgrCallback(usrcme);
         xprsp.AddCutmgrCallback(del, (object)xprbp); // Define the cut manager callback
         xprbp.mipOptimize();                  // Solve the problem as MIP
      }
  }
}