sci.op-research

Thank you very much, that looks interesting (I'll have a more proper look
tomorrow :) ).
By the way, could you give me your code (as I'm really new with specific
branch-and-cut that might help), especially if it is in Java.

Thank's again !!!

Paul Rubin wrote:
>> Hi there,
>>
>[quoted text clipped - 22 lines]
>>
>> 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

--
Message posted via http://www.mathkb.com