Goals allow you to take control of the branch & cut search procedure used by IloCplex to solve MIP problems. To help you understand how to use goals with IloCplex, this section reviews how this procedure works.

The IloCplex branch & cut search procedure manages a search tree consisting of nodes. Every node represents a subproblem to be solved, and the root node of the tree represents the entire problem. Nodes are called active if they have not yet been processed.

The tree is first initialized to contain the root node as the only active node. IloCplex processes active nodes from the tree until either no more active nodes are available or some limit has been reached. Once a node has been processed, it is no longer active.

When processing a node, IloCplex starts by solving the continuous relaxation of its subproblem - that is, the subproblem without integrality constraints. If the solution violates any cuts, IloCplex adds them to the node problem and re-solves. This is iterated until no more violated cuts are found by IloCplex. If at any point the relaxation becomes infeasible, the node is pruned, that is, it is removed from the tree.

To solve the node problem, IloCplex checks whether the solution satisfies the integrality constraints. If so, and if its objective value is better than that of the current incumbent, the solution of the node problem is used as the new incumbent. Otherwise, IloCplex splits the node problem into one or two smaller subproblems, typically by branching on a variable that violates its integrality condition. These subproblems are added to the tree as active nodes and the current node is deactivated.

The primary use of goals is to take control of these last steps, namely the integer-feasibility test and the creation of subproblems. However, as discussed later, goals also allow you to add local and global cuts.

In C++, goals are implemented in objects of type IloCplex::GoalI (having handle class IloCplex::Goal). In Java, goals are implemented in objects of type IloCplex.Goal (and there are no handle classes). The method IloCplex::GoalI::execute (IloCplex.Goal.execute) is where all the control is implemented. This method is called by IloCplex after a node relaxation has been solved and all cuts have been added. Invoking method execute of a goal is often referred to as executing a goal. When the method execute is executed, other methods of the class IloCplex::GoalI (IloCplex.Goal) can be called to query information about the current node problem and the solution of its relaxation.

Typically, the implementation of method execute will perform the following steps:

IloCplex provides a selection of special goals that can be used to specify how to proceed:

Since IloCplex::GoalI::OrGoal (IloCplex.or) and IloCplex::GoalI::AndGoal (IloCplex.and) take other goals as parameters, goals can be combined into aggregate goals. In fact, this is how goals are typically used for specifying a branching strategy. A typical return goal of a user-written execute method for C++ looks like this:

return AndGoal(OrGoal(var <= IloFloor(val), var >= IloFloor(val)+1), this);

and for Java looks like this:

return cplex.and(cplex.or(cplex.leGoal(var, Math.floor(val)),
                          cplex.geGoal(var, Math.floor(val)+1)), this);

For the C++ case, note that since this statement would be called from the execute method of a subclass of IloCplex::GoalI, the full method name IloCplex::GoalI::OrGoal can be abbreviated to OrGoal (and likewise AndGoal).

This return statement returns an And goal that first executes the Or goal and then the current goal itself specified by the this parameter. When the Or goal is executed next, it will create two subnodes. In the first subnode, the first local cut goal representing (where denotes the floor of val) will be executed, thus adding the constraint for the subtree of this node. Similarly, the second subnode will be created, and when executing its constraint goal the constraint var will be added for the subtree. this is then executed on each of the nodes that have just been created; the same goal is used for both subtrees. Further details on how goals are processed will be discussed later.

Here is an example that precedes further discussions of goals. This example is available as file ilogoalex1.cpp in the examples/src subdirectory of your ILOG CPLEX distribution. The equivalent Java version can be found as GoalEx1.java in the same location.

// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/ilogoalex1.cpp
// Version 9.0    
// --------------------------------------------------------------------------
//  Copyright (C) 1999-2003 by ILOG.
//  All Rights Reserved.
//  Permission is expressly granted to use this example in the
//  course of developing applications that use ILOG products.
// --------------------------------------------------------------------------
//
// ilogoalex1.cpp - A simple goal example.
//
//                  Create a branch goal that chooses the variable
//                  with the largest objective from amongst those
//                  with the largest integer infeasibility.
//

#include <ilcplex/ilocplex.h>

ILOSTLBEGIN

static void usage (const char *progname);

// Branch on var with largest objective coefficient
// among those with largest infeasibility

ILOCPLEXGOAL1(MyBranchGoal, IloNumVarArray, vars) {
   IloNumArray x; 
   IloNumArray obj;
   IntegerFeasibilityArray feas;

   x    = IloNumArray(getEnv());
   obj  = IloNumArray(getEnv());
   feas = IntegerFeasibilityArray(getEnv());
   getValues(x, vars);
   getObjCoefs(obj, vars);
   getFeasibilities(feas, vars);

   IloInt bestj  = -1;
   IloNum maxinf = 0.0;
   IloNum maxobj = 0.0;
   IloInt cols = vars.getSize();
   for (IloInt j = 0; j < cols; ++j) {
      if ( feas[j] == Infeasible ) {
         IloNum xj_inf = x[j] - IloFloor (x[j]);
         if ( xj_inf > 0.5 )
            xj_inf = 1.0 - xj_inf;
         if ( xj_inf >= maxinf                             &&
             (xj_inf > maxinf || IloAbs (obj[j]) >= maxobj)  ) {
            bestj  = j;
            maxinf = xj_inf;
            maxobj = IloAbs (obj[j]);
         }
      }
   }

   IloCplex::Goal res;
   if ( bestj >= 0 ) {
      res = AndGoal(OrGoal(vars[bestj] >= IloFloor(x[bestj])+1,
                           vars[bestj] <= IloFloor(x[bestj])),
                    this);
   }

   x.end();
   obj.end();
   feas.end();

   return res;
}


