Originally posted by: NingZhu

hi, guys

I want to solve a MIP problem by my own branch and cut. I use cplex 12.7.0 and python 2.7. the difference between my branch and cut and the classical branch and cut is shown as below.

First, when I get a "possible" feasible integer solution (the corresponding objective value is smaller than the upper bound, and the problem is minimum),  I should use a "complex method" to judge if it is really feasible, otherwise this solution is infeasible and add a cut to delete this point.

Second, when this "possible" feasible integer solution is infeasible , I may use some heuristic method in order to get a feasible solution quickly (not ensure it is incumbent optimal). if the corresponding objective value is best than the upper bound, the upper bound and incumbent solution will be updated.

To design my algorithm,  I see some  topics and learn something about callback. I guess that I should define the "complex method" first and call it in the lazyconstraint callback. If the solution is infeasible, a cut is added. Then the heuristic callback will be invoked to set incumbent solution because I know this callback is the only way to set the incumbent solution by users. However,  I know the heuristic callback is invoked only when the solution is not integer. It is not my need. 

Therefore, how should I design my algorithm and what kinds of  callbacks should I use?

Ning Zhu

Add both a lazy constraint callback and a heuristic callback, and create a variable for new solutions in global memory. When the lazy constraint callback creates a "possible" solution, it sets the global variable to that solution. When the heuristic callback is invoked, it looks at that variable and, if not null, gives the solution to CPLEX and sets the variable to null. The "possible" solution may not (in fact, I think will not) be added at the same node where the lazy constraint callback was called, but it will be added at the next node processed, which should be soon enough.

Originally posted by: NingZhu

Dear Paul

thanks for your help, but I still have some problems

what is  the sentence " The "possible" solution may not (in fact, I think will not) be added at the same node where the lazy constraint callback was called, but it will be added at the next node processed, which should be soon enough." mean? 

as I say above, it seems that  the heuristic callback will be invoked only when the incumbent solution is non-integer. Therefore, I wonder if it will be invoked 

Ning Zhu

The incumbent solution is never non-integer; a solution violating integrality restrictions cannot be accepted as an incumbent.

If you mean that the heuristic callback will only be called at nodes where the solution to the node LP relaxation is not integer-feasible, that is possible. I've seen multiple explanations of the order of operations CPLEX uses at a node, and those explanations differ among themselves. Also, there is no guarantee that the order CPLEX does things at a node will be the same in a future version as it is now.

The solution I gave in my previous answer queues your "possible" solution to be applied the next time that the heuristic callback is called. Unless every node after the current one generates new integer-feasible candidates, the heuristic callback will eventually be called and the "possible" solution will be evaluated as a possible incumbent. Typically, I would expect the heuristic callback to be called at the vast majority of nodes, so I would be surprised if you had to wait long to have the "possible" solution tested and very surprised if it never was.