Most member functions of classes in Concert Technology are inline functions that contain an assert statement. This statement asserts that the invoking object and the member function parameters are consistent; in some member functions, the assert statement checks that the handle pointer is non-null. These statements can be suppressed by the macro NDEBUG. This option usually reduces execution time. The price you pay for this choice is that attempts to access through null pointers are not trapped and usually result in memory faults.

Compilation with assert statements will not prevent core dumps by incorrect code. Instead, compilation with assert statements moves the execution of the incorrect code (the core dump, for example) to a place where you can see what is causing the problem in a source code debugger. Correctly written code will never cause one of these Concert Technology assert statements to fail.

CPLEX uses branch & cut search when solving mixed integer programming (MIP) models. The branch & cut search procedure manages a search tree consisting of nodes. Every node represents an LP or QP subproblem to be processed; that is, to be solved, to be checked for integrality, and perhaps to be analyzed further. Nodes are called active if they have not yet been processed. After a node has been processed, it is no longer active. Cplex processes active nodes in the tree until either no more active nodes are available or some limit has been reached.

A branch is the creation of two new nodes from a parent node. Typically, a branch occurs when the bounds on a single variable are modified, with the new bounds remaining in effect for that new node and for any of its descendants. For example, if a branch occurs on a binary variable, that is, one with a lower bound of 0 (zero) and an upper bound of 1 (one), then the result will be two new nodes, one node with a modified upper bound of 0 (the downward branch, in effect requiring this variable to take only the value 0), and the other node with a modified lower bound of 1 (the upward branch, placing the variable at 1). The two new nodes will thus have completely distinct solution domains.

A cut is a constraint added to the model. The purpose of adding any cut is to limit the size of the solution domain for the continuous LP or QP problems represented at the nodes, while not eliminating legal integer solutions. The outcome is thus to reduce the number of branches required to solve the MIP.

As an example of a cut, first consider the following constraint involving three binary (0-1) variables:

20x + 25y + 30z <= 40

That sample constraint can be strengthened by adding the following cut to the model:

1x + 1y + 1z <= 1

No feasible integer solutions are ruled out by the cut, but some fractional solutions, for example (0.0, 0.4, 1.0), can no longer be obtained in any LP or QP subproblems at the nodes, possibly reducing the amount of searching needed.

The branch & cut method, then, consists of performing branches and applying cuts at the nodes of the tree. Here is a more detailed outline of the steps involved.

First, the branch & cut tree is initialized to contain the root node as the only active node. The root node of the tree represents the entire problem, ignoring all of the explicit integrality requirements. Potential cuts are generated for the root node but, in the interest of keeping the problem size reasonable, not all such cuts are applied to the model immediately. If possible, an incumbent solution (that is, the best known solution that satisfies all the integrality requirements) is established at this point for later use in the algorithm. Such a solution may be established either by CPLEX or by a user who specifies a starting solution by means of the Callable Library routine CPXcopymipstart or the Concert Technology method IloCplex::setVectors.

If you are solving a sequence of problems by modifying the problem already in memory and re-solving, then you do not need to establish a starting solution explicitly every time, because for each revised problem, the solution of the previous problem will be retained as a possible starting solution.

When processing a node, CPLEX starts by solving the continuous relaxation of its subproblem. that is, the subproblem without integrality constraints. If the solution violates any cuts, CPLEX may add some or all of them to the node problem and may resolve it, if CPLEX has added cuts. This procedure is iterated until no more violated cuts are detected (or deemed worth adding at this time) by the algorithm. If at any point in the addition of cuts the node becomes infeasible, the node is pruned (that is, it is removed from the tree).

Otherwise, CPLEX checks whether the solution of the node-problem 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. If not, branching will occur, but first a heuristic method may be tried at this point to see if a new incumbent can be inferred from the LP-QP solution at this node, and other methods of analysis may be performed on this node. The branch, when it occurs, is performed on a variable where the value of the present solution violates its integrality requirement. This practice results in two new nodes being added to the tree for later processing.

Each node, after its relaxation is solved, possesses an optimal objective function value Z. At any given point in the algorithm, there is a node whose Z value is better (less, in the case of a minimization problem, or greater for a maximization problem) than all the others. This Best Node value can be compared to the objective function value of the incumbent solution. The resulting MIP Gap, expressed as a percentage of the incumbent solution, serves as a measure of progress toward finding and proving optimality. When active nodes no longer exist, then these two values will have converged toward each other, and the MIP Gap will thus be zero, signifying that optimality of the incumbent has been proven.

