Logical Benders Decomposition
John Mitchell

Linear programs with complementarity constraints (LPCCs) arise, for example, in the modeling of bilevel problems. In such a problem, the constraints include the requirement that some of the variables should be optimal solutions to another problem. For example, when designing a traffic network, the designer needs to account for the fact that individual travelers will usually try to find an optimal solution to their own shortest path problems. The lower level optimization problem can be modeled using its KKT optimality conditions under certain assumptions, which leads to complementarity constraints between slack variables and dual multipliers. For more examples of LPCCs, see [3].

LPCCs can be solved using a variant of Benders decomposition. We consider the LPCC

             T        T        T
minx,y,w    c x  +   d y   +  g  w
subject to  Ax   +    By   +   Cw   =   b
              0  ≤     y   ⊥     w  ≥   0
              x                     ≥   0
(1)

where x n, y,w m, b k, and all other vectors and matrices are dimensioned appropriately. The orthogonality constraint between y and w gives the problem a combinatorial flavor: for each component i ∈{1,,m}, either set yi = 0 or set wi = 0.

To simplify the presentation, we assume the LP relaxation of (1) is feasible.

If we know upper bounds on each component of y and w, we can construct an equivalent mixed integer program to (1):

minx,y,w,z   cTx  +   dTy  +   gTw
subject to  Ax   +   By   +    Cw   =   b
              0  ≤     y            ≤   D z
                                          1
                       0  ≤     w   ≤   D2(e - z)
              x                     ≥   0
                                 z  ∈   Bm
(2)

where D1 and D2 are diagonal matrices whose diagonal entries contain the upper bounds on y and w respectively, and e is a vector of ones. If bounds are not known, we can use a logical Benders decomposition approach to solve the problem. We again use binary variables z Bm, and we use them to enforce the complementarity restriction. The LPCC (1) can be represented equivalently as

minm φ(z) :=   minx,y,w    cT x  +  dT y  +   gTw
z∈B           subject to  Ax   +   By   +   Cw    =  b
                                    yi            ≤  0  if zi = 0
                                             w    ≤  0  if z = 1
                                               i           i
                                          x,y,w   ≥  0
(3)

By LP duality, φ(z) can be expressed equivalently as:

                          T
mzi∈nBm φ(z) =  max λ,μ,ν    bT λ
             subject to  A  λ                 ≤  c
                         BT λ  -   μ          ≤  d
                         CT λ         -    ν  ≤  g
                                   μ          =  0  if z = 1
                                    i                   i
                                          νi  =  0  if zi = 0
                                        μ, ν  ≥  0
(4)

since the primal constraint yi 0 only exists if zi = 0, so the corresponding dual variable μi can only be nonzero if zi = 0, or equivalently μi = 0 if zi = 1.

In the algorithmic framework, we have a Master Problem to pick z. We then solve the subproblem (4) to find φ(z) and find constraints to add to the Master Problem and restrict the choice of z.

Let (ˆ
λ,ˆμ,ˆν) be an optimal dual solution to the subproblem for a particular , so φ() = bT ˆλ. If this is the best z seen so far, then we store as the incumbent solution. Initially, there may be no incumbent solution, so the first feasible z becomes the first incumbent.

We want to minimize φ(z), so we want to restrict attention to choices of z that are better than . Any z that allows the dual feasible solution (ˆ
λ,ˆμ,ˆν) will have value at least φ(), so we add a constraint on z to rule this out:

 ∑         ∑
     zi +      (1 - zi) ≥ 1.
i:μˆi>0     i:ˆνi>0
(5)

This constraint forces either zi = 0 for some i with ˆνi > 0 or zi = 1 for some i with ˆμi > 0. For such a z, the constraints in the subproblem would either force νi = 0 for some i with ˆνi > 0 or force μi = 0 for some i with ˆμi > 0.

Similar cuts can be defined when (4) has an unbounded optimal value, using a ray. The positive components of the ray lead to exactly the same constraint as (5) for the Master Problem.

In practice, it is important to try to sparsity the constraint, in order to make it more powerful. This can be done by looking at requiring additional components of μ and/or ν be zero in (4), or by branching on the z variables. The sparsest constraint (5) would involve only one variable, which implies that we can fix that variable.

The Master Problem is a Satisfiability problem, since the constraints (5) are satisfiability constraints.

For more details on logical Benders decomposition for LPCCs, see [2]. For extension to quadratic programs with complementarity constraints, see [1].

1 A numerical example

We use the following example to illustrate the algorithm.

minimize    2x  + x  + 2y  - y
  (x,y,w )      1    2     1    3
subject to  x  + x  - x  = 5
             1    2    3
            - x1 + y3 + w1 = 1

            - x2 - y1 - y2 + w2 = 0
            - x1 - x2 + y2 + w3 = 2

            x ≥ 0

            0 ≤ y ⊥ w  ≥ 0
