Originally posted by: SystemAdmin
If I understand you correctly, you want to provide a MIP, have CPLEX generate cutting planes for it, and then read out the LP relaxation plus cuts that you want to use for your branch-and-price.
Yes, this can be done, but only in the C API and it is not trivial. You need to use a cut or a branch callback to access the nodelp, and then the last rows of the nodelp are the cuts. You can uncrush them to get cuts for the original (not presolved) model.
But I don't think that this is useful for branch-and-price. Namely, similar to presolve, CPLEX assumes for the cutting plane procedures that all columns are known and the constraints are "final" (i.e., there are no coefficients for columns that CPLEX does not know of). If this assumption is wrong, then the cutting planes are not valid.
Let me explain this with an example. Consider a set partitioning problem, where you have generated some columns such that it looks like this:
min x1 + x2 + x3 + x4 s.t. x1 + x2 + x3 = 1 x1 + x2 + x4 = 1 x1 + x3 + x4 = 1
CPLEX can now generate the clique cut
x1 + x2 + x3 + x4 = 1
But now let's assume that your pricing method would later add a column x5 such that the system looks like this:
min x1 + x2 + x3 + x4 + x5 s.t. x1 + x2 + x3 + x5 = 1 x1 + x2 + x4 + x5 = 1 x1 + x3 + x4 + x5 = 1
Suddenly, the clique cut that CPLEX generated is no longer valid, because (0,0,0,0,1) is a feasible solution.
If you want to use cuts from CPLEX for your branch-and-price, then you also have to extend your new columns towards the cuts, i.e., you need to add coefficients for the new columns to all of the cuts such that they stay valid. In the example above, the cut has to be extended to read
x1 + x2 + x3 + x4 + x5 = 1
For clique cuts this may be doable, but in the general case, you just do not know how to extend the cuts appropriately. Additionally, those cuts will of course get dual variables that are part of the dual solution. Typically, this will mess up your pricing problem.
In short: branch-cut-and-price is a
very delicate topic and very hard to implement. There are so many things to consider. I have never seen general purpose cutting planes being used in BC&P applications (but I am not an expert, so there may be some). I think this can only work well if you have problem specific cuts for which you know how the pricing problem needs to be transformed to deal with them.
Tobias
#CPLEXOptimizers#DecisionOptimization