10
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ How did you obtain the supposedly optimal objective value? Did you check the corresponding solution to confirm that it is actually feasible? $\endgroup$
    – prubin ♦
    Feb 20, 2020 at 21:07
  • $\begingroup$ With the original MIP after some long runtime. Now I'm using this value as an initial upper bound for the subgradient $\endgroup$
    – seimetz
    Feb 20, 2020 at 21:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – LarrySnyder610
    Feb 20, 2020 at 21:49
  • $\begingroup$ 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 $\endgroup$
    – seimetz
    Feb 20, 2020 at 22:32
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Feb 20, 2020 at 23:07

1 Answer 1

Reset to default
5
$\begingroup$

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.

Thanks everyone who asked more information and gave suggestions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I have the same problem. The lower bound exceeds the best found/optimal solution in literature. I decomposed the MILP into three sub-problems with two Lagrangian multipliers. The method works well for small instances, however, I face the same problem for longer instances. Could you please inform me how you figure out that you tighten the big M? I do not have a big M in my formulation. So, wondering how can I find the bug of my algorithm! Was time limit an issue for your problem? Thank you in advance. $\endgroup$
    – Aria
    Jun 26, 2020 at 17:03
  • $\begingroup$ As far as debugging goes, if you fix the integer variables in the Lagrangian subproblems to their values in the best found or optimal solution, does it still produce a bound that exceeds the best known solution value? Is there an issue with alleged infeasibility? If either happens, close investigation of the fixed subproblems may point you to a formulation error or a numerical stability problem. $\endgroup$
    – prubin ♦
    Jun 27, 2020 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.