Originally posted by: amindehghanian

Hi,

I have implemented my branch-and-cut in CPLEX, and I am suffering from a horrible tailing effect in closing optimality gap. Unfortunately, CPLEX generates not internal cuts (exactly 0)  for this problem even though I set them to be aggressively generated? 

It is worth to mention that:

1. In the root node, I only have a coupe of constraints, however I set CPX _PARAM_CUTSFACTOR to be a large number.

2. In most of the nodes, I have only 1 or 2 integer infeasible  variables.

Any idea would be greatly appreciated!

Thanks,

If you only have a couple of constraints, I would not be shocked to find that CPLEX has a hard time generating cuts. The cuts have to be built from something.

Is the long tail primarily due to CPLEX being slow to find good incumbents, is the bound moving slowly, or both? Have you tinkered with MIPEmphasis? Have you tried anything else mentioned in the user manual's section on slow convergence?

Paul

Originally posted by: amindehghanian

Thanks for your answer!

Though I start with a couple of constraints, I add my lazy constraints as the optimization progresses, and according to what Tobias told me,  CPLEX could build its own cuts on user cuts. However this is not happening in my case.

I can find the optimal solution in a reasonable time, however I face a horrible tailing effect as optimality gap gets smaller than .005. I already have work with MIPEmphasis, and it did not work.

Originally posted by: TobiasAchterberg

My guess is that the lazy constraints only come into play after the root node has been finished and solution candidates are identified by branching. Cutting planes are mostly used at the root node. Thus, your lazy constraints probably come in too late to be considered as basis for additional CPLEX internal cuts.

You should try to find out which of the lazy constraints are actually important for your problem (those that you had to add because some integer solution found by CPLEX violated them). Then, you should generate these constraints in advance as regular constraints. This will give CPLEX better options to apply presolving and cutting planes.

Alternatively, you could test whether the "advanced start indicator" parameter set to 2 is interesting for you. When you set this parameter to 2, it means that when you call the MIP optimizer again after having interrupted a previous solve (e.g., using a node limit) it will throw away the search tree to start the search from scratch, but it will keep the incumbents, the cutting planes, and the lazy constraints. Doing so should then enable CPLEX to generate additional cuts on top of the lazy constraints that have been added in the first MIP optimizer run.

Tobias

You might look at whether it is possible to generate deeper lazy constraints. In particular, if you are doing Benders decomposition, there's a paper by Magnanti & Wong (Operations Research, 1981, 29, 464-484) that suggests a way to generate deeper optimality cuts, which might make the bound close faster.

Paul

Originally posted by: amindehghanian

Thanks for your answers!

@ Tobias:

Yes, I generate only a few lazy constraint in the root node.

1. Unfortunately, I cannot figure out ahead of time which constraints are important to add them in the root node.

2.  "advanced start indicator" did not work either, however it seems reasonable to me. Actually, I have a class of important constraints which are locally valid, so I cannot use them. On the other hand, My global constraints are combinatorial valid inequalities ( e.g.  \sum_{i \in I} x_i \geq 1 where x_i is binary ), and they barely remove a non-integer solutions.

3. It is worthy to mention that in my problem there are many integral solutions very close to the optimal. So, multiplicity might be an issue.

@ Paul:

Yes, I am doing Benders, and I am generating strongest  optimality cuts now, so I cannot think of a way to improve them.

Thanks for your answers again!

If your model contains symmetry, you might try reducing it, either through symmetry-breaking constraints or through a custom branching scheme. Symmetry is one possible cause of sluggish movement of the bound.

Paul