Originally posted by: Ccl_

Hello,

I am using concert for C++ (version 12.6.0) and I am implementing my own branching strategy using a BranchCallBack.

More precisely, I branch on the variables and bounds Cplex chooses to branch on, but in each newly created branch I also add some more variable fixings.

I know I can fix these variables because there are symmetries in my problem, and I will not change the optimal value by doing that. However, this action removes some solutions which were valid for the model I gave Cplex.

I noticed that in some (rare) cases, the solution returned by this algorithm is not optimal.

Could Cplex reductions during the presolve process interfering with my branching strategy?
Should I use an empty LazyConstraint callback? Are there other options?

Thansk a lot!

What you have to do is to disable dual reductions via CPX_PARAM_REDUCE.

Dual reductions may remove all but one optimal solution. If your branching happens to remove this optimal solution then CPLEX will terminate with a suboptimal solution.

Originally posted by: Ccl_

Thank you for your answer!

Just another question, I've read in the doc that the lazy constraint callback also disables non-linear reductions in pre-solve. 

Should I disable this too?

Surprisingly, the solving process seems to be slower when only dual reductions are disabled, compared to the case where I use an empty Lazy Constraint callback.

Something odd seems to be happening. Do you actually observe a difference in the solve if you just set CPX_PARAM_REDUCE to CPX_PREPREDUCE_PRIMALONLY (value 1)?

I had forgotten about the following fact: If you solve with a branch callback in C++ then CPLEX will automatically disable dual reductions and non-linear reductions. So you changing these parameters should not make any difference.

Here is the reason why non-linear reductions must be disabled (which should answer your question): CPLEX internally does not work with the user model but with the presolved model. On the other hand, the branching callback and lazy constraint callbacks work on the user model. Thus any branching decision or lazy constraint must be translated from the user model to the presolved model. This translation may fail if variables were subject to non-linear reductions. Such a failure would mean that CPLEX cannot apply your branching decision or cannot apply a lazy constraint. That is why these reductions must be disabled.

Originally posted by: Ccl_

There is no difference in the solve when I just set CPX_PARAM_REDUCE to 1, but I observe a difference in the solve when I add the Lazy Constraint Callback.

To illustrate, my original code with the Branch callback returns an optimal value of 8.81834e+06 with 62 nodes in the branching tree.

When I set CPX_PARAM_REDUCE to 1 the result does not change. If I also set CPX_PARAM_PRELINEAR to 0 the result still does not change.

But when I add an empty Lazy Constraint callback, then I get an optimal value of 8.81833e+06 with 83 nodes in the tree.

Does the Lazy Constraint callback disable other features? 

Presence of a lazy constraint callback disables dynamic search. If you compare the log output (after presolve, before root node) for the two approaches, I suspect you'll see dynamic search used when there is no lazy constraint callback but not when the callback is added.

Originally posted by: Ccl_

Thanks for your answer.

I thought the presence of the Branch callback would anyway disable the dynamic search (and the log outputs indeed specifies "MIP search method: traditional branch-and-cut.").

I still do not understand why the presence of an empty lazy constraint callback affects the optimal value. Do you have any clue explaining that behavior?

Thank you again for your help!

The discrepancy in optimal value is the result of CPLEX taking a different path through the search. With the lazy constraint callback, it probably landed on a different feasible solution that, while slightly worse, was still good enough to trigger the termination criteria (either absolute or percentage gap below the corresponding threshold). Less like, but still possible, is that it ended up with the same solution (in terms of values for the integer variables), but the different path it took led to a different amount of rounding error.

As to why the path changed, CPLEX does lots of clever stuff during a MIP solution run, including some stuff involving dual solutions to LP relaxations. The presence of a lazy constraint callback tells CPLEX that it may not have a full picture of all the constraints going in, so it should not trust dual solutions for certain things. That changes CPLEX's behavior. The changes occur when you attach the callback; regardless of what the code in the callback is. In particular, CPLEX does not make any special effort to detect an empty callback.

All this is qualified with "AFAIK".

Originally posted by: Ccl_

Thanks a lot for your answer! I understand it better now.

When you say Cplex "should not trust dual solutions for certain things", is it because it may lead to a suboptimal solution?

What I do in my branch callback is similar to adding lazy constraints, so is it safer to leave an empty Lazy Constraint callback, to be sure the optimal solution is found?

Thanks again!

We're reaching the limits of my knowledge, but I think the danger of using dual solutions in the presence of a lazy constraint callback is that CPLEX might end up prematurely fixing the value of a variable and/or prematurely pruning a node. So yes, you might end up with a suboptimal solution, or you might possibly end up with no solution when the problem is actually feasible (because CPLEX fixed some values that make an as yet undiscovered constraint unsatisfiable).

I'm a bit more confident in my answer to the second question. User constraint callbacks and (I'm pretty sure) branch callbacks come with an implicit "contract" telling CPLEX that the user will not cause an integer-feasible solution to be rendered infeasible by the callback. A lazy constraint callback does not make that contract, and in fact tells CPLEX that it in all likelihood will generate cuts that lop off some integer-feasible solutions. So if you do something funky in your branch callback that can make an otherwise feasible solution vanish from the search tree, then yes, you should add a lazy constraint callback (even an empty one) to tell CPLEX that you are "breaching the contract".

Hello,

just some clarifications:

1. An empty lazy constraint callback is not really a no-op. Preparing for invoking a lazy constraint callback can result in very tiny changes in the internal data structures. This can cause changes in the path CPLEX takes through the search tree and explains your observation. CPLEX will still find the optimal solution but potentially on a different path. Additionally, using a lazy constraint callback will disable even more MIP features than using only a branch callback. This also explains why CPLEX takes a different path in that case.
2. A branch callback indeed already disables dynamic search.
3. If you disable dual and non-linear reductions then it should be fine for your branch callback to generate "lazy constraints". I don't see how this would cut off optimal solutions, provided your code is wrong.

I suggest to do the following:

- explicitly disable dual and non-linear reductions (just to be on the safe side)

- double check the constraints you add to the node. Maybe even use the known optimal solution to make sure you are not by accident cutting off nodes that should not be cut off.

- double check numerics

If you have a small code example that you can share and that illustrates the problem then we can try to take a look here as well.

Finally, if you say the returned solution is not optimal, how sub-optimal is it? Could it be that both solutions are optimal within the tolerances given by CPX_PARAM_EPGAP and CPX_PARAM_EPAGAP? Does the problem persist if you set both to 0?