Originally posted by: amindehghanian

Hi,

In my branch and cut code, CPLEX does not generate any internal cut(exactly 0 cuts)( even I set them to be generated aggressively)!
What does this mean?

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Well, it can just happen that CPLEX is unable to find any cutting plane.

If possible, could you send me your model (lp, mps, or sav file) to achterberg (at) de (dot) ibm (dot) com? Then I can take a look at what is going on...
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Hi Tobias,

I sent you my model. Did you have a chance to take a look?

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Amin,

sorry for the late reply. I was sick and wasn't able to do much for the last couple of days.

I looked at the three models you sent. The "master.lp" is solved already in presolve, so there is no reason to produce any cuts. The "dual of subproblem.lp" is an LP. And "extensive.lp" is solved at the root node and uses some cutting planes:

Implied bound cuts applied:  33
Flow cuts applied:  1          
Mixed integer rounding cuts applied:  5

Which is the model for which you do not see cuts and for which you expected to get some?

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

I am sorry to hear that, and I hope you are all right now!

Actually, I use a Bender’s decomposition algorithm to solve my two stage stochastic program while first stage and second stage variables are binary and continuous, respectively.

So, I first write the master problem, then I try to add the violated cut, which is found in my "dual of subproblem.lp", to my master problem (exactly in the Bender's style).

The Benders violated cuts are valid for LP relaxation of my problem. So, they don't use the fact that my first stage variables are Binary.

So, I was expecting CPLEX to generate its own internal cuts in non-integral nodes of my branch and cut tree in order to handle this issue.

I sent you the extensive.lp to you in order that you can see what is the real problem which I am trying to solve. So, it does not have anything with my branch and cut algorithm.

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Okay, but I still don't see the problem.
You said that you are having a MIP (your master model, I guess) where CPLEX does not generate any cuts, but you were hoping for CPLEX to do so.
The "master.lp" that you sent is a MIP, but this is so trivial that CPLEX solves it with presolve. Consequently, no cuts are needed...

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Consider that I have a branch and cut tree.
My master.lp is just the initializing point of the algorithm.
Then, I iteratively add my lazy constraints to this master problem.

At the initialization point, as you observed, CPLEX solves it with presolve immediately.
But, at next iterations (nodes of my branch and cut tree) of my algorithm when master problem is getting bigger, I was expecting CPLEX to add some internal cuts!

To make a long story short, master problem is iteratively getting bigger in my algorithm, that is the place where CPLEX is expected to generate internal cuts.

Please let me know if it is not clear yet?

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Okay, I understand. Could you then please send me one of those more advanced master.lp problems where you would expect CPLEX to generate cuts?

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Clearly, at any non-integral node of my branch and cut tree, there is a version of master problem.

I just picked one of them randomly and uploaded it here.

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you uploaded is an LP; no integrality restriction. If I convert all x variables to binary, then the model is again solved in presolve.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Hi Tobias,
Maybe, you already find the issue with the file which I uploaded.
Actually, I got the file through CPXgetcallbacknodelp. It is not mentioned which variables are binary and which of them are continuous.
I modified it manually and attached it.

I also threw this into CPLEX, and it was solved in a second.

But, my problem is that in my branch and cut tree, CPLEX does not generate internal cuts!

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Let us put it this way:

I am implementing a branch and cut algorithm in CPLEX.

I suppose that in addition to my own generated cuts (user cuts), CPLEX generates its own internal cuts to solve the problem in the B&C tree.
This does not happen in my case! Is it normal?

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Or, in the other word:

Does using a lazy constraint callback and a user cut callback make CPLEX unable to generate its own internal cuts (like what happens for dynamic search)?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

No, using a lazy constraint or user cut callback will not prevent CPLEX from generating its own internal cuts.
But I still do not see the problem here. Your "130-modified.lp" is still so easy that CPLEX solves it during presolve. If I disable dual presolve reductions (which implicitly happens if you install a lazy constraint callback), then the LP relaxation of the presolved model has an integral solution and no cutting nor branching needs to be done.
If you want to see CPLEX adding cutting planes, you have to use a more complicated problem instance.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks Tobias!

Yes, "130-modified.lp" is very easy because it is obtained at early steps of my branch and cut.

Actually,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks Tobias!

Yes, "130-modified.lp" is very easy because it is obtained at early steps of my branch and cut.

I tried to upload a more advanced problem, but it is still too easy for CPLEX to solve this independently.

It is worth to mention that the sub-problems which I added is obtained my branch and cut tree. So, CPLEX consider them as LP rather than MILP. After that, I don't know what is going on in CPLEX?

My understanding from what you said is that if this trend continues in my branch and cut tree, CPLEX will not need to generate any internal cut ("LP relaxation of the presolved model has an integral solution and no cutting nor branching needs to be done"). Right?

Thanks again,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Tobias,

I strongly believe this is what is happening in my case.

In, my master problem, I don't have any constraint, then I add violated constraints dynamically using a cutcallbackadd.

I think CPLEX does not build its internal cuts based on user cuts.
On the other hand, my master problem at its initialization point (before adding violated cuts by cutcallbackadd)does not have any constraint.
So, there is no constraint for CPLEX such that it could build an internal cut based on.

To make it short, again I think CPLEX does not does not build its internal cuts based on user cuts, right?
If this is true, is there any workaround for this issue?

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Some of the cutting plane procedures in CPLEX only work on original constraints, but some others would also build cuts on top of other cuts (including user cuts).

If you set all cuts to aggressive (in the interactive, use "set mip cuts all 2"; from a programming API set all cuts parameters individually to 2), then you should see some cutting planes generated for your problem, provided that the model is not so easy that it is solved either by presolve or by the initial LP relaxation.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Sorry; I found it. The issue is the CPX_PARAM_CUTSFACTOR parameter. This limits the relative growth of the problem due to cuts. So, CPLEX will stop generating cuts if the total number of rows would exceed CPX_PARAM_CUTSFACTOR * origrows, with origrows being the number of rows after presolve.

In your case, origrows == 0, so CPLEX will not generate any cutting plane, independent on how large you will set CPX_PARAM_CUTSFACTOR. Unfortunately, there is no way to disable CPX_PARAM_CUTSFACTOR. The workaround would be that you add one or a few of your cuts in advance as original rows. You just need to make sure that they are non-trivial and survive the presolve step. Since you need to disable dual presolve reductions anyway (due to your lazy constraints), this should not be too hard.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

And of course the other part of the workaround is to set CPX_PARAM_CUTSFACTOR to a really high value, for example 10000.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thank you very much Tobias!
I got your point!
I never imagined that this issue would be solved :)

Thanks a lot!
Amin
#CPLEXOptimizers
#DecisionOptimization