It is possible to tell CPLEX to terminate the branch & cut procedure sooner than a completed proof of optimality. For example, a user can set a time limit or a limit on the number of nodes to be processed. Indeed, with default settings, CPLEX will terminate the search when the MIP Gap has been brought lower than 0.0001 (0.01%), because it is often the case that much computation is invested in moving the Best Node value after the eventual optimal incumbent has been located. This termination criterion for the MIP Gap can be changed by the user, of course.

A callback is an object with a main method implemented by a user. This user-written main method is called by the IloCplex algorithm at specific points during optimization.

Callbacks may be called repeatedly at various points during optimization; for each place a callback is called, ILOG CPLEX provides a separate callback class (derived from the class IloCplex::CallbackI). Such a callback class provides the specific API as a protected method to use for the particular implementation.

There are several varieties of callbacks:

• Informational callbacks allow your application to gather information about the progress of MIP optimization without interfering with performance of the search. In addition, an informational callback also enables your application to terminate optimization.
• Query callbacks, also known as diagnostic callbacks, enable your application to retrieve information about the progress of optimization, whether continuous or discrete. The information available depends on the algorithm (primal simplex, dual simplex, barrier, mixed integer, or network) that you are using. For example, a query callback can return the current objective value, the number of simplex iterations that have been completed, and other details. Query callbacks can also be called from presolve, probing, fractional cuts, and disjunctive cuts. Query callbacks may impede performance because the internal data structures that support query callbacks must be updated frequently. Furthermore, query or diagnostic callbacks make assumptions about the path of the search, assumptions that are correct with respect to conventional branch and cut but that may be false with respect to dynamic search. For this reason, query or diagnostic callbacks are not compatible with dynamic search. In other words, CPLEX normally turns off dynamic search in the presence of query or diagnostic callbacks in an application.
• Control callbacks make it possible for you to define your own user-written routines and for your application to call those routines to interrupt and resume optimization. Control callbacks enable you to direct the search when you are solving a MIP in an instance of IloCplex. For example, control callbacks enable you to select the next node to process or to control the creation of subnodes (among other possibilities). Control callbacks are an advanced feature of ILOG CPLEX, and as such, they require a greater degree of familiarity with CPLEX algorithms. Because control callbacks can alter the search path in this way, control callbacks are not compatible with dynammic search. In other words, CPLEX normally turns off dynamic search in the presence of control callbacks in an application.

If you want to take advantage of dynamic search in your application, you should restrict your use of callbacks to the informational callbacks.

If you see a need for query, diagnostic, or control callbacks in your application, you can override the normal behavior of CPLEX by nondefault settings of the parameters MIPSearch, ParallelMode, and Threads. For more details about these parameters and their settings, see the ILOG CPLEX Parameter Reference Manual.

You do not create instances of the class IloCplex::CallbackI; rather, you use one of its child classes to implement your own callback. In order to implement your user-written callbacks with an instance of IloCplex, you should follow these steps:

1. 1. Determine which kind of callback you want to write, and choose the appropriate class for it. The class hierarchy (displayed online when you click Tree on the menu) may give you some ideas about which kind of callback suits your purpose.
2. 2. Derive your own subclass, MyCallbackI, say, from the appropriate predefined callback class.
3. 3. In your subclass of the callback class, use the protected API defined in the base class to implement the main routine of your user-written callback. (All constructors of predefined callback classes are protected; they can be called only from user-written derived subclasses.)
4. 4. In your subclass, implement the method duplicateCallback.
5. 5. Write a function myCallback, say, that creates an instance of your implementation class in the Concert Technology environment and returns it as an IloCplex::Callback handle.
6. 6. Create an instance of your callback class and pass it to the member function IloCplex::use.

There are macros of the form ILOXXXCALLBACKn (for n from 0 to 7) available to facilitate steps 2 through 5, where XXX stands for the particular callback under construction and n stands for the number of arguments that the function written in step 5 is to receive in addition to the environment argument.

You can use one instance of a callback with only one instance of IloCplex. When you use a callback with a second instance of IloCplex, a copy will be automatically created using the method duplicateCallback, and that copy will be used instead.

Also, an instance of IloCplex takes account of only one instance of a particular callback at any given time. That is, if you call IloCplex::use more than once with the same class of callback, the last call overrides any previous one. For example, you can use only one primal simplex callback at a time, or you can use only one network callback at a time; and so forth.

