Injecting Solutions
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 method IloCplex::GoalI::SolutionGoal() (IloCplex.solutionGoal()). Such a goal can be returned typically as a subgoal of And goal much like global cut goals.
When IloCplex 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 if an injected solution is feasible with all goals the execute() method of a solution goal IloCplex 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) IloCplex ensures that the solution is feasible with respect to all goals, or is otherwise 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 assured.
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 IloCplex will either prove feasibility of the solution with respect to the remaining goals or, in case the relaxation becomes infeasible, determine it to be really infeasible and discard the solution. The rest of the branch & cut search remain 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 IloCplex will ensure 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.
