[Previous chapter]

Working with cuts in BCL

---

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

XPRBaddcutarrterm	Add multiple terms to a cut.
XPRBaddcuts	Add cuts to a problem.
XPRBaddcutterm	Add a term to a cut.
XPRBdelcut	Delete a cut definition.
XPRBdelcutterm	Delete a term from a cut.
XPRBgetcutid	Get the classification or identification number of a cut.
XPRBgetcutrhs	Get the RHS value of a cut.
XPRBgetcuttype	Get the type of a cut.
XPRBnewcut	Create a new cut.
XPRBnewcutarrsum	Create a sum cut with individual coefficients (i ci xi).
XPRBnewcutprec	Create a precedence cut (v1+dur v2).
XPRBnewcutsum	Create a sum cut (i xi).
XPRBprintcut	Print out a cut.
XPRBsetcutid	Set the classification or identification number of a cut.
XPRBsetcutmode	Set the cut mode.
XPRBsetcutterm	Set a cut term.
XPRBsetcuttype	Set the type of a cut.

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 */
 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");
 }
 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 */
 XPRBsolve(prob, "g");                   /* Solve the MIP problem */
 ...                                     /* Solution output */
 return 0;     
} 

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
 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;
 }
 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.solve("g");                         // 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 
   {   
    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);
    }
   }
   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.solve("g");                        /* Solve the problem as MIP */
 ...                                   /* Solution output */
 }
}

[Index]

---

If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.