int
main (int argc, char **argv)
{
   IloEnv   env;
   try {
      IloModel model(env);
      IloCplex cplex(env);
    
      if ( argc != 2 ) {
         usage (argv[0]);
         throw(-1);
      }
    
      IloObjective   obj;
      IloNumVarArray var(env);
      IloRangeArray  rng(env);
      cplex.importModel(model, argv[1], obj, var, rng);
    
      cplex.extract(model); 
      cplex.solve(MyBranchGoal(env, var));
    
      IloNumArray vals(env);
      cplex.getValues(vals, var);
      cout << "Solution status = " << cplex.getStatus() << endl;
      cout << "Solution value  = " << cplex.getObjValue() << endl;
      cout << "Values          = " << vals << endl;
   }
   catch (IloException& e) {
      cerr << "Concert exception caught: " << e << endl;
   }

   env.end();

   return 0;
}


static void usage (const char *progname)
{
   cerr << "Usage: " << progname << " filename" << endl;
   cerr << "   where filename is a file with extension " << endl;
   cerr << "      MPS, SAV, or LP (lower case is allowed)" << endl;
   cerr << " Exiting..." << endl;
}

This example shows how to implement and use a goal for controlling the branch strategy used by IloCplex. As discussed, goals are implemented as subclasses of class IloCplex::GoalI (IloCplex.Goal). The C++ version of that example uses the macro

instead. This macro defines two things, class MyBranchGoalI and the function

The class MyBranchGoalI is defined as a subclass of class IloCplex::GoalI (IloCplex.Goal) and has a private member IloNumVarArray vars. The function MyBranchGoal creates an instance of class MyBranchGoalI, initializes the member vars to the parameter vars passed to the function, and returns a handle to the new goal object. The curly brackets "{ ... }" following the macro enclose the implementation of method MyBranchGoalI::execute containing the actual code of the goal.

The use of the macro is very convenient as the amount of user code is equivalent to the amount for defining a function, but with a slightly unusual syntax. IloCplex provides 7 such macros that can be used for defining goals with 0 to 6 private members. If more than 6 members are needed, IloCplex::GoalI (IloCplex.Goal) must be subclassed by hand.

Since the Java programming language does not provide macros, a subclass of IloCplex.Goal must always be implemented by hand. In this example, this class is called MyBranchGoal and there is no helper function for creating an instance of that class (as the macro does in the case of C++).

The goal is then used for solving the extracted node by calling:

for C++, or for Java:

instead of the usual cplex.solve. The rest of the main function contains nothing new and will not be discussed any further.

In the implementation of the goal, or more precisely its method execute, start by declaring and initializing some arrays. These arrays are then used by methods of class IloCplex::GoalI (IloCplex.Goal) to query information about the node subproblem and the solution of its relaxation. The method getValues is used to query the solution values for the variables in vars, method getObjCoefs is used to query the linear objective function coefficients for these variables, and method getFeasibilities is used to query feasibility statuses for them. The feasibility status of a variable indicates whether IloCplex considers the current solution value of the variable to be integer feasible or not. IloCplex::GoalI (IloCplex.Goal) provides a wealth of other query methods. For details, see the ILOG CPLEX Reference Manual.

Once you have gathered information about the variables, their objective coefficients, and their current feasibility statuses, compute the index of an integer infeasible variable in vars that has the largest objective coefficients among the variables with largest integer infeasibility. That index is recorded in variable bestj.

Then create a new goal handle object res. By default, this is initialized to an empty goal. However, if an integer infeasible variable was found among those in vars, then variable bestj will be 0 and a nonempty goal will be assigned to res:

res = AndGoal(OrGoal(vars[bestj] >= IloFloor(x[bestj])+1,
                     vars[bestj] <= IloFloor(x[bestj])),
                     this);

This goal creates two branches, one for and one for and continues branching in both subtrees with the same goal this. Finally, call method end for all temporary arrays and return goal res.

Since Java objects are garbage collected, there is no need for variable res. Instead, depending on the availability of an integer infeasible variable, the null goal is returned or the returned goal is created in the return statement itself:

return cplex.and(cplex.or(cplex.geGoal(_vars[bestj], 
Math.floor(x[bestj]))+1,
                          cplex.leGoal(_vars[bestj], 
Math.floor(x[bestj]))),
                 this);