How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Question

Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem. The master problem is solved to optimality (or alternatively for a MIP, every time a potential new best solution is identified while branching) and then the associated subproblem is solved. If the subproblem is feasible then the solution of the master problem is a (optimal) solution to the original problem. Otherwise a new constraint is added to the master problem to cut the current solution.

An example of this could be the following (even though I would guess that the results would be quite deceiving): If our original problem is the Capacitated Vehicle Routing Problem, a way to solve it using Benders decomposition would be to use the VRP as a master problem and in the subproblem to check that each vehicle respects its capacity constraints. If the capacity constraints are not respected we add a constraint stating that at least one arc used in the current (master problem) solution cannot be used.

In order to be able to successfully use this solution method, what are some characteristics that the original problem should display?

I have the felling that the subproblem should not be too constraining (in the sense, that for an arbitrary solution of the master problem there should be a good chance that the subproblem is feasible), but would be interested by any data backing (or refuting) this up.

Edit: One of the comments of @Michael Trick made me realise that there exist more variation of Benders decomposition than I was aware of. For clarification purposes I was referring to Combinatorial Benders decomposition .

Answer 1

In combinatorial Benders, where $x$ are the variables in the master problem and $y$ the variables in the subproblem, the purpose of the subproblem is to come up with constraints on the $x$ variables that force them to take on better values. In the case where there are no costs in the subproblem, the only issue is feasibility of the $y$ variables. In the case where the subproblem is infeasible, the Benders constraint is then of the form "If you want to avoid this particular infeasibility, then $x$ must satisfy this".

At the very weakest, the combinatorial Benders constraint is of the form "$x$ must be different than the current $x$ solution". The master problem will then find the next cheapest $x$ solution and try that. Sometimes that works, but in most cases that leads to way too many iterations.

Ideally the subproblem will cut off lots of possible $x$'s, and the likelihood that Benders will work well depends on how many $x$'s get cut off (along with other things like speed of master and subproblem solution, etc.).

To be concrete, suppose the subproblem involves assigning jobs to machines to be scheduled within some fixed time span. The master problem assigns $n$ jobs to $m$ machines, and the subproblem then determines if all jobs can be scheduled. Let the solution to the master problem be given by $x^*_{ij}$, where $x^*_{ij} = 1$ means job $i$ is assigned to machine $j$. There are multiple levels of Benders constraints that might be generated:

1) These jobs cannot be assigned to those machines in that way $$\sum_{ij| x^*_{ij} = 1} \le n-1$$

2) The $k$ jobs assigned to machine $j^*$ don't fit $$\sum_{i|x^*_{ij^*} = 1} \le k-1$$

3) The subset $J$ of the $k$ jobs assigned to machine $j^*$ doesn't fit $$\sum_{i\in J|x^*_{ij^*} = 1} \le |J|-1$$

You remove more $x$ solutions with 2) than with 1) and more with 3) than with 2).

Benders is more likely to be successful with 3) than with 1), though it might default to 1) if it is unsuccessful in identifying a 2) or 3).

In the example given by OP, it would be best to determine why capacity is not being respected and find a minimum set of customers (or arcs) that cause that infeasibility.

TL;DR If you want combinatorial Benders to work, the subproblems must do more than say "Give me another solution to try".

Answer 2

Talking about general Benders (and Geoffrion for general convex), my student @Fischenders suggested the following slides

An important remark is that Benders introduced TWO ideas: (1) working on a master relaxation involving only a subset of the variables, and (2) a machinery (the Benders cut) based on LP duality to take the remaning variables into account. In logic/combinatorial Benders you buy (1) and use a more combinatorial version of (2).

As to Combinatorial/Logic Benders cuts, they are a way to bring feasibility constraints into the master in a more combinatorial form that does not necessarily require to have a convex subproblem (to apply duality). The only requirement is that you are able to detect somehow a minimal certificate of infeasibility for the master solution, and to translate it into a linear cut for the master. Depending on the application, these kinds of cuts can be strong or weak—-one should try and see.

Answer 3

My way of understanding (Benders) decomposition is that you rather solve (two) separate problems repeatedly than your original problem once. One of the two subproblems has to be resolved with an increasing number of inequalities, derived from some "dual" information of the other subproblem; while the second problem usually is solved for some variable values fixed from the solution of the first subproblem. The first subproblem is usually called the master problem.

So to answer your question, in order to determine if a problem is fit to be solved using Benders decomposition you need to identify in your problem the partition in constraints/variables such that you can have two subproblems that satisfy the following conditions.

1. (Master) subproblem: Can be efficiently solved, and can accommodate extra linear inequalities (Benders cuts). This is usually the case with a well structured MIP.
2. Subproblem: Arises when fixing some variables given by the Master subproblem's solution, can be efficiently solved, and you can obtain an optimality proof to derive the cuts. In this case, you do not need to have a linear program, meaning that you can use other methods to efficiently solve the problem.

A final note that you should take into account. The Benders cuts are there to approximate the feasible region of the second subproblem using linear inequalities, such that they inform the master problem about violations or suboptimalities that come from this subproblem. The inequalities can be seen as outer-approximation of the feasible region of the subproblem. For instance, if the subproblem's feasible region in nonconvex and the outer-approximations cut off parts of that feasible region Benders decomposition is not guaranteed to converge.

Answer 4

Most importantly, you need to define a subproblem that you can solve as LP without violating integrality constraints.

In many mixed integer programs, it is not possible/sensible to find a subproblem that can be written as LP without relaxing original constraints on integrality of variables.

It is even better if that subproblem (or its dual, which is more interesting in this case) can be solved "by inspection", rather than really using an LP solver because this usually speeds up things a lot. This means that fixing the master variables, the subproblem is a trivial problem whose solution can be derived by simple calculation.