Existing extractables should never be modified within a callback. Temporary extractables, such as arrays, expressions, and range constraints, can be created and modified. Temporary extractables are often useful, for example, for computing cuts.

Example

Here is an example showing you how to terminate optimization after a given period of time if the solution is good enough. It uses one of the predefined macros to facilitate writing a control callback with a timer, a time limit, and a way to recognize a good enough solution.

ILOMIPINFOCALLBACK3(nodeLimitCallback,
                    IloBool, aborted,
                    IloNum,  nodeLimit,
                    IloNum,  acceptableGap)
{
   if ( !aborted  &&  hasIncumbent() ) {
      IloNum objval = getIncumbentObjValue();
      IloNum bound  = getBestObjValue();
      IloNum gap    = fabs(objval - bound) / (1.0 + fabs(bound)) * 100.0;
      if ( getNnodes() > nodeLimit &&
           gap < acceptableGap ) {
         getEnv().out() << endl
                        << "Good enough solution at "
                        << getNnodes() << " nodes, gap = "
                        << gap << "%, quitting." << endl;
         aborted = IloTrue;
         abort();
      }
   }
}

Concert Technology supports column-wise modeling, a technique widely used in the math programming and operations research communities to build a model column by column. In Concert Technology, creating a new column is comparable to creating a new variable and adding it to a set of constraints. You use an instance of IloNumColumn to do so. An instance of IloNumColumn allows you to specify to which constraints or other extractable objects Concert Technology should add the new variable along with its data. For example, in a linear programming problem (an LP), if the new variable will appear in some linear constraints as ranges (instances of IloRange), you need to specify the list of such constraints along with the non zero coefficients (a value of IloNum) for each of them.

You then create a new column in your model when you create a new variable with an instance of IloNumColumn as its parameter. When you create the new variable, Concert Technology will add it along with appropriate parameters to all the extractable objects you have specified in the instance of IloNumColumn.

Instead of building an instance of IloNumColumn, as an alternative, you can use a column expression directly in the constructor of the variable. You can also use instances of IloNumColumn within column expressions.

The following undocumented classes provide the underlying mechanism for column-wise modeling:

• IloAddValueToObj
• IloAddValueToRange

The following operators are useful in column-wise modeling:

• in the class IloRange,

IloAddValueToRange operator() (IloNum value);

• in the class IloObjective,

IloAddValueToObj operator () (IloNum value);

That is, the operator () in extractable classes, such as IloRange or IloObjective, creates descriptors of how Concert Technology should add the new, yet-to-be-created variable to the invoking extractable object.

You can use the operator + to link together the objects returned by operator () to form a column. You can then use an instance of IloNumColumn to build up column expressions within a programming loop and thus save them for later use or to pass them to functions.

Here is how to use an instance of IloNumColumn with operators from IloRange and IloObjective to create a column with a coefficient of 2 in the objective, with 10 in range1, and with 3 in range2. The example then uses that column when it creates the new variable newvar1, and it uses column expressions when it creates newvar2 and newvar3.

    IloNumColumn col = obj(2) + range1(10) + range2(3);
    IloNumVar newvar1(col);
    IloNumVar newvar2(col + range3(17));
    IloNumVar newvar3(range1(1) + range3(3));
    

In other words, given an instance obj of IloObjective and the instances range1, range2, and range3 of IloRange, those lines create the new variables newvar1, newvar2, and newvar3 and add them as linear terms to obj, range1, and range3 in the following way:

    obj: + 2*newvar1 + 2*newvar2
    range1: +10*newvar1 + 10*newvar2 + 1*newvar3
    range2: + 3*newvar1 + 3*newvar2
    range3: + 17*newvar2 +3*newvar3
    

For more information, refer to the documentation of IloNumColumn,IloObjective, and IloRange.

For most Concert applications, you can simply create the extractable objects that you need to build your model, then let their destructors manage the subsequent deletions. However, when memory use is critical to your application, you may need to take control of the deletion of extractable objects. In such cases, you will need a deeper understanding of how ILOG Concert Technology creates and maintains extractable objects. The following guidelines, along with the concept Deletion of Extractable Objects, should help.

1. An expression (that is, an instance of the class IloExpr) is passed by value to an extractable object (an instance of the class IloExtractable). Therefore, you can delete the original expression after passing it by value without affecting the extractable object that received it.

