sci.op-research

raskorasko wrote:
> Hi there,
>
> I'm currently working on a network design problem so that I have to solve a
> quite hard IP (not MIP; there are no continuous variable).
>
> I'd like to use a sort of branch-and-cut, with the following modifications:
>
> - When we reach an integer node in the B-C tree, we have to solve some
> auxiliary LP to test whether a global cut can be added to the problem. If we
> find such a cut, we add it to the master problem as a global cut and we solve
> that node again and so on.
>
> - I want the optimizer to consider an integer solution as feasible only if no
> cuts were found solving the auxiliary LP for that node.
>
> Going through the user's manual, I think I've to use two callbacks:
>
> - IloCplex.UserCutCallback : adding my cuts
> - IloCplex.IncumbentCallback : telling the optimize whether to keep an
> integer solution
>
> However, I don't know how to use these classes in my program; reading
> "AdMIPex5.java", I think I could manage the cutcallback but I definitly don't
> know how to incopore the IncumbentCallback.
>
> Thank for any help :) !
>

I have code that does exactly this. It actually requires three
callbacks, subclassed from IncumbentCallback, LazyConstraintCallback and
BranchCallback.

The IncumbentCallback solves the LP. If there is no new cut, it simply
returns (which signals CPLEX to accept the new incumbent). If a new cut
is found, it queues the new cut (the queue is in my code) and calls the
reject() method to tell CPLEX not to accept the incumbent.

The LazyConstraintCallback simply uses the add() method to add any new
cuts in the queue (my code can generate more than one cut at a time),
then clears the queue.

The BranchCallback checks the queue and returns without doing anything
if the queue is empty. If there are cuts in the queue, it uses the
makeBranch() method to create a single child node based on all the new
cuts. In other words, it "separates" the parent node but only creates
one child. Rather than the usual separation process (bounding an
integer variable above/below), it just tacks the new cut(s) onto the
existing node. This callback does *not* clear the queue.

The reason for the BranchCallback is that CPLEX can find a new incumbent
in one of two ways. The obvious one is that the LP relaxation at a
node coughs up an integer-feasible solution. Usually, that signals the
end of exploration for that branch of the tree, since you will not find
a better integer-feasible solution below that node. In our case,
though, it's possible that this solution is not actually feasible, but
another integer-feasible solution to the node LP might exist which is
feasible in the overall problem. So we can't afford to automatically
cut the node. The other way CPLEX can find a candidate incumbent is
using node heuristics. You can turn these off, but I like to leave them
on because I'll take any help I can get solving the bugger. If the new
incumbent comes from a node heuristic, and you cut the node because it's
not really feasible, you run a serious risk of missing something important.

So the bottom line is that if CPLEX finds a candidate incumbent that
fails the external LP test, you're not done with that node. You need to
add the new cut(s) and solve the node LP again. The problem is with the
timing. (I hope I get this next part right; my eyes water every time I
think about it.) The first thing CPLEX does at a node is call the
CutCallback to see if you want to add any cuts. Then it solves the LP
relaxation. If it gets an integer-feasible solution to the LP, it calls
the IncumbentCallback. If the IncumbentCallback rejects the solution,
it calls the CutCallback again (I believe), then solves the LP again.
It keeps doing this until the CutCallback stops adding cuts at the node
and either the LP solution is not integer-feasible (this case includes
the LP becoming infeasible or violating the objective bound) or it gets
a new incumbent that the IncumbentCallback accepts. If the LP is
infeasible or blows the bound, or if a new incumbent is accepted, CPLEX
cuts the node and goes on its merry way. If the LP is feasible,
satisfies the objective bound, but is not integer-feasible, CPLEX then
applies node heuristics (if they're turned on and if it's internal logic
thinks they're worth trying). If the node heuristics don't produce an
integer-feasible solution, CPLEX does its usual branch-and-bound thing.

(Hang on, we're getting to the chase scene.) If the node heuristics
produce a new "incumbent", CPLEX calls the IncumbentCallback, but it
does *not* call the CutCallback again at this node. So if you reject
the solution, CPLEX will cut the node and try to branch ... but where?
This is where the BranchCallback is needed. By creating a child that is
essentially a clone of the parent, but with the new cut(s) added, it
effectively does the same thing that would have happened if CPLEX had
called the CutCallback at the parent node, after you rejected the
heuristic solution. (The BranchCallback is called at every node where
CPLEX branches, but at nodes where you don't have new cuts, it will just
cede control back to CPLEX.)

Hope that made some sense. Incidentally, this is not entirely
CPLEX-specific. I had an earlier version of this code in BCL (the
modeling language for Dash Optimization's XPRESS-MP), and it required
the same three callbacks for more or less the same reason.

HTH,
Paul