Originally posted by: Gilead

Hi all,
I'm doing some research that requires the solution of linear and integer programs with constraints generation. My problem is twofold.

The first one concerns linear programming and cutting planes algorithm. I need to solve a linear program with a great number of inequalities. In this scope, I have a separation algorithm to generate dynamically violated constraints (given a solution of a reduced linear program, the separation algorithm gives either a certificate that the solution satisfies the constraints of the complete LP, or if not, raise a violated constraint). With this, I used the cut callback macro of concert to generate the violated constraints. The problem is that I'm not able to use this callback when the variables are defined as continuous variables. I must declare them as integral variables, limit the number of nodes in the branching tree to 1, and tune off one by one all the MIP constraints generated by Cplex in order to get the lower bound at the root node. Is there a more simple way to handle pure cutting planes algorithms with concert and cplex ?

The second problem concerns integer programming and branch-and-cut algorithms. The formulation I'm dealing with contains a great number of constraints for which I have as above, a separation algorithm. However, when I'm relaxing this set of constraints, I can get integral solutions that are not feasible (I'm starting with a linear and combinatorial relaxation of the original MIP). In this case, the separation algorithm will give some violated constraints in order to break these solutions. The problem is that the MIP cplex solver stops whenever it gets an integral solution and does check if the cut callback (implementing my separation algorithm) provides violated constraints. Is there a possibility in cplex/concert to force the use of the cut callback before stopping cplex, or even better, to provide the solver (by a callback) with a checker for solution feasibility at the root node?

Gilead
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Gilead wrote:

>Is there a more simple way to handle pure cutting planes algorithms with concert and cplex ?

If you solve an LP, modify it, and solve the modified problem, CPLEX will automatically "hot start" (attempt to use the previous optimal basis, and modify it as needed). So you don't need to use a callback for this case; just solve the LP to optimality, check the optimal solution, if necessary generate a new constraint and add it to the model, then solve the modified model. (This is all it takes with the Java API; with the C++ API, I can't remember whether you need to re-extract the model, but I don't think so.)
>
> The problem is that the MIP cplex solver stops whenever it gets an integral solution and does check if the cut callback (implementing my separation algorithm) provides violated constraints.

I think the best way to handle this is to add an incumbent callback. The incumbent callback checks the alleged integer solution and, if necessary, generates the separating cut, queues the cut (somewhere in your code) and rejects the incumbent. When the cut callback is subsequently called, it needs to check the queue and, if a cut is present, add it (and clear the queue).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Gilead

Thanks a lot for your answers. I will try your propositions.
#CPLEXOptimizers
#DecisionOptimization