Two Examples of

Lagrangian Relaxation of Integer Programs

John Mitchell

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

Customers: C := {1,…,n}. For each i C, have demand d_{i}, and a time window [a_{i},b_{i}] 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 c_{ij}, with c_{0,n+1} = 0. Can arrive at customer i before time a_{i} but must then wait
until time a_{i}. Parameter t_{ij} is the time required to traverse the link from customer i to
customer j. Parameter T_{ij} = max{t_{ij} + b_{i} - a_{j}, 0}.

Variables:

Formulation:

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:

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.

Time periods N := {1,…,n}, items M := {1,…,m}, all processed on a single machine with
capacity C_{t} at time t. Have demand d_{jt} for item j at time t. Production, holding, setup costs of
item j at time t are c_{jt}, h_{jt}, and f_{jt}, 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 a_{jt} and b_{jt} respectively. Let
D_{jt} = ∑
_{i=t}^{n}d_{
jt}, the remaining demand for item j.

Variables:

Formulation:

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:

[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.