Delayed Disaggregation for Benders Decomposition
Yannik Rista and Michael Forbesa
a University of Queensland, Brisbane, Australia

yannik.rist@uq.net.au, m.forbes@uq.edu.au ∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 1, 2022
Keywords: Benders Decomposition; Vehicle Routing; Time windows

Introduction
Combinatorial Benders Decomposition (CBD) (Codato and Fischetti, 2006) is a variation on
Benders Decomposition Benders, 1962 for Mixed Integer Programs (MIP) where the inclusion ofconstraints in the linear subproblem is allowed to depend on the master problem variables. CBD
is often used in vehicle routing problems to handle timing constraints for vehicle routes (Ropkeet al., 2007; Alyasiry et al., 2019; Rist and Forbes, 2021), albeit without an explicit Benders
formulation. Disaggregation of the subproblem is used to produce multiple Benders cuts fromone master problem solution. Our main contribution is the idea of delayed disaggregation;
disaggregating the subproblem and optimality cuts after solving the subproblem rather thanbefore. We give an example of why this is useful for vehicle routing subproblems in particular.

Benders Decomposition with Delayed Disaggregation
In CBD, a Benders Master Problem is defined,min θ + f ⊤ y(1)θ subject to Benders Cuts

(2)

y∈D

(3)

where D ⊆ {0, 1}n and θ is the estimator of the subproblem objective. The subproblem, containing conditional constraints, is defined below.
min c⊤ tk⊤

yik = 1 =⇒ a(4)t ≤ bkt ∈ Rm
≥01≤k≤K(5)(6)

For a particular y ∗ ∈ Y , let A(y ∗ ) denote the matrix formed by the implied subproblem constraints at y ∗ . If the subproblem is optimal one may find a Minimally Responsible Subset (MRS)of constraints by taking the set of constraints with non-zero dual variables, and inferring which
presently-active master variables imply these constraints. Let YMRS ⊆ {y1 , . . . , yn } be such a
set of master problem variables, and let t∗ be the optimal subproblem solution at y ∗ . The
Combinatorial Benders Cut is  Xθ ≥ c⊤ t∗ ·yk − |YMRS | + 1yk ∈YMRS

TRISTAN XI Symposium

Original abstract submittal

Y. Rist and M. Forbes

2

The right-hand side equal to c⊤ t∗ when all variables in YMRS are set to 1 in the master problem
and non-positive otherwise. If A(y) is block-diagonal with
P L blocks, then the subproblem disaggregates into L smaller subproblems. By splitting θ = m
i=1 θi , one θi per subproblem variable,lwe can disaggregate the optimality cut into L individual cuts. Let YMRS
be an MRS for the l-thlsubproblem, and let I ⊆ {1, . . . , m} index the variables that appear in the l-th subproblem.
The disaggregated cuts read:
Xi∈Ilθi ≥Xi∈Il ci t∗i ·X

lyk − |YMRS|+1

(7)lyk ∈YMRS

To summarise the process for deriving disaggregated cuts, an integral y ∗ is found, the subproblem corresponding to A(y ∗ ) is decomposed, each component is solved and finally cuts arecalculated. We propose switching the second and third steps; to solve a single subproblem, anddecompose it afterwards (and therefore disaggregating the cuts) with full knowledge of the optimal solution. Specifically, once A(y ∗ ) is solved we can remove from A(y ∗ ) all rows whose dual
variables are 0 to construct an equivalent, reduced subproblem with constraint matrix A′ (y ∗ ).
However, since A′ (y ∗ ) contains fewer rows than A(y ∗ ) it will decompose into smaller blockdiagonal blocks. Specifically, for each block submatrix of A(y ∗ ), deleting rows will sub-divide
it into one or more sub-blocks, or remove the block entirely. We now present a class of linear
programs commonly found in vehicle routing subproblems which work well with this method ofdecomposition.

Application: Scheduling Subproblems in Vehicle Routing
In vehicle routing, Combinatorial Benders Subproblems are often linear programs (LPs) of theform given below, where E ⊆ {(i, j) | 1 ≤ i, j ≤ n} and ai , bi , ci , dij ≥ 0.
min c⊤ t(8)ti + dij ≤ tj

∀ (i, j) ∈ E(9)t i ≥ ai∀1≤i≤n(10)ti ≤ bi∀1≤i≤n(11)t≥0(12)

Examples of such vehicle routing problems include the Travelling Salesman Problem with Time
Windows, Pickup-and-Delivery Problem with Time Windows (PDPTW), and the Active Passive
Vehicle Routing Problem (APVRP). One well-known vehicle routing problem which does not fit
this classification is the Dial-A-Ride Problem, where dij < 0 for some constraints. The LP (8)–(11) can be represented using a directed graph, called a constraint graph, where nodes represent
the variables ti and edges represent the constraints eq. (9), weighted by dij , Constraints eq. (9)are called edge constraints.
If the constraint graph contains a strongly connected component (SCC) then the SCC implies
infeasibility or a simplification of the subproblem. Precisely, if any SCC edge (ti , tj ) has positive
weight then a cycle containing this edge exists which implies ti > ti . The cycle therefore
represents an infeasible subsystem. Otherwise, one can deduce that ti = tj for every pair ofvariables in the SCC and replace the SCC with a single meta-variable. Processing every SCC
in this manner, one obtains the condensation graph of the original constraint graph, which isalways acyclic.
TRISTAN XI Symposium

Original abstract submittal

Y. Rist and M. Forbes