Similarly, instances of IloNumColumn and IloIntSet are passed by value to any predefined Concert Technology objects. More generally, if you have multiple handles passed to Concert objects pointing to an instance of IloExpr, IloNumColumn, or IloIntSet, and you call a method that modifies one of those handles, Concert Technology performs a lazy copy. In other words, it first copies the implementation object for the handle you are modifying and then makes the modification. The other handles pointing to the original implementation object remain unchanged, and your modification has no impact on them.

Lazy copying does not apply to other Concert Technology objects. In general, it is recommended that you avoid using multiple handles to the same object if you do not feel comfortable with lazy copying.

2. A variable (that is, an instance of IloNumVar, IloIntVar, or IloBoolVar) is passed by reference to an extractable object. Therefore, when your Concert application is in linear deleter mode, deleting a variable will remove it from any extractables that received it.

3. An extractable object is passed by reference to a logical constraint (such as IloIfThen) or to a nonlinear expression (such as IloMax). Therefore, you should not delete the original expression after passing it to such functions unless you have finished with the associated model.

Here are some examples to consider in light of these guidelines. The first example illustrates guidelines 2 and 3.

      IloEnv env;
      IloNumVar x(env, 0, IloInfinity, "X");
      IloNumVar y(env, 0, IloInfinity, "Y");
      IloNumVar z(env, 0, IloInfinity, "Z");

      IloExpr e = x + y;

      IloConstraint c1 = (e <= z);
      IloConstraint c2 = (e >= z);
      IloConstraint c3 = IloIfThen(env, c1, c2);
      e.end();           // OK; c1 and c2 use copies of e;
      c1.end();          // BAD IDEA; c3 still references c1
      IloModel m(env);
      m.add (c3);        // c3 is not correctly represented in m.

In that example, since c1 is passed by reference, the call to c1.end raises errors. In contrast, the call to e.end causes no harm because e is passed by value.

The following example illustrates guidelines 1 and 2.

      IloEnv env;
      IloModel model(env);
      IloNumVar y(env, 0, 10, "y");
#ifdef WILLDELETE
      IloNumVar y2 = y;     // second handle pointing to implementation of y
#else
      IloExpr y2 = y;       // first handle pointing to expression 1*y
#endif
      IloConstraint cst = y2 <= 6;
      model.add(cst);
      y2.end();

When y2 is an instance of the class IloNumVar, the call to y2.and will remove y2 from the constraint cst, according to guideline 2.

When y2 is an expression, it will be passed by value to the constraint cst, according to guideline 1. Hence, the call to y2.end will leave cst untouched.

While a thorough understanding of these conventions provides you with complete control over management of the extractable objects in your application, in general, you should simply avoid creating extra handles to extractable objects that can result in unexpected behavior.

In light of that observation, the previous example can be simplified to the following lines:

    IloEnv env;
    IloModel model(env);
    IloNumVar y(env, 0, 10, "y");
    IloConstraint cst = y <= 6;
    model.add(cst);

As a modeling layer, Concert allows the creation and destruction of extractables through the methods IloExtractable::end and IloExtractableArray::endElements. The purpose of these methods is to reclaim memory associated with the deleted objects while maintaining the safest possible Concert environment. In this context, a safe Concert environment is defined by the property that no object points to a deleted object; a pointer to a deleted object is referred to as a dangling pointer in C++.

There exist two paradigms to make sure of the safety of the delete operation. The first, linear mode, comes from math programming; in a Concert application, linear mode is possible only on extractable and other objects used in linear programming. The second, safe generic mode, is stricter and is valid on all Concert extractable objects.

You can access both paradigms by calling IloEnv::setDeleter(IloDeleterMode mode), where mode may be IloLinearDeleterMode or IloSafeDeleterMode.

Linear Mode

To use linear mode, you must either

• call IloEnv::setDeleter(IloLinearDeleterMode), or
• refrain from calling IloEnv::setDeleter, as linear is the default mode.

In linear mode, the following behavior is implemented:

• If a range constraint is deleted, it is removed from the models that contain it.
• If a variable is deleted, its coefficient is set to 0 (zero) in the ranges, expressions, and objectives where it appears. The variable is removed from the special ordered sets of type 1 and 2 (that is, SOS1 and SOS2), as well as from instances of IloConversion where it appears.

Example

