3
$\begingroup$

When I think of Benders Decomposition, I typically think of two-stage stochastic programs. However, I was wondering if there is any application to decomposing a large scale deterministic MILP with only one sub problem each iteration. A potential application could be say a large scale supply chain model where facility location decisions are binary and flow variables and inventory decisions are continuous. For illustration, assume we have an MILP problem split into a master/sub problem as in benders:

The master problem (MP)

$$\min_{x,\theta} c^T x + \theta\\ \text{s.t. } Ax \leq b\\ x \geq 0\\ \text{opt. cuts}\\ x \in \mathbb{Z}$$

The Sub problem (SP) where $(\hat{x_k},\hat{\theta_k})$ is the solution to MP at iteration $k$

$$\min_y d^Ty\\ \text{s.t. } Wy = h-T\hat{x_k}\\ y\geq 0 \\ y \in \mathbb{R}$$

We would then solve the MP and SP for $k = 0,1,2,\dots,n$ adding optimality cuts (assume the subproblem is always feasible for this example) to the master problem in the form $\theta \geq \pi_k^T(h-Tx)$ at each iteration where $\pi_k$ are the optimal dual vectors.

My questions are:

Does having only one subproblem each iteration (as opposed to a multi-cut Benders approach to stochastic programs) limit the effectiveness and number of cuts added to the MP?

For a very large MILP, would decomposing the problem in this way lead to any benefit or does the eventual large number of cuts added to the MP make it too difficult to solve?

Is there a name for this approach so that I can find any literature or published applications where I could learn more?

$\endgroup$
6
$\begingroup$

Is there a name for this? Yes: Benders decomposition. I'm pretty sure the seminal work by Jack Benders (1962) had only a single LP subproblem (and was most definitely deterministic in nature).

Does having a single subproblem limit the effectiveness and number of cuts? I don't think so.

Is there a benefit to doing it? I think the answer is generally no, with three exceptions. In Benders's day, mainframes had very limited memory, so decomposition might be the only way to handle an industrial-size problem. Today we have way more memory, much faster processors (and more than one per machine) and algorithms tailored for sparse matrices (which most large problems have). So while I have not tested it, my theory is that most single-subproblem decompositions are better left as a single MILP.

The first exception is the current version of what I suspect motivated Benders. If your problem is so big that, even in sparse matrix form, it won't fit in memory, decomposition may be your only hope.

The second exception is when the original MILP has "big M" constraints of the form "enforce this constraint if binary variable x is 1 but not if x is 0" (or vice versa), and the best known safe value of M is annoyingly large (which makes for loose bounds and possibly numerical problems). For that case, there is something I know as "combinatorial Benders cuts", in which you may well have only one subproblem but by decomposing you are able to get rid of those pesky Ms.

The third exception, sometimes known as "logical Benders decomposition" (or, when I do it, "illogical Benders decomposition"), is a bit more esoteric. It uses what may well be a single subproblem that is not a linear program. It is used when the relationship between the integer (usually binary) variables and the continuous variables cannot be expressed with linear equations and inequalities.

$\endgroup$

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.