At any time in the execution of a goal, you may find that, for example, by slightly manipulating the current node subproblem solution, you may construct a solution to your model. Such solutions are called heuristic solutions, and a procedure that generates them is called a heuristic.

Heuristic solutions can be injected into the branch & cut search by creating a solution goal with the method IloCplex::GoalI::SolutionGoal (IloCplex.solutionGoal or Cplex.SolutionGoal). Such a goal can be returned typically as a subgoal of an And goal much like global cut goals.

When ILOG CPLEX executes a solution goal, it does not immediately use the specified solution as a potential new incumbent. The reason is that with goals, part of the model may be specified via global cuts or through specialized branching strategies. Thus the solution needs first to be tested for feasibility with respect to the entire model, including any part of the model specified through goals.

To test whether an injected solution is feasible, ILOG CPLEX first creates a subnode of the current node. This subnode will of course inherit the goal stack from its parent. In addition, the solution goal will push local cuts onto the stack of the subnode such that all variables are fixed to the values of the injected solution.

By processing this subnode as the next node, ILOG CPLEX makes sure that either the solution is feasible with respect to all goals or otherwise it is discarded. Goals that have been executed so far are either reflected as global cuts or by the local cuts that are active at the current node. Thus, if the relaxation remains feasible after the variable fixings have been added, the feasibility of these goals is certain.

If at that point the goal stack is not empty, the goals on the goal stack need to be checked for feasibility as well. Thus by continuing to execute the goals from the goal stack, ILOG CPLEX will either prove feasibility of the solution with respect to the remaining goals or, in case the relaxation becomes infeasible, decide it really is infeasible and discard the solution. The rest of the branch & cut search remains unaffected by all of this.

The benefit of this approach is that your heuristic need not be aware of the entire model including all its parts that might be implemented via goals. Your heuristic can still safely be used, as ILOG CPLEX will make sure of feasibility for the entire model. However, there are some performance considerations to observe. If parts of the model specified with goals are dominant, heuristic solutions you generate might need to be rejected so frequently that you do not get enough payoff for the work of running the heuristic. Also, your heuristic should account for the global and local cuts that have been added at the node where you run your heuristic so that a solution candidate is not rejected right away and the work wasted.