Originally posted by: SystemAdmin

[shaon said:]

Hi, all

I use the incumbent callback in my CPLEX　for the MIP. When I reject one integer solution, I want to add one local cut to the node LP.
I want to know whether CPLEX will automatically solve the LP again after I add one local cut in the incumbent callback. If it does not, is there any other to add one cut and resolve the node LP when I reject one integer solution?

Thanks for your help.


/Shaon
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Yes, but it's a bit complicated.  You will need, besides the incumbent callback, a branch callback and maybe a cut callback.  Note that, unless I am grossly mistaken, you cannot add a cut in the incumbent callback.  You can only reject the incumbent there.

Part of the problem is in part that CPLEX can generate incumbents more than one way.  One, of course, is that the node LP problem produces an integer feasible solution.  If that happens, I don't think CPLEX will call the cut callback (which occurs after solving the node LP the first time), but I'm not positive.  What I am more certain of is that the other way CPLEX can find an incumbent is by applying heuristics at the node.  That happens after the LP is solved and after the cut callback is called, so it's too late to apply any cuts to that node.

Another issue is that you don't necessarily want CPLEX fathoming the node where the incumbent was found.  Normally, in the absence of callbacks, if CPLEX finds an integer solution to the node LP, it fathoms the node (whereas if heuristics produced the incumbent, the node stays alive).  If you are going to reject the incumbent and add a cut, though, the descendants of that node might contain an optimal solution, even if the incumbent came from an integer-feasible solution to the node LP.  You would only want to fathom the node if the new cut either made the node infeasible or made its bound worse than the current incumbent.  But if the node LP gives an integer-feasible solution, CPLEX does not know how to branch, since it normally branches on a fractional value in an integer variable.

Here is the way I have (successfully) implemented this:

1.  The incumbent callback processes the incumbent and, if it does not like it, creates a new cut which it queues someplace in my code, then uses the reject() method to reject the incumbent.  (As a passing note, you could queue a cut and also accept the incumbent, if that made sense in your algorithm.)

2.  The cut callback checks the cut queue to see if any cuts are pending.  If so, it adds them (either locally or globally, whichever is appropriate) and purges the queue.

3.  The branch callback looks at the same cut queue.  If it sees a cut queued up, it creates one child node using that cut.  Otherwise, it does nothing (letting CPLEX handle branching the normal way).  The branch callback does [i]not[/i] purge the queue.

Note that the branch callback will be called at the current node, whereas the cut callback will not be called until the next node, so there is no danger that the new cut will be purged from the queue before the branch callback sees it.  In effect, the branch callback creates a clone of the current node with the new cut added.  (If you want, you can use a node callback to force CPLEX to process the cloned node next.  I don't; I'm content to let CPLEX process nodes according to whatever search strategy is in effect.)  The cut callback applies the cut to all other nodes.

If you want the cut to be local, you don't need the cut callback at all; the branch callback applies the cut to the clone of the current node (and by implication its descendants).  My cuts are all global, which is why I need the cut callback.  If you do only local cuts and skip the cut callback, then the branch callback purges the queue while implementing the new cut.

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[shaon said:]

Thanks you very much.

I have some questions:

In your successful implementation, the cut can be produced and added as local cut in the branch callback. But CPLEX will not swith to solve the LP when you reject an incumbent.


In fact we use a pure CPLEX. In other words, we turn off the presovle, heuristic, and other cuts routines by which CPLEX can automatically adds the cuts.  I have used a cutcallback to add the cuts based on the LP solutions.  Additional cut can be produced when I reject an integer solution.

[u]So in my problem, the integer solution can only happen when the node LP is solved. [/u]

When an integer solution is found, we will call the incumbent callback to check whether it is feasible by addtitional conditons.
  (1) If it is feasible, I will accept it in the incumbent callback.
  (2)If it is infeasible, I want to produce additional cut based on this integer solution and add it to current node. After that I want CPLEX to continue the solving this node LP in usual way (say. solve the lp, call cut callback. If the integer solution is found, it will call incumbent callback.  Repeat these three procedure until no cut can be added. Then it will branch). It is unlike what you have implemented.

I donot know whether you understand my question.




Shaon

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[shaon said:]

Hi, Rubin,


Can I say that your method  uses an indirect way to dealt with my problem? We create one child node at current node when we reject one integer solution. Then CPLEX can deal with this child node in usual way.  Indirectly, CPLEX solve the origianl node LP with new cut again.

So according to your suggestion, I will add a branch callback. I give a flag to this callback whether the incumbent is rejected. If this happens, we will control the branch and create one child node. Otherwise, I let the CPLEX to the branching.

Is it right?

Anyway, thank you very much. You are a very nice man and spent much times answering the questions  in this forum.


Shaon


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

I'll try to answer your last two messages in one gulp here.  It sounds from the latest one that you are on the right track.  Please keep in mind that my knowledge of the inner workings of CPLEX is limited, since I'm a user, not an ILOG code wizard.

Normally, when CPLEX steps into a node, the first thing it does (I think) is to check for a solve callback.  If one is present, the user wants to solve the node LP relaxation himself, or at least specify the solution process.  If not, CPLEX solves the node LP using whatever algorithm is indicated (probably dual simplex once you are past the root node), calls the cut callback (if present), and if a cut is added, solves again with the new cut included and calls the callback again, ad nauseum.  My understanding, though, is that once an integer-feasible solution is found (and the incumbent callback, if any, is called), there are no further calls to the cut callback at that node.  So the only way I know to add a local cut and continue processing the node is to use the local cut in a branch callback to create a single child, which is the current node plus the new cut.  You then either use a node callback to force CPLEX to process the child next, or else let CPLEX pick the next node on its own (knowing that sooner or later it will get to the child).  In most cases, I suspect that (left to its own devices) CPLEX will process the new node immediately, but if you are using best-bound search and the new cut drives the node bound above that of some other node, CPLEX might wander off for a while.

Your most recent response sounds correct to me.  Good luck.

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[shaon said:]

Hi, Paul,


Thank you very much.

I have finished the program according to your suggestions.

Shaon
#CPLEXOptimizers
#DecisionOptimization