2
$\begingroup$

I have a convex MINLP that after a Dantzig-Wolfe reformulation, passes most of the difficulty onto the pricing problem, which becomes a convex MINLP itself.

The pricing problem should be solvable with a Benders-like algorithm since it has a set of variables $y$ such that, when fixed, the problem is extremely easy to solve. However, these fixable variables are continuous, not discrete, and so the corresponding Benders-like subproblem has integer variables, which excludes traditional Generalized Benders.

I know that I can solve the continuous relaxation and then branch, and I have also seen Logic-based Benders Decomposition, which requires branching as well. I am afraid that this will take too much time, especially given that I am not interested in an optimal solution, I just want to generate a new column for the Dantzig-Wolfe's master.

So my question is, besides setting a high $\varepsilon$ parameter for the Benders termination criteria, are there any other $\textit{fast}$ alternatives? To summarize, the subproblem is a MINLP for which I can obtain solutions very very quickly, and I am not necessarily interested in provably optimal solutions (but still would like more than just feasibility).

As additional information, all integer variables are binary. Furthermore, for fixed $y$ variables, I can solve the subproblem directly without calling an outside solver, as everything else is fixed as well. Solving the continuous relaxation takes considerably more time, and that is why I am wary of branching approaches. Finally, the domain of $y$ is such that I do not need to worry about its feasibility.

Improve this question
$\endgroup$
9
  • $\begingroup$ Just to be clear, when you say "subproblem" you are referring to a subproblem of the pricing problem (which is itself a subproblem of the D-W problem), assuming the pricing problem is being solved by some version of Benders? Since you do not require optimality, what about "solving" either the subproblem or the entire pricing problem via heuristics? $\endgroup$
    – prubin ♦
    Jan 18 at 16:43
  • $\begingroup$ @prubin , yes what you said is correct. Regarding solving either the pricing or the subproblem of the pricing with heuristics, that would be a viable way to do it. However, given that I have the $y$ variables, it really seems like Benders should work as well, even if it serves as just a comparison to some heuristics. Not only that, but eventually I would require optimal solutions, but that would only be relevant on the later iterations of D-W. $\endgroup$
    – J. Dionisio
    Jan 18 at 16:53
  • 1
    $\begingroup$ What about solving the subproblem by branch-and-cut with either a node limit or a time limit (or both) keeping the solution time short? $\endgroup$
    – prubin ♦
    Jan 18 at 16:59
  • $\begingroup$ @prubin , the subproblem is very easily solvable for a fixed $y$, in the milliseconds. Are you suggesting that, for a fixed $y$, I try to solve the continuous relaxation of the subproblem by branch-and-cut while imposing limits? This is a strange case where the continuous relaxation is harder to solve than the integer counterpart. $\endgroup$
    – J. Dionisio
    Jan 18 at 17:11
  • $\begingroup$ No, I meant the integer version, not the relaxation. So your concern about the Benders decomposition is the number of Benders cycles rather than the time to solve a single subproblem? That can again be capped with an iteration (or time) limit. $\endgroup$
    – prubin ♦
    Jan 18 at 19:00

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.