Two Examples of
Lagrangian Relaxation of Integer Programs
John Mitchell

This is based on material in Chapter 4 of [1].

1 Vehicle Routing Problems with Time Windows

Customers: C := {1,,n}. For each i ∈ C, have demand di, and a time window [ai,bi] for the delivery.

Vehicles: V := {1,,v} identical vehicles with capacity q. All vehicles start at end their routes at the same depot; N is the set of all nodes, which consists of the nodes C plus two copies of the depot (labelled nodes 0 and n + 1). Depot has trivially satisfied values for its time window. Cost to traverse arc (i,j) is cij, with c0,n+1 = 0. Can arrive at customer i before time ai but must then wait until time ai. Parameter tij is the time required to traverse the link from customer i to customer j. Parameter Tij = max{tij + bi - aj, 0}.

Variables:

          { 1  if vehicle k visits customer i immediately before customer  j
xijk  =
            0  otherwise
          {
 sik  =     departure time   if vehicle k visits customer i
            anything         otherwise

Formulation:

min k∈V i∈N j∈Ncijxijk (1a)
subject to k∈V j∈Nxijk = 1 i ∈ C (1b)
j∈Cdi j∈Nxijk q k ∈ V (1c)
ȷ∈Nx0jk = 1 k ∈ V (1d)
i∈Nxihk - j∈Nxhjk = 0 h ∈ C,k ∈ V (1e)
i∈Nxi,n+1,k = 1 k ∈ V (1f)
sik + tij - Tij(1 - xijk) sjk i,j ∈ N,k ∈ V (1g)
ai sik bi i ∈ N,k ∈ V (1h)
xijk binary i,j ∈ N,k ∈ V. (1i)

Lagrangian relaxation:

Constraint (1b) is the only one where the left hand side involves a sum over the vehicles. So if we dualize this constraint, we will be left with a separable problem. Let λ denote the vector of Lagrangian multipliers, with one component for each i ∈ C. To make the notation easier, we extend λ to include two additional components corresponding to nodes 0 and n + 1 and set those components equal to zero. Since the vehicles are identical, each subproblem can be regarded as a problem for a single vehicle. The part of the Lagrangian relaxation corresponding to a single vehicle can be written:

min i∈N j∈N(cij - λi)xij (2a)
subject to j∈Cdi j∈Nxij q (2b)
ȷ∈Nx0j = 1 (2c)
i∈Nxih - j∈Nxhj = 0 h ∈ C (2d)
i∈Nxi,n+1 = 1 (2e)
si + tij - Tij(1 - xij) sj i,j ∈ N (2f)
ai si bi i ∈ N (2g)
xij binary i,j ∈ N. (2h)

This is known as an elementary shortest path problem with resource constraints.

If we use a cutting plane approach to solve the Lagrangian dual, then the dual to the LP cutting plane approximation has variables corresponding to vehicle tours that satisfy the time windows. The constraints are that every customer should appear in exactly one tour.

For more details, see [21].

2 Capacitated lot sizing with setup times

Time periods N := {1,,n}, items M := {1,,m}, all processed on a single machine with capacity Ct at time t. Have demand djt for item j at time t. Production, holding, setup costs of item j at time t are cjt, hjt, and fjt, respectively. In any time period, the machine can perform many tasks; if it produces item j in time period t it must be setup in that time period for that item. Processing and setup times for item j in time t are ajt and bjt respectively. Let Djt = i=tnd jt, the remaining demand for item j.

Variables:

xjt :   production of item j in time t
sjt :   inventory of item  j at end of time period t
y  :    binary  variable equal to one if and only if item j is produced in time period  t
 jt

Formulation:

min t∈N j∈Mcjtxjt + hjtsjt + fjtyjt (3a)
subject to j∈M(ajtxjt + bjtyjt) Ct t ∈ N (3b)
sj,t-1 + xjt = djt + sjt j ∈ M,t ∈ N (3c)
xjt Djtyjt j ∈ M,t ∈ N (3d)
xjt 0 j ∈ M,t ∈ N (3e)
sjt 0 j ∈ M,t ∈ N (3f)
yjt binary j ∈ M,t ∈ N (3g)

Lagrangian relaxation:

The items are linked through constraint (3b), so we dualize this constraint, with multipliers λt for each t ∈ N. The resulting Lagrangian relaxation is separable by item, and the subproblem for item j is the following single item lot-sizing problem:

min t∈N(cjt + ajtλt)xjt + hjtsjt + (fjt + bjtλt)yjt (4a)
subject to sj,t-1 + xjt = djt + sjt t ∈ N (4b)
xjt Djtyjt t ∈ N (4c)
xjt 0 t ∈ N (4d)
sjt 0 t ∈ N (4e)
yjt binary t ∈ N (4f)

For more details, see [31].

References

[1]   P. González-Brevis. Advances in interior point methods and column generation. PhD thesis, University of Edinburgh, 2013.

[2]   S. Irnich and G. Desaulniers. Shortest path problems with resource constraints. In G. Desaulniers, J. Desrosiers, and M. M. Solomon, editors, Column Generation, chapter 2. Springer, 2005.

[3]   W. W. Trigeiro, L. J. Thomas, and J. O. McClain. Capacitated lot sizing with setup times. Management Science, 35(3):353–366, 1989.