Originally posted by: nadelgr

Does CPLEX have a cut separator interface? In particular, if I know of a specific disjunction, is there a way to ask CPLEX to generate cuts based on this disjunction? If so, in what form will I have access to the cuts? Can I implement them locally, or must they be globally valid? If it helps, I'm using CPLEX 12.6, the C API, and several callbacks.

Thanks!

Nathan

Within a user cut callback or a lazy constraint callback, CPXcutcallbackadd() can be used to add a globally valid cut and CPXcutcallbackaddlocal() to add a locally valid cut (applies only to the current node and its descendants). There are also CPXX... versions. Use in a user cut callback implicitly warrants that your cuts will not invalidate any otherwise feasible integer solution. Use in a lazy constraint callback does not make this contract -- the cuts can (and likely are designed to) separate integer feasible points from the true feasible region.

Originally posted by: nadelgr

Paul,

Thank you for your reply. I am aware of the ways in which I can add cuts if I know of them, but I'm asking something slightly different. What I'm trying to find out is, suppose I know of some disjunction, can I ask CPLEX to generate cuts based on this disjunction? Essentially, I'm looking for a tool that functions independently of branch-and-bound. I'd like to pass CPLEX a problem (LP, MIP, etc) and a disjunction, and have CPLEX return to me a cut (or possibly a set of cuts) which convexifies (or is at least valid for) the disjunction. Does something like this exist? My thought is that it would be too good to be true, but before I go writing my own code to generate the cuts, I thought I would ask.

Nathan

Sorry, I misunderstood the question. I'm not sure that CPLEX will necessarily generate convexification cuts. For instance, if I take a MIP model containing an auxiliary variable zz (real-valued) and add the constraint zz <= 2 or zz >= 5 (using IloCplex.add(...) with an IloOr argument), then export the model, the following is added to the LP file:

 zz_or:  zz_lo + zz_hi >= 1
 zz_lo: zz_lo = 1 <-> zz <= 2
 zz_hi: zz_hi = 1 <-> zz >= 5

The constraint names were assigned by me: zz_lo is the IloRange zz <= 2, zz_hi is the IloRange zz >= 5, zz_or is the IloOr object. Note that CPLEX automatically created eponymous boolean variables for zz_lo and zz_hi and used them to formulate the disjunction. My guess is that, internally, the "if and only if" constraints will be represented by big-M type constraints. I think that's not what you have in mind by convexification cuts.

If CPLEX does in fact add convexification cuts, I think the only way to get them is to access the root node LP (after cut generation), which can be done only in the C API.

I'm not sure about software alternatives. I think Couenne contains a route for generating convexification cuts, but I don't know how hard it would be to access separately from the solution process.

Paul

Originally posted by: nadelgr

Paul,

Thank you for replying again. These IloOr objects are quite interesting, but as you said, not quite what I am looking for. I'm sure CPLEX does add convexification cuts, but only for disjunctions that it knows of (perhaps split cuts or something like this). As you mentioned, I have been able to take some of the cutsCPLEX generates and utilize them in various ways (since I am using the C API). The problem is that I want to generate the convexification cuts for a user-specified disjunction, which I'm afraid I'm unable to do. I have considered the use of Couenne and other alternatives, but the disjunctions I have are simple enough that if I'm going to try to generate these cuts outside of a built-in CPLEX function, I may as well just write the code to do it. Either way, thank you for your insight and your help. Maybe I'll leave the question open for a few days to see if I get any more interesting responses.

Nathan

Originally posted by: AndreaTramontani

Hi Nathan,

unfortunately, there is no possibility for the user to specify a disjunction (or a list of disjunctions) and "force" CPLEX to generate cuts from such disjunctions.

CPLEX offers several separators, and two of them are specifically for disjunctive cuts:
.. Disjunctive cut separator, the C API parameter to control them is CPXPARAM_MIP_Cuts_Disjunctive or CPX_PARAM_DISJCUTS
.. Lift and Project cuts, C API parameter to control them is CPXPARAM_MIP_Cuts_LiftProj or CPX_PARAM_LANDPCUTS

The two above separators are alternative ways of separating Split cuts (i.e., disjunctive cuts from split disjunctions).
The parameters give you the possibility to control, to some extent, how much aggressive you want to be with the separators, but there is no possibility to specify the disjunctions in advance and force CPLEX to use them. The separators will consider some disjunctions selected according to some internal rules.

The main difficulty I see on our side (i.e., CPLEX) to provide such a feature is that, even if the disjunction is fixed, there are plenty of cuts you can generate and many alternative separators you could use. If you want to implement your own separator to be used with callbacks, then maybe the references below can be useful.
The first two ones are papers on alternative approaches proposed in the literature for Lift and Project cuts. The third one is an INFORMS presentation that describes what we did when we implemented Lift and Project cuts in CPLEX.

Hope this can help.
Andrea

1. M. Fischetti, A. Lodi, A. Tramontani, "On the separation of disjunctive cuts". Mathematical Programming, Ser. A, 128, 205--230, 2011
2. P. Bonami, "On Optimizing over lift-and-project closures". Mathematical Programming Computation, 4, 151--179, 2012
3. A. Tramontani, "Lift-and-Project Cuts in CPLEX 12.5.1". INFORMS 2013, Minneapolis (MN), 2013, available at
https://www.ibm.com/developerworks/community/wikis/form/anonymous/api/wiki/de368162-e90b-432c-a4e9-795cc51440dd/page/4096cfd2-4525-4e5a-a076-a09e259e6ce8/attachment/96a1a8cd-d607-41f0-90ab-83c57739b91e/media/INFORMS2013_LiftProjCuts.pdf

Originally posted by: nadelgr

Andrea,

Thank you very much for your reply! I understand the difficulty on your end to provide a tool like this, and I'm not upset that such a thing does not exist, I just wanted to make sure before implementing my own separator. Thank you for the useful resources provided, I will certainly use some of that information in my implementation!

Nathan