Originally posted by: frangio

Hello.

We are trying to solve some large LPs (the continuous relaxation of a multicommodity network design problem) as efficiently as possible with Cplex. We know a large set of constraints, most of which inactive in the optimal solutions, that considerably improve the bound, and we need to include them. They are many, but not so much as to require (or even benefit from) algorithmic separation. In short, we would like Cplex to take them into account, but knowing that the vast majority of them will not be active, and therefore avoiding to add all of them to the coefficient matrix from start. We'd also like to avoid dabbling with the cut callback function.

Apparently, "user cuts" should perfectly fit the bill. We initially thought "lazy constraints" were the thing, but the manual clearly specifies that these are only applied to integer solutions, while we want our cuts applied to fractional ones (since as far as Cplex is concerned we are not solving an integer problem).

Much to our displeasure, this does not seem to work. When solving the LP as such, cuts are apparently not applied. This may be reasonable (although disappointing for us), and we think that we may probably obtain what we want by:

• solving the problem as a MIP but stopping it at the root node;

• disallowing any heuristic and other cut generation routine.

We just wanted to know whether this would work as intended, and if there is any simpler way to attain our desired result.

Thanks

Antonio
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX will do the work for you. You didn't specify an API, so I'll illustrate with Java (C++ will be very similar; presumably so will Python and C#).

IloCplex cplex = new IloCplex();
// build the LP model in cplex
// figure out the number (nlazy) of lazy constraints desired
IloRange[] lazy = new IloRange[nlazy];
// populate lazy with constraints -- no need to worry about "lazy constraint" v. cut, they're just 
// instances of IloRange
cplex.addCuts(lazy);
cplex.solve();
// etc.

CPLEX will automatically treat the problem as a MIP (due to the presence of lazy constraints), solve it at the root node, and apply any lazy constraints that would otherwise be violated.

/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: frangio

Dear Paul,

> CPLEX will do the work for you. You didn't specify an API, so I'll illustrate with Java
> (C++ will be very similar; presumably so will Python and C#).

Actually, we are old-schoolers: we still use the C API (since it was the only one around when we started writing our codes many years ago ...).

But the trick still works. We define a problem without integer variables, but we call CPXmipopt() to solve it. Then, magically, lazy constraints work the way we wanted.

It's a bit counter-intuitive, and it seems to contradict the manual, which explicitly says that lazy constraints are only applied to integer solutions. Your manual writers may consider rephrasing these sentences. That having been said, I'm very glad it works for us. Thanks a lot.

Antonio
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> frangio wrote:
>
> Actually, we are old-schoolers: we still use the C API (since it was the only one around when we started writing our codes many years ago ...).

I go back to when there was a FORTRAN API (but no C++), so I sympathize.
>
> But the trick still works. We define a problem without integer variables, but we call CPXmipopt() to solve it. Then, magically, lazy constraints work the way we wanted.
>
> It's a bit counter-intuitive,

The entire business of lazy constraints causing an LP to be treated as a MIP is a trifle counter-intuitive to me, too.

> and it seems to contradict the manual, which explicitly says that lazy constraints are only applied to integer solutions.

I'm not sure where it says that. I found the following in the C reference manual entry for CPXaddlazyconstraints:

The routine CPXaddlazyconstraints adds constraints to the list of constraints that should be added to the LP subproblem of a MIP optimization if they are violated. CPLEX handles addition of the constraints and makes sure that all integer solutions satisfy all the constraints. The constraints are added to those specified in prior calls to CPXaddlazyconstraints.

To me, that means they're added to the node LP if the node LP solution violates them, rather than if an integer-feasible solution violates them.

> Your manual writers may consider rephrasing these sentences.

Well, they're not my manual writers (I'm a civilian), but I'm sure someone from IBM will read this thread and pass the hint along to their documentation team.

> That having been said, I'm very glad it works for us. Thanks a lot.

You're welcome.

/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: frangio

Dear Paul,

> I'm not sure where it says that.

In the User Manual, section

Differences between user cuts and lazy constraints

I found this

Another important difference between pools of user cuts and pools of lazy constraints
lies in the timing by which these pools are applied. CPLEX® may check user cuts for
violation and apply them at any stage of the optimization. Conversely, it does not
guarantee to check them at the time an integer-feasible solution candidate has been
identified. Lazy constraints are only (and always) checked when an integer-feasible
solution candidate has been identified, and of course, any of these constraints that
turn out to be violated will then be applied to the full model.

The emphasis on "only" is mine. To me, that seemed to say that lazy constraints are not
checked against the fractional solution. Again, I'm glad it was not so.

Best Regards

Antonio
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi there,
I know the differences between lazy constraints and user cuts may seem a bit subtle. However, in your case I think CPLEX is working as documented.
As far as I understood you do not have any integer variables, correct? So any solution is integer feasible. This means that lazy constraints should be checked for any solution you found (as any solution has no integer infeasible values).
I got your comments and we will think about improving documentation in the future.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: frangio

Hello.

> As far as I understood you do not have any integer variables, correct?
> So any solution is integer feasible. This means that lazy constraints
> should be checked for any solution you found (as any solution has no
> integer infeasible values).

Heck, your logic is impeccable. My fault for not figuring out this myself.

I may only add that a few lines to this effect in the manual may be useful to the more logically-challenged users like myself. :-)

Best Regards

Antonio
#CPLEXOptimizers
#DecisionOptimization