I am implementing a Benders Decomposition on a large MILP, where the objective is to minimize the cost associated with the integer variables. As a result, my Benders subproblem is only a feasibility problem. This is not an issue since the dual will have an objective and I can use Benders to make feasibility cuts. However, I am not sure whether the subproblem dual should be a minimization or maximization problem. What clue should I look for that will tell me the optimization direction?

asked 18 Jan '18, 10:53

leruckle's gravatar image

accept rate: 0%

If I understand you correctly, you have a problem of the form \[ \begin{align} \min \ & cx + 0f\\ s.t.:\ & Ax + Bf = b\\ \ & x\in \mathcal{X}\cap\{0,1\}\\ \ & f \in\mathcal{F} \end{align} \] From here you should just continue as usually. If \(\bar{x}\) is a solution to the integers variables then the subproblem becomes \[ \begin{align} c\bar{x}+\min \ & 0f\\ \ &Bf=b-A\bar{x}\\ \ &f\in\mathcal{F} \end{align}\]


answered 18 Jan '18, 14:02

Sune's gravatar image

accept rate: 20%

edited 18 Jan '18, 14:06

Ah, yes, you are exactly correct. It is obvious in retrospect. Thank you.


answered 18 Jan '18, 15:17

leruckle's gravatar image

accept rate: 0%

If your question was answered, please accept the answer for future useres comining across your question.

(20 Jan '18, 16:08) Sune
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 18 Jan '18, 10:53

Seen: 387 times

Last updated: 20 Jan '18, 16:08

OR-Exchange! Your site for questions, answers, and announcements about operations research.