3Solution
It is now assumed that the constraint graph is acyclic, as a result of performing the condensation
described above. It is straight-forward to solve the LP represented by the directed acyclic graph.
First, all t∗i are initialised to ai . Then, traversing the graph in topological order, the successorsof node ti are updated with t∗j ← max(t∗j , t∗i + dij ). This can be implemented as a modificationof Kahn’s Algorithm (Kahn, 1962) which runs in O(m + |E|) time. Note the invariant that t∗i
is an underestimate of the smallest value that ti can have in any feasible solution. Therefore, if
any t∗i > bi then the LP is infeasible, otherwise the solution is optimal since c ≥ 0.

Dual Variables and Optimality Cuts
With a small modification to the algorithm above, we can extract the dual variable values
from the optimal solution (assuming the problem is feasible). Whenever the update along theedge (ti , tj ) causes t∗j to increase, we store ti as the active predecessor of tj . Each node has at
most one active predecessor. If ti is the active predecessor of tj , then the edge (ti , tj ) is said tobe active. Each set of nodes connected by active edges defines a subgraph which is a tree, sinceeach node has at most one active predecessor. Lonely nodes form their own single-node trees(see figure 1 for an example). This idea is similar to the Critical Path Method of Kelley andWalker (1959).
t1

t2

t6

t9

t5

t3

t4

t7

t8

Figure 1 – Active edges and connected nodes in the constraint graph shown in red. Shaded nodes
are ti with ci > 0

These trees, whose nodes and edges are denoted by T and ET respectively, are used to calculate
an optimal solution to the dual of (8)–(11). Let πij , αi , βi denote the dual variables associatedwith constraints (9)–(11) respectively. For ti ∈ T , let Ti be subtree of T rooted at ti . It is
straightforward to show that the values,(Pk∈Tj ck if edge (ti , tj ) ∈ ET is active∗πij=0otherwise(Pk∈T ck if i is the root of a subtree T
αi∗ =0otherwiseβi∗ = 0are dual-optimal. LP (8)–(11) has the nice property that block-diagonality in the constraint∗ = 0 decomposes
matrix corresponds to connectedness in the graph. Removing edges with πij
the graph into a forest of trees whose edges are active. A Benders Optimality cut of the form(7) can be defined for each tree. Without delayed disaggregation, a cut would be added for eachconnected component of the original graph.
LP (8)–(11) has another useful property: a solution t∗ found by the algorithm described aboveis optimal for any c ≥ 0, since it minimises all variables simultaneously. Consider a hypothetical
LP for each variable ti which has the same constraints but a modified objective c′ = ci ei where ei
is the i-th unit vector. The same t∗ is optimal for each of these n subproblems, but the optimal
TRISTAN XI Symposium

Original abstract submittal

Y. Rist and M. Forbes

4

Table 1 – Examples of cut disaggregation for figure 1.
Disaggregation Kind
RegularDelayed (MRS)
Delayed (Critical Path)

No. of cuts
136Remarks
Graph is connected
The trees are {t1 , t2 , t5 }, {t7 , t6 , t8 }, {t9 }ti with ci > 0: {t1 , t2 , t5 , t6 , t8 , t9 }duals will differ. If we apply delayed disaggregation to each of these problems individually, we
find a single critical path (Kelley and Walker, 1959) of edges with non-zero duals which ends atti . We may therefore can add separated cuts for variables ti and tj even if ti and tj reside in thesame active edge tree in the original LP (the LP with objective c). Note we only need to solve
the original LP – the active edges from a variable to the root of its tree form the critical path,
which is used to calculate the cut. For example, in figure 1, the active edge tree T = {t6 , t7 , t8 }disaggregates into the critical paths (t7 , t8 ) and (t7 , t6 ). Let p be the critical path for ti anddefine Yp as a set of master problem variables which imply the edge constraints and lower boundat the start of p. Below is the optimality cut which arises from p.
 X
θi ≥ ci t∗i ·yk − |Yp | + 1yk ∈YpFinally, note that if ci = 0 then a cut is not needed. Table 1 summarises the MRS and critical
path disaggregations. The former is applicable to any LP subproblem whereas the latter relieson the graph structure of (8)–(11).

Conclusion
We presented a novel enhancement for disaggregation in CBD where disaggregation of cuts isespecially important. We showed the utility of the technique for vehicle routing subproblems.
Furthermore, we demonstrated how additional assumptions on the subproblem can lead to aneven finer level of disaggregation. The conference presentation will contain computational results
for the APVRP.

References
Alyasiry, Ali Mehsin, Michael Forbes, and Michael Bulmer (Nov. 2019). “An Exact Algorithm
for the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading”.
In: Transportation Science 53.6, pp. 1695–1705. doi: 10.1287/trsc.2019.0905.
Benders, J. F. (Dec. 1962). “Partitioning procedures for solving mixed-variables programmingproblems”. In: Numerische Mathematik 4.1, pp. 238–252. doi: 10.1007/BF01386316.
Codato, Gianni and Matteo Fischetti (Aug. 2006). “Combinatorial Benders’ Cuts for MixedInteger Linear Programming”. In: Operations Research 54.4, pp. 756–766. doi: 10.1287/
opre.1060.0286.
Kahn, A. B. (Nov. 1962). “Topological sorting of large networks”. In: Communications of theACM 5.11, pp. 558–562. doi: 10.1145/368996.369025.
Kelley, James E. and Morgan R. Walker (1959). “Critical-path planning and scheduling”. In:
doi: 10.1145/1460299.1460318.
Rist, Yannik and Michael A. Forbes (Aug. 2021). “A New Formulation for the Dial-a-RideProblem”. In: Transportation Science. doi: 10.1287/trsc.2021.1044.
Ropke, Stefan, Jean-François Cordeau, and Gilbert Laporte (2007). “Models and branch-andcut algorithms for pickup and delivery problems with time windows”. In: Networks 49.4,
pp. 258–272. doi: 10.1002/net.20177.

TRISTAN XI Symposium

Original abstract submittal