(6)

If we choose z = (1, 1, 1) we get the dual LP of the form (4) as follows:

max  λ,μ,ν     5λ1  +   λ2           +   2λ4
subject to    λ1  -   λ2           -    λ4          ≤   2
              λ1          -    λ3  -    λ4          ≤   1

            - λ1                                    ≤   0
                              - λ3          -   μ1  ≤   2
                              - λ3 +    λ4  -   μ2  ≤   0
                      λ2                    -   μ3  ≤   - 1
                      λ                     -   ν   ≤   0
                       2                         1
                               λ3           -   ν2  ≤   0
                                        λ4  -   ν3  ≤   0
                                                μ1  =   0
                                                μ2  =   0
                                                μ   =   0
                                                 3
                                               μ,ν  ≥   0
(7)

This problem is unbounded and has a ray:

dλ = (0,0,1,1),  dμ = (0,0, 0),  dν = (0,1,1).
(8)

Hence from (5), we obtain the valid constraint:

(1 - z2) + (1 - z3) ≥ 1.
(9)

One choice of z that satisfies this constraint is z = (1, 0, 1). The dual problem is then

max  λ,μ,ν     5λ1  +   λ2           +   2λ4
subject to    λ1  -   λ2           -    λ4          ≤   2
              λ1          -    λ3  -    λ4          ≤   1
            - λ                                     ≤   0
               1
                              - λ3          -   μ1  ≤   2
                              - λ3 +    λ4  -   μ2  ≤   0
                      λ2                    -   μ3  ≤   - 1
                      λ2                    -   ν1  ≤   0
                               λ            -   ν   ≤   0
                                 3               2
                                        λ4  -   ν3  ≤   0
                                                μ1  =   0
                                                ν2  =   0
                                                μ3  =   0

                                               μ,ν  ≥   0
(10)

This problem is unbounded and has a ray:

d =  (0,0,0,1),  d  = (0,1, 0),  d  = (0,0,1).
 λ                μ               ν
(11)

Hence from (5), we obtain the valid constraint:

z  + (1 - z) ≥ 1.
 2         3
(12)

One choice of z satisfying both (9) and (12) is z = (0, 0, 0). This gives the dual LP

max  λ,μ,ν     5λ1  +   λ2           +   2λ4
subject to    λ1  -   λ2           -    λ4          ≤   2

              λ1          -    λ3  -    λ4          ≤   1
            - λ1                                    ≤   0
                              - λ3          -   μ1  ≤   2
                              - λ3 +    λ4  -   μ2  ≤   0
                      λ2                    -   μ3  ≤   - 1

                      λ2                    -   ν1  ≤   0
                               λ3           -   ν2  ≤   0
                                        λ4  -   ν3  ≤   0
                                                ν1  =   0
                                                ν   =   0
                                                 2
                                                ν3  =   0
                                               μ,ν  ≥   0
(13)

This problem has an optimal solution with value 5:

λ =  (1,0, 0,0),  μ = (0,0,1 ),   ν = (0,0,0)
(14)

so from (5), we obtain the valid constraint:

z3 ≥ 1.
(15)

The choice z = (0, 0, 0) becomes the incumbent best solution found.

The satisfiability Master Problem has three constraints:

(1 - z ) + (1 - z ) ≥   1                            (16)
      2         3
      z2 + (1 - z3) ≥   1                            (17)
                z   ≥   1                            (18)
                 3
These constraints are inconsistent, so we can stop, and conclude that the best solution found is optimal. Thus, the optimal solution is z = (0, 0, 0). With this choice of z, the primal problem (3) has the form
minimize    2x  + x  + 2y  - y
  (x,y,w )      1    2     1    3
subject to  x  + x  - x  = 5
             1    2    3
            - x1 + y3 + w1 = 1

            - x2 - y1 - y2 + w2 = 0
            - x1 - x2 + y2 + w3 = 2

            x,y,w  ≥ 0

            y1 = y2 = y3 = 0
(19)

The optimal solution is

x = (0,5,0),  y = (0,0, 0),  w = (1,5, 7),
(20)

achieving the value 5.

References

[1]   L. Bai, J. E. Mitchell, and J. S. Pang. On convex quadratic programs with linear complementarity constraints. Computational Optimization and Applications, 54(3):517–554, 2013.

[2]   J. Hu, J. E. Mitchell, J.S. Pang, K. P. Bennett, and G. Kunapuli. On the global solution of linear programs with linear complementarity constraints. SIAM Journal on Optimization, 19(1):445–471, 2008.

[3]   J. Hu, J. E. Mitchell, J.S. Pang, and B. Yu. On linear programs with linear complementarity constraints. Journal of Global Optimization, 53(1):29–51, 2012.