1
$\begingroup$

I was trying to solve a MILP by a column generation algorithm, and I noticed that the algorithm was stuck at the same solution, I tried to diversify the pool of initial columns, but the problem I faced was that even if the MP solved by CPLEX gave the optimal solution, the algorithm cannot prove it and keep returning it.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ It's not clear what "the algorithm cannot prove it and keep returning it" means. Do you mean that you find a column with negative reduced cost that is already in the column pool? If yes, what is the value of the reduced cost? $\endgroup$
    – fontanf
    Aug 24 at 11:55
  • $\begingroup$ Does the subproblem keep returning new columns with negative reduced cost? $\endgroup$
    – RobPratt
    Aug 24 at 11:56
  • $\begingroup$ Yeah, the subproblem keeps returning new columns. I solved the problem instance exactly using CPLEX in 1 second, but when calling column generation even if the Master Problem returns this solution from the first iteration, the subproblem keeps returning columns with negative reduced cost for many hours (I set 5 hours as limit time). $\endgroup$
    – Nada.S
    Aug 24 at 12:47
  • $\begingroup$ Does your subproblem objective maybe include a constant offset that you are not accounting for? It might be best to show us your original, master, and subproblem formulations (in math, not in code). $\endgroup$
    – RobPratt
    Aug 24 at 13:11
  • 1
    $\begingroup$ If at least one of the columns that you add at each iteration was not in the pool and ends up in the master problem solution of the next iteration, then it''s just that the algorithm hasn't converge yet. For large problems, the column generation procedure might require a lot of iterations $\endgroup$
    – fontanf
    Aug 24 at 13:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.