Originally posted by: StephanBeyer

Hi,

I have a model (maximization problem) where I know that the optimal (maximal) integral objective value is an even integer. Since the relaxation is rather weak, the CPLEX search finds a lot of odd and fractional lower and upper bounds. So I hoped I can find an easy way to impose some "even" constraint into the model, such that the relaxation does better (due to improved upper bound) and more lower values are cut off (due to improved lower bound).

I thought I knew how to do it for the upper bound: add a UserCutCallback where the getBestObjValue() is compared to the maximum even number "newUpperBound" which is not larger than getBestObjValue() ... however, when I add a new constraint Objective <= newUpperBound (and I do not add locally!), I still get a lot of UserCutCallback debug outputs that shows me that the best objective has not been improved. So I guess I'm doing something wrong.

My questions:

1) What is the best way to impose a "we have an even optimal solution!" constraint for upper bounds?

2) And what should I do for lower bounds?

Thank you!

Stephan

Rather than optimizing f(x), you could try optimizing a new integer variable z with the added constraint that f(x) = 2z. This will have the side effect of rendering otherwise feasible solutions that yield odd objective values infeasible.

Originally posted by: StephanBeyer

Wow, this is a surprisingly simple idea! I give it a try.

Could CPX_PARAM_OBJDIF help here? If you know that an improving solution must improve the incumbent by at least 2 you could set this parameter to 1.9, for example.

Originally posted by: StephanBeyer

Thank you! This helps a lot and is much faster than using UserCutCallbacks.

Originally posted by: hllsen

If I am not mistaken, without the "f(x) = 2z" idea of Prof. Rubin, CPX_PARAM_OBJDIF parameter may lead to a non-optimal solution with an odd objective function value. More specifically, let f* be the optimal objective function value of the original problem, without the "f(x) = 2z" conversion, there may exist a feasible solution with an objective function value of (f*+1) and if Cplex finds this feasible solution during the optimization then it will miss the optimal solution.

Originally posted by: StephanBeyer

I think you are not mistaken. Luckily, there even are no feasible solutions to the MIP with odd value. Unluckily, the idea of Prof. Rubin worsens the run-time on all my tested instances.

Originally posted by: T_O

Unluckily, the idea of Prof. Rubin worsens the run-time on all my tested instances.

This is an effect that often appears when you put the objective function into the constraints. This has several reasons. One of them is dual degeneracy in the node lps, but there are further reasons that I forgot (I think it had something to do with branching).

Best regards,
Thomas