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, we review 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 feasibility test and the creation of subproblems. However, as we will discuss later, goals also allow you to add local and global cuts.

The discussion of the details of using goals will be presented mainly in terms of the C++ library. The Java library follows the same design and is thus equivalent. In cases where a difference between the C++ and Java API needs to be observed, the point will be raised. Where the difference is only in syntax, the Java syntax will be mentioned in parentheses following the C++ syntax

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 method execute() is executed, the member functions of 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:

Check feasibility. An interesting possibility here is that the feasibility check may include more than verifying integrality of the solution. This allows you to enforce constraints that could not reasonably be expressed using linear constraints through cuts or branching. In other words, this allows you to use goals in a way that makes them part of the model to be solved. Such a use is common in Constraint Programming, but it is less frequently used in Mathematical Programming.
Optionally find local or global cuts to be added. Local cuts will be respected only for the subtree below the current node, whereas global cuts will be enforced for all nodes from then on.
Optionally construct a solution and pass it to IloCplex.
Instruct IloCplex how to proceed. Instructing IloCplex how to proceed is done through the return value of method execute(), which is another goal. IloCplex simply continues by executing this goal.

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

• Method IloCplex::GoalI::OrGoal() (IloCplex.or()) returns a goal that creates subnodes of the current node. This function takes at least 2 and up to 6 goals as parameters. For each of its parameters, the Or goal will create a subnode in such a way that when processing that subnode, the corresponding goal will be executed. Once the goal has been executed, the current node is immediately deactivated.
• Method IloCplex::GoalI::AndGoal() (IloCplex.and()) also takes goals as parameters. It returns a goal that will cause IloCplex to execute the goals passed as parameters in the order of the parameters.
• Method IloCplex::GoalI::FailGoal() (IloCplex.failGoal()) creates a goal that causes IloCplex to prune the current node. In other words, it discontinues the search at the node where the goal is executed. IloCplex will continue with another active node from the tree, if available.
• Class IloCplex::Goal has constructors that take an IloRange object or an IloRangeArray (IloRange[])object as parameters. When one of these constructors is used, a local cut goal is created. Local cut goals add local cuts to the node where they are executed. To create local cut goals with the Java API, use method IloCplex.constraintGoal() or if more convenient, one of the methods IloCplex.leGoal(), IloCplex.geGoal() or IloCplex.eqGoal().
• The 0 (null) goal, or empty goal, that is, an IloCplex::Goal handle object with 0 implementation pointer can also be returned by method IloCplex::GoalI::execute(). In most cases this will instruct IloCplex to take over control of the branch & cut search with its built-in strategies.

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.

We will discuss the execution of goals in the branch & cut search tree in more detail below. Before doing so, let us go through a first example. 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 8.1 // -------------------------------------------------------------------------- // Copyright (C) 1999-2002 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 we discussed, goals are implemented as subclasses of class IloCplex::GoalI (IloCplex.Goal). In the C++ version of the example listed above we do so by using the macro

ILOCPLEXGOAL1(MyBranchGoal, IloNumVarArray, vars)

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

IloCplex::Goal MyBranchGoal(IloEnv env, IloNumVarArray vars);

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 braces "{ ... }" 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 programing 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 we do not provide a 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:

cplex.solve(MyBranchGoal(env, var));

for C++, or for Java:

cplex.solve(new MyBranchGoal(var));

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(), we 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. 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 we have gathered information about the variables, their objective coefficients, and their current feasibility statuses, we 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 we 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 variable bestj will be 0 and we assign a non-empty goal to res:

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

This goal creates two branches, one for vars[bestj]

and one for vars[bestj]

+ 1 and continues branching in both subtrees with the same goal this. Finally, we 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);