# Lagrangian Relaxation bound greater than optimal solution

I am working on a Lagrangian relaxation for a minimization MIP.

Everything seemed to be working fine before I started to run a batch of instances.

Checking the log results for one of the instances I found out that the lower bound given by the LR algorithm was greater than my optimal objective.

One of my concerns, beyond wrong coding from my part, is the chance that the solver is removing columns or doing any other stuff to speed up optimization that is only feasible because of the relaxed constraints.

I saw this kind of problem before when a friend was implementing a branch and cut with cplex without changing a solver parameter.

Is there any parameters set that I should deactivate, like presolve, cutting planes etc?

PS: I posted a copy of this question on gurobi community, but thought it would be good to also ask here, as here we are more active and also could find opinions from non gurobi users.

• How did you obtain the supposedly optimal objective value? Did you check the corresponding solution to confirm that it is actually feasible? – prubin Feb 20 '20 at 21:07
• With the original MIP after some long runtime. Now I'm using this value as an initial upper bound for the subgradient – seimetz Feb 20 '20 at 21:17
• So you are solving the subproblem using a MIP solver? If so you’d have to be very careful to get a true optimal solution (within a very small tolerance) otherwise the bound will not be valid. How far is the bound from the supposedly optimal solution? – LarrySnyder610 Feb 20 '20 at 21:49
• Which bound? The relaxed model bound is very far... The LR best bound was actually good for smaller instances. For larger ones, as a proof of concept, I was solving with time limit, and to avoid invalid bounds I was using the Lagrangian problem lower bound just to check the algorithm flow faster – seimetz Feb 20 '20 at 22:32
• If you terminate the solution of the relaxed MIP prematurely (time limit, memory limit, nonzero relaxation gap limit), the (relaxed) objective value you get may not be a valid lower bound for the original problem. I think that's what Larry was getting at in his comment. – prubin Feb 20 '20 at 23:07

After the discussion here and a suggestion on my post at gurobi's community I'll post an answer for the forum records.

Concerning the presolve, I found out that in order to check if this is what is getting strange results some parameters to change are:

'Presolve':0,
'Cuts':0,


Turns out that on my problem the issue wasn't bad code of the subgradient method, neither the presolve phase.

I found that I tightened too much one of the big M in the formulation and this is what produced the subproblem with a strange bound.