This example tests the linear mode deletion of a variable x.

  void TestLinearDeleter() {
    IloEnv env;
    env.out() << "TestLinearDeleter" << endl;
    try {
      IloModel model(env);
      IloNumVar x(env, 0, 10, "x");
      IloNumVar y(env, 0, 10, "y");
      IloConstraint con = (x + y <= 0);
      IloConstraint con2 = y >= 6;
      IloNumVarArray ar(env, 2, x, y);
      IloSOS1 sos(env, ar, "sos");
      model.add(con);
      model.add(con2);
      model.add(sos);
      env.out() << "Before Delete" << endl;
      env.out() << model << endl;
      x.end();
      con2.end();
      env.out() << "After Delete" << endl;
      env.out() << model << endl;    
    } catch (IloException& e) {
      cout << "Error : " << e << endl;
    }
    env.end();
  }
  

The example produces the following output:

  TestLinearDeleter
  Before Delete
  IloModel model0 = {
  IloRange rng3(    1 * x + 1 * y ) <= 0
  
  IloRange rng46 <=(    1 * y )
  
  IloSOS1I (sos)
    _varArray [x(F)[0..10], y(F)[0..10]]
    _valArray []
      
  }
  
  After Delete  
  IloModel model0 = {
  IloRange rng3(    1 * y ) <= 0
  
  IloSOS1I (sos)
    _varArray [y(F)[0..10]]
    _valArray []
  }

Safe Generic Mode

To use safe generic mode, you must:

• call IloEnv::setDeleter(IloSafeDeleterMode), and
• add #include <ilconcert/ilodeleter.h> to your application.

In this mode, the environment builds a dependency graph between all extractable objects. This graph contains all extractable objects created

• after a call to IloEnv::setDeleter(IloSafeDeleterMode) and
• before a call to IloEnv::unsetDeleter.

Objects not managed by this dependency graph are referred to here as "nondeletable". An attempt to delete a nondeletable object will throw an exception.

It is recommended that you create this graph just after the creation of the environment and that you refrain from using IloEnv::unsetDeleter because building an incomplete dependency graph is very error prone and should only be attempted by advanced users. A clear example of this incomplete graph is the separation of a model between a nondeletable base model and deletable extensions of this base model.

Calling IloExtractable::end on extractable xi will succeed only if no other extractable object uses extractable xi. If this is not the case, a call to IloExtractable::end will throw an exception IloDeleter::RequiresAnotherDeletionException indicating which extractable object uses the extractable object that you want to delete.

Example

This example shows an attempt to delete one extractable object that is used by another.

  
  void TestSafeDeleter() {
    IloEnv env;
    env.out() << "TestSafeDeleter" << endl;
    env.setDeleter(IloSafeDeleterMode);
    try {
      IloModel model(env);
      IloNumVar x(env, 0, 10);
      IloNumVar y(env, 0, 10);
      IloConstraint con = (x + y <= 0);
      try {
        x.end();
      } catch (IloDeleter::RequiresAnotherDeletionException &e) {
        cout << "Caught " << e << endl;
        e.getUsers()[0].end();
        e.end();
      }
      x.end();
    } catch (IloException& e) {
      cout << "Error : " << e << endl;
    }
    env.unsetDeleter();
    env.end();
  }
  

The example produces the following output:

  TestSafeDeleter
  Caught You cannot end x1(F)[0..10] before IloRange rng3(  1 * x1 + 1 * x2  ) <= 0
  

To address this situation, you should use the method IloExtractableArray::endElements. With this method, all extractable objects in the array are deleted one after another. Thus, if an extractable object is used by another extractable object and this other extractable object is deleted before the first one, the system will not complain and will not throw an exception.

Example

This example illustrates the use of the endElements method

  
  void TestSafeDeleterWithArray() {
    IloEnv env;
    env.out() << "TestSafeDeleterWithArray" << endl;
    env.setDeleter(IloSafeDeleterMode);
    try {
      IloModel model(env);
      IloNumVar x(env, 0, 10);
      IloNumVar y(env, 0, 10);
      IloConstraint con = (x + y <= 0);
      IloExtractableArray ar(env, 2, con, x);
      ar.endElements();
    } catch (IloException& e) {
      cout << "Error : " << e << endl;
    }
    env.unsetDeleter();
    env.end();
  }
  

That example will not throw an exception.

An exception is thrown; it is not allocated in a Concert Technology environment; it is not allocated on the C++ heap. It is not necessary for you as a programmer to delete an exception explicitly. Instead, the system calls the constructor of the exception to create it, and the system calls the destructor of the exception to delete it.

