Originally posted by: Namal

Hello,

I have a question about my problem

\ENCODING=ISO-8859-1
\Problem name: IloCplex

Maximize
 obj:
Subject To
 c1: x2 + x3 - x1 >= 0
 c2: - x2 + x3 - x1 >= -1
 c3: x2 - x1 + x4 >= 0
 c4: x2 - x3 + x4 >= 0
 c5: x2 - x3 + x1 >= 0
 c6: x2 + x1 + x4 >= 1
 c7: - x2 + x3 - x1 >= -1
 c8: - x2 - x3 + x1 >= -1
Bounds
 0 <= x2 <= 1
 0 <= x3 <= 1
 0 <= x1 <= 1
 0 <= x4 <= 1
Binaries
 x2  x3  x1  x4
End

If I solve it I don't get any information about the cuts, only if I add more constrains constrain so the problem becomes infeasible I get information about the type of cut and how many were made. I also tried to use specific cuts like

cplex.setParam(IloCplex::Param::MIP::Cuts::Cliques, 3);

but they are still not used. Why is that  so?

Originally posted by: BoJensen

It will only print cut info if cuts were applied. If not disabled it will of course call the cut separators, but only add cuts found if they are deemed worth it. Your problem can have many cliques, but if they are not violated in the node LP solutions, no cuts will be active nor added to the LP.

Originally posted by: Namal

So if there is no information about the cuts is it done by branching only?

Originally posted by: BoJensen

It tells you that it was solved without adding cuts.
 

Originally posted by: Namal

So do I understand it right,  cplex can't generate useful cuts from my problem to solve it or is it just bad to do it that way and cplex does something else?

Originally posted by: BoJensen

If CPLEX decides not to add cuts, it could be because no cuts was found by the used cut separators or some violated cuts was found but not deemed useful. Then it continues with exploring the tree, which means branch and bound, but it does many other things to speed up the process too. 

Originally posted by: Namal

Well, for this particular problem there is this in the stream

Total (root+branch&cut) =    0.00 sec. (0.00 ticks)
Solution status = Optimal

that is why I was wondering why there is branch&cut used but no cuts.

If add some more constraints to my problem it becomes infeasible. Cplex generates one zero-half cut. So is this zero half cut considered useful? Because there are still no clique cuts being generated.

Originally posted by: BoJensen

CPLEX is using a branch and cut scheme, even if no cuts were added it's still called branch&cut in logging.

In the case you add an infeasible constraint to this particular problem, then the polyhedron changes and for this case CPLEX decides to add a cut, which possibly helps CPLEX to determine the problem is infeasible.

Also note that the model in your initial post is very simple: The objective value of the LP relaxation is 1 and the all-1 vector is a feasible solution with objective value 1. Since CPLEX finds this feasible solution very early, it can stop as soon as it has solved the LP relaxation since that proves optimality of the simple solution.

Like Bo said, the model is just way too simple to trigger any cuts in CPLEX. It gets solved before CPLEX would even consider using any cut.

Originally posted by: Namal

Hello Daniel,

can you explain to me the part with the objective value of the LP relaxation please. I am interested in how it works. If I only do the relaxation of this problem it is not integer.

Well, this is basic integer programming:.

The LP relaxation of the model has objective value 1. This means that no feasible solution can ever have an objective function value that is better than 1. This fact is independent of whether the LP relaxation is integral or not. Also, it does not prove that there is a feasible solution with objective value 1. It just says that there cannot be any feasible solution better than that.

On the other hand, we have a feasible solution with objective value 1 (the all-1 vector). Combining these two facts (you have objective 1 and know that it cannot get any better) one can immediately conclude optimality. No need to do anything further.

EDIT: What I said here applies to the model I downloaded in the morning from the initial post in this thread. In that model the objective function was 'x1'. Now the objective function in that post is empty, so the optimal objective function value is of course no longer 1.

Originally posted by: Namal

Thank you Daniel,

the only part I don't understand is how do you know that the objective value is 1?

Did you update your initial problem after posting it? Because when I copy-pasted your model this morning, the objective was x1. Now the objective is empty?

In this case things are even easier: you can stop as soon as you have a feasible solution. Technically, you would not even have to solve an LP relaxation, so no need for any cuts again.

Originally posted by: Namal

Hallo Daniel,

yes, my goal is to get any integer solution, therefore I did following

IloObjective obj = IloMaximize(env);

model.add(obj);

and

cplex.setParam(IloCplex::Param::MIP::Tolerances::MIPGap, 1.0);

But this sets the objective function to x1 somehow and I just removed this lines.

I could not reproduce that. Calling

IloObjective obj = IloMaximize(env);
model.add(obj);

Always produces an empty objective for me. In any case, with an empty objective my statements from my previous post still apply: the model is so simple that CPLEX can solve it before it even has to consider any cuts. That is why you don't see any reports about separated cuts.