sci.op-research

Hi Paul,
I'm implementing my algorithm with your help. Thank you so much for your
replies.
I just have a simple question :

- in the branch callback, I will just create a new branch with a "null"
IloRange as argument, because I want my cuts to be added as global cuts,
which is done by the lazy cut callback ?

By the way, I'd love to speak more about the project your working on,
especially because I have seen very few such algorithms in the litterature
whereras it seems to me (young and naive phd student ;-) ) that they might be
very efficient.

Here is my email: mposs [at] ulb [dot] ac [dot] be

Send my yours and we could chat a bit more about that subject if you're
interested.

Thank's again for your help, you prevented me from writing another branch-and-
cut from scratch :-).

Michael.

Paul Rubin wrote:
>> Ok ok ... I think your previous answer should be enough.
>> However I wonder why the LazyCutCallback alone is not enough?
>> Shouldn't it help us to add feasibility cut to a branch-and-cut (in
>> opposition to strengthening cuts) ?
>> The problem might be that it consider integer solution as feasible before
>> testing new cuts, is it ?
>
>When CPLEX enters a node:
>
>1. Any global cuts, and any local cuts from ancestor nodes, are applied.
>
>2. Any cuts used in the separation process that created the node (via
>makeBranch) are applied.
>
>3. If there is a cut callback, it is called (repeatedly) until it stops
>supplying new cuts.
>
>4. Once no more cuts are forthcoming, the LP is solved. If the LP
>solution is integer feasible, the incumbent callback (if it exists) is
>called. (Note that during solution of the LP, CPLEX will typically add
>more cuts of its own.)
>
>5. (Here's where my memory gets slippery.) If the incumbent callback
>rejects the incumbent, I'm not sure if CPLEX calls the cut callback and,
>if it finds cuts, applies them and solves the LP again. I don't think
>so, but I'm not positive.
>
>6. If the LP is feasible but not integer-feasible, and if heuristics
>are turned on (they're on by default), CPLEX may attempt to apply node
>heuristics to find an integer-feasible solution. If it finds one, and
>if that solution looks like a potential incumbent (survives the bound
>check), it calls the incumbent callback.
>
>The key is that the cut callback is not called after step 4 (or maybe
>after step 5 -- I've got this written down somewhere, but not handy).
>So you need the branch callback to deal with the possibility that the
>incumbent callback is called in step 6, and finds a new cut -- which
>can't be added to the current node because we're past the last call to
>the cut callback.
>
>The other place where I believe we need the branch callback is where the
>LP is integer-feasible and we reject the solution. It *could* have a
>second, integer-feasible solution that we just did not happen to find,
>and that solution might be feasible in the original problem. But if we
>reject the integer-feasible solution CPLEX got, and can't apply the new
>cut at the current node, CPLEX has no way to separate the current node
>(because the solution is integer-feasible).
>
>So, bottom line, it's a matter of timing -- when does CPLEX stop calling
>the cut callback and when does it encounter the candidate integer solution?
>
>Hope that clarifies it.
>
>/Paul

--
Message posted via MathKB.com
http://www.mathkb.com/Uwe/Forums.aspx/op-research/200711/1