When exceptions are enabled on a platform that supports C++ exceptions, an instance of a class of Concert Technology is able to throw an exception in case of error. On platforms that do not support C++ exceptions, it is possible for Concert Technology to exit in case of error.

Programming Hint: Throwing and Catching Exceptions

Exceptions are thrown by value. They are not allocated on the C++ heap, nor in a Concert Technology environment. The correct way to catch an exception is to catch a reference to the error (indicated by the ampersand &), like this:

catch(IloException& oops);

Concert Technology offers classes for you to design a model of your problem. You can then invoke an algorithm to extract information from your model to solve the problem. In this context, an algorithm is an instance of a class such as IloCplex, documented in the ILOG CPLEX Reference Manual, or IloSolver, documented in the ILOG Solver Reference Manual.

For details about what each algorithm extracts from a model, see the reference manual documenting that algorithm. For example, the ILOG CPLEX Reference Manual lists precisely which classes of Concert Technology are extracted by an instance of IloCplex. In general terms, an instance of IloCplex extracts a model as rows and columns, where the columns indicate decision variables of the model. Also in general terms, an instance of IloSolver extracts an instance of a class whose name begins Ilo to a corresponding instance of a class whose name begins Ilc. For example, an instance of IloAllDiff is extracted by IloSolver as an instance of IlcAllDiff.

Goals can be used to control the branch and cut search in IloCplex . Goals are implemented in the class IloCplex::GoalI . The class IloCplex::Goal is the handle class. That is, it contains a pointer to an instance of IloCplex::GoalI along with accessors of objects in the implmenetation class.

To implement your own goal, you need to subclass IloCplex::GoalI and implement its virtual member functions execute and duplicateGoal. The method execute controls the branch & cut search. The method duplicateGoal creates a copy of the invoking goal object to be used for parallel branch & cut search. Implementing your goal can be greatly simplified if you use one of the macros ILOCPLEXGOALn.

Every branch & cut node maintains a goal stack, possibly containing IloCplex::GoalI objects. After IloCplex solves the relaxation of a node, it pops the top goal from the goal stack and calls its method execute. There are several types of goals:

• If OrGoal is executed, IloCplex will create child nodes. Each of the child nodes will be initialized with a copy of the goal stack of the current node. Then, for each child node, the specified goal in the OrGoal is pushed onto the corresponding goal stack of the child node. Finally, the current node is deleted. (See IloCplex#GoalI::OrGoal for a more detailed discussion.)
• If a cut goal is executed, the constraint will be added to the current node relaxation. Constraint goals are provided to represent both local and global cuts. Local cut goals are conventionally used to express branching.
• If AndGoal is executed, its subgoals are simply pushed onto the stack. (See IloCplex::GoalI::AndGoal for a more detailed discussion.)
• If IloCplex::GoalI::FailGoal is executed, IloCplex will prune the current node; that is, it will discontinue the search at the current node. IloCplex will continue with another node if there is one still available in the tree.
• If IloCplex::GoalI::SolutionGoal is executed, IloCplex will attempt to inject a user-provided solution as a new incumbent. Before ILOG CPLEX accepts the injected solution, it first tests whether the injected solution is feasible with respect to the model and goals.
• When ILOG CPLEX executes any other goal, the returned goal is simply pushed onto the stack.

IloCplex continues popping goals from the goal stack until OrGoal or FailGoal is executed, or until the stack becomes empty; in the case of an empty stack, it will continue with a built-in search strategy.

The predefined goals OrGoal and AndGoal allow you to combine goals. AndGoal allows you to execute different goals at one node, while OrGoal allows you to execute different goals on different, newly created nodes. A conventional use of these two goals in a return statement of a user-written goal looks like this:

 
return AndGoal ( OrGoal (branch1, branch2), this);

This AndGoal first pushes this (the goal currently being executed) onto the goal stack, and then it pushes the OrGoal. Thus the OrGoal is on top of the stack and will be executed next. When the OrGoal executes, it creates two new nodes and copies the remaining goal stack to both of them. Thus both new nodes will have this goal on top of the goal stack at this point. Then the OrGoal proceeds to push branch1 onto the goal stack of the first child node and branch2 onto the goal stack of the second goal child node. Conventionally, branch1 and branch2 contain cut goals, so by executing branch1 and branch2 at the respective child nodes, the child nodes will be restricted to represent smaller subproblems than their parent. After branch1 and branch2 have been executed, this is on top of the node stack of both child nodes; that is, both child nodes will continue branching according to the same rule. In summary, this example creates the branches branch1 and branch2 and continues in both branches to control the same search strategy this.

To perform a search using a goal, you need to solve the extracted model by calling the method IloCplex::solve(goal) with the goal to use as an argument instead of the standard IloCplex::solve. The method solve(goal) simply pushes the goal onto the goal stack of the root node before calling the standard solve.

See Also

IloCplex::Goal and IloCplex::GoalI

Most Concert Technology entities are implemented by means of two classes: a handle class and an implementation class, where an object of the handle class contains a data member (the handle pointer) that points to an object (its implementation object) of the corresponding implementation class. As a Concert Technology user, you will be working primarily with handles.

As handles, these objects should be passed in either of these ways:

• as const by value (when no change is involved);
• by reference (when the function to which the handle is passed changes the implementation of that handle).

They should be created as automatic objects, where "automatic" has the usual C++ meaning.

Member functions of a handle class correspond to member functions of the same name in the implementation class.

When you problem is infeasible, ILOG CPLEX offers tools to help you diagnose the cause or causes of infeasibility in your model and possibly repair it: IloCplex::refineConflict and IloCplex::feasOpt.

Given an infeasible model, the conflict refiner can identify conflicting constraints and bounds within the model to help you identify the causes of the infeasibility. In this context, a conflict is a subset of the constraints and bounds of the model which are mutually contradictory. The conflict refiner first examines the full infeasible model to identify portions of the conflict that it can remove. By this process of refinement, the conflict refiner arrives at a minimal conflict. A minimal conflict is usually smaller than the full infeasible model and thus makes infeasibility analysis easier. To invoke the conflict refiner, call the method IloCplex::refineConflict.

If a model happens to include multiple independent causes of infeasibility, then it may be necessary for the user to repair one such cause and then repeat the diagnosis with further conflict analysis.

A conflict does not provide information about the magnitude of change in data values needed to achieve feasibility. The techniques that ILOG CPLEX uses to refine a conflict include or remove constraints or bounds in trial conflicts; the techniques do not vary the data in constraints nor in bounds. To gain insight about changes in bounds on variables and constraints, consider the FeasOpt feature.

Also consider FeasOpt for an approach to automatic repair of infeasibility.

Refining a conflict in an infeasible model as defined here is similar to finding an irreducibly inconsistent set (IIS), an established technique in the published literature, long available within ILOG CPLEX. Both tools (conflict refiner and IIS finder) attempt to identify an infeasible subproblem in an infeasible model. However, the conflict refiner is more general than the IIS finder. The IIS finder is applicable only in continuous (that is, LP) models, whereas the conflict refiner can work on any type of problem, even mixed integer programs (MIP) and those containing quadratic elements (QP or QCP).

Also the conflict refiner differs from the IIS finder in that a user may organize constraints into one or more groups for a conflict. When a user specifies a group, the conflict refiner will make sure that either the group as a whole will be present in a conflict (that is, all its members will participate in the conflict, and removal of one will result in a feasible subproblem) or that the group will not participate in the conflict at all.

See the method IloCplex::refineConflictExt for more about groups.

A user may also assign a numeric preference to constraints or to groups of constraints. In the case of an infeasible model having more than one possible conflict, preferences guide the conflict refiner toward identifying constraints in a conflict as the user prefers.

In these respects, the conflict refiner represents an extension and generalization of the IIS finder.

Alternatively, after a model have been proven infeasible, IloCplex::feasOpt performs an additional optimization that computes a minimal relaxation of the constraints over variables, of the bounds on variables, and of the righthand sides of constraints to make the model feasible. The parameter FeasOptMode lets you guide feasOpt in its computation of this relaxation.

IloCplex::feasOpt works in two phases. In its first phase, it attempts to minimize its relaxation of the infeasible model. That is, it attempts to find a feasible solution that requires minimal change. In its second phase, it finds an optimal solution among those that require only as much relaxation as it found necessary in the first phase.

Your choice of values for the parameter FeasOptMode indicates two aspects to ILOG CPLEX:

• whether to stop in phase one or continue to phase two:
  • Min means stop in phase one with a minimal relaxation.
  • Opt means continue to phase two for an optimum among those minimal relaxations.
• how to measure the minimality of the relaxation:
  • Sum means ILOG CPLEX should minimize the sum of all relaxations
  • Inf means that ILOG CPLEX should minimize the number of constraints and bounds relaxed.

The possible values of FeasOptMode are documented in the method IloCplex::feasOpt.

The status of the bounds and constraints of a relaxation returned by a call of IloCplex::feasOpt are documented in the enumeration IloCplex::Status.

For ILOG CPLEX, a logical constraint combines linear constraints by means of logical operators, such as logical and, logical or, negation (that is, not), conditional statements (that is, if ... then ...) to express complex relations between linear constraints. ILOG CPLEX can also handle certain logical expressions appearing within a linear constraint. One such logical expression is the minimum of a set of variables. Another such logical expression is the absolute value of a variable.

In C++ applications, the class IloCplex can extract modeling objects to solve a wide variety of MIPs and LPs. Under some conditions, a problem expressed in terms of logical constraints may be equivalent to a continuous LP, rather than a MIP. In such a case, there is no need for branching during the search for a solution. Whether a problem (or parts of a problem) represented by logical terms can be modeled and solved by LP depends on the shape of those logical terms. In this context, shape means convex or concave in the formal, mathematical sense.

For more about convexity, see that topic in the ILOG CPLEX User's Manual.

In fact, the class IloCplex can extract logical constraints as well as some logical expressions. The logical constraints that IloCplex can extract are these:

• IloAnd which can also be represented by the overloaded operator &&;
• IloOr which can also be represented by the overloaded operator ||;
• IloDiff which can also be represented by the overloaded operator !=;
• IloNot, negation, which can also be represented by the overloaded operator !;
• IloIfThen
• == (that is, the equivalence relation)
• != (that is, the exclusive-or relation)

For examples of logical constraints in ILOG CPLEX, see the ILOG CPLEX User's Manual.

Normalizing is sometimes known as reducing the terms of a linear expression.

Linear expressions consist of terms made up of constants and variables related by arithmetic operations; for example, x + 3y is a linear expression of two terms consisting of two variables. In some expressions, a given variable may appear in more than one term, for example, x + 3y +2x. Concert Technology has more than one way of dealing with linear expressions in this respect, and you control which way Concert Technology treats expressions from your application.

In one mode, Concert Technology analyzes linear expressions that your application passes it and attempts to reduce them so that a given variable appears in only one term in the linear expression. This is the default mode. You set this mode with the member function IloEnv::setNormalizer(IloTrue).

In the other mode, Concert Technology assumes that no variable appears in more than one term in any of the linear expressions that your application passes to Concert Technology. We call this mode assume normalized linear expressions. You set this mode with the member function IloEnv::setNormalizer(IloFalse).

In classes such as IloExpr or IloRange, there are member functions that check the setting of the member function IloEnv::setNormalizer in the environment and behave accordingly. The documentation of those member functions indicates how they behave with respect to normalization.

When you set IloEnv::setNormalizer(IloFalse), those member functions assume that no variable appears in more than one term in a linear expression. This mode may save time during computation, but it entails the risk that a linear expression may contain one or more variables, each of which appears in one or more terms. Such a case may cause certain assertions in member functions of a class to fail if you do not compile with the flag -DNDEBUG.

By default, those member functions attempt to reduce expressions. This mode may require more time during preliminary computation, but it avoids of the possibility of a failed assertion in case of duplicates.

For more information, refer to the documentation of IloEnv,IloExpr, and IloRange.

You may modify the elements of a model in Concert Technology. For example, you may add or remove constraints, change the objective, add or remove columns, add or remove rows, and so forth.

In order to maintain consistency between a model and the algorithms that may use it, Concert Technology notifies algorithms about changes in the objects that the algorithms have extracted. In this manual, member functions that are part of this notification system are indicated like this:

Some problems are most naturally represented by constraints over functions that are not purely linear but consist of linear segments. Such functions are sometimes known as piecewise linear.

The treatment of models that are unbounded involves a few subtleties. Specifically, a declaration of unboundedness means that ILOG CPLEX has determined that the model has an unbounded ray. Given any feasible solution x with objective z, a multiple of the unbounded ray can be added to x to give a feasible solution with objective z-1 (or z+1 for maximization models). Thus, if a feasible solution exists, then the optimal objective is unbounded. Note that ILOG CPLEX has not necessarily concluded that a feasible solution exists. Users can call the methods IloCplex::isPrimalFeasible and IloCplex::isDualFeasible to determine whether ILOG CPLEX has also concluded that the model has a feasible solution.