4  Lagrangian Relaxation Theories

When it comes to solving integer programming (IP) problems, linear programming relaxation is often used to obtain the lower bound of a minimization problem or upper bound of a maximization problem. The effectiveness of the bounding algorithm plays a vital role in the overall performance of branch and bound algorithms. Sometimes, we might not be interested in solving the optimization problem at hand to its optimality at all, instead, we could be happy with deriving a feasible solution from the optimal solution of the relaxed formulation. This is particularly common in industry application where proving optimality might not be as important as obtaining a near-optimal solution in reasonable computational time.

Aside from resorting to linear programming relaxation to help solve IP problem, there is another powerful decomposition algorithm, Lagrangian Relaxation, that can help obtain tight bound though another form of relaxation of the original problem. I have used this algorithm to solve some very interesting optimization problems in industry and I believe mastering the essence and intricacies of Lagrangian Relaxation could be very beneficial to the success of solving optimization problems in practice.

In the following sections, we will examine the two key components of applying Lagrangian Relaxation, namely, reformulation and problem solving through subgradient search.

4.1 Lagrangian Relaxation Reformulation

As with the case of applying other decomposition algorithm, the first step in utilizing Lagrangian Relaxation is to transform our problem at hand into a suitable format. This involves two critical steps:

• Recognizing the applicability of the Lagrangian Relaxation algorithm.
• Model reformulation.

Arguably, the first step is more challenging when facing a new optimization problem. The second step is often straightforward to do once one recognize the required structure is present in the model formulation. My experience in using the Lagrangian Relaxation is through problem solving. It is natural to build up intuition once one solves more optimization problem with this powerful algorithm. In this chapter and following chapter, we will use Lagrangian Relaxation to solve a number of classical optimization problems. Hopefully, the exercise will help us gain enough sense of recognizing when Lagrangian Relaxation is applicable.

Regarding the second point, we will see that sometimes one original problem formulation invites multiple forms of Lagrangian relaxations and some are better than others in terms of providing tighter bounds.

To illustrate the Lagrangian Relaxation process, we adopt the following primal problem model as in Fisher (2004). In the model, \(x\) are the decision variables that are nonnegative and integral. \(c\) are the cost coefficients in the objective function. There are two constraints \(Ax = b\) and \(Dx \leq e\) in the model that by putting one of them into the objective function, the remaining problem becomes easier to solve.

One example of such case is that \(Dx \leq e\) are separable constraints and \(Ax = b\) are the complicating constraints that couple all the separable constraints together. After lifting the coupling constraints into the objective function, the remaining problems consists in several independent subproblems and become much tractable to solve.

\[\begin{align} \text{min.} &\quad cx \label{p-obj} \\ \text{s.t.} &\quad Ax = b \label{p-cons1} \\ &\quad Dx \leq e \label{p-cons2} \\ &\quad x \geq 0 \ \text{and integral} \end{align}\]

To perform Lagrangian Relaxation, we define a vector of Lagrange multipliers for constraints \(\eqref{p-cons1}\) and penalize the constraint violations in the objective function.

\[\begin{align} q(u) = \text{min.} &\quad cx + u(Ax - b) \label{lr-obj} \\ \text{s.t.} &\quad Dx \leq e \label{lr-cons1} \\ &\quad x \geq 0 \ \text{and integral} \end{align}\]

Note that for any given vector of \(u\), the optimal objective value of the Lagrangian Relaxation is one lower bound of the optimal value of the original problem. The our goal is to find the optimal value of \(u^*\) that gives up the best lower bound for the original problem. This dual problem id formally defined below.

\[\begin{align} \text{max.} &\quad q(u) \\ \text{s.t.} &\quad u \ \text{unrestricted} \end{align}\]

Note that the sign of the Lagrange multipliers is decided by the form of objective sense of the original problem and the constraints that are relaxed. In the aforementioned case, the primal objective is minimization and the relaxed constraints take the ‘=’ sign. The value of \(Ax\) could be smaller or greater than \(b\) and therefore the violations could be positive or negative, which leads to the unrestricted sign of the multipliers \(u\). If the constraints \(\eqref{p-cons2}\) are relaxed, the associated Lagrange multipliers must be restricted to \(u \geq 0\).

4.2 Approximating the Optimal Lagrange Multipliers

The essential component of Lagrangian relaxation is the use of Lagrange multipliers to penalize the violation of constraints that we choose to put in the objective function. There are several approaches proposed in the literature to approximate the optimal \(u\) values. In the following section, we introduce two such algorithms, namely, subgradient search and surrogate subgradient search.

4.2.1 Subgradient search

The subgradient search algorithm was proposed by Polyak (1969). The algorithm workflow is as follows:

• Step 0: initialize stopping criteria. Set lower bound \(lb = -\infty\). Obtain the best bound \(q(u^*)\) and prepare the starting values of the Lagrange multipliers \(u^k\) with \(k\) as the iteration count, \(k=0\).
• Step 1: solve the Lagrangian Relaxation with \(u^k\) to get the optimal objective value \(q(u^k)\) and relaxed constraint violations \(g(x^k) = Ax^k - b\). Update \(lb = g(u^k)\) if \(lb < q(u^k)\).
• Step 2: checking stopping criteria. If satisfied, output the best lower bound \(lb\).
• Step 3: compute the updated Lagrange multipliers according to \[\begin{align} u^{k+1} = u^k + s^k g(x^k) \end{align}\] where \(s^k\) is the step size and is computed as \[\begin{align} s^k = \gamma \cdot \frac{q(u^*) - q(u^k)}{\lVert g(x^k) \rVert^2}, \ \gamma < 2 \end{align}\]
• Step 4: let \(k = k + 1\) and go to step 1.

In the above algorithm workflow, \(g(x^k)\) represents the violations of the relaxed constraints that are lifted into the objective function. It is also used as the subgradient to update the Lagrange multipliers.

4.2.2 Surrogate subgradient search

The surrogate subgradient search we introduce here was proposed by Bragin et al. (2015). It follows similar steps with the subgradient search algorithm with the major difference in how the step size is computed.

• Step 0: initialize stopping criteria. Set lower bound \(lb = -\infty\). Obtain the best bound \(q(u^*)\) through best available heuristic and \(x^0\) through solving the relaxed problem with \(u^0\). Let \(k = 1\). Prepare the starting values of the step size \(s^0\) using \[\begin{align} s^0 = \frac{q(u^*) - q(u^0)}{\lVert g(x^0) \rVert^2} \end{align}\]
• Step 1: update \(\alpha_k\) with \[\begin{align} \alpha_k = 1 - \frac{1}{M\cdot k^p}, \ p = 1 - \frac{1}{k^r}, \ M \geq 1, \ 0 < r < 1, k = 1, 2, \cdots \end{align}\] Then update the step size \(s^k\) using \[\begin{align} s^k = \alpha_k \frac{s^{k-1}\lVert g(x^{k - 1}) \rVert}{\lVert g(x^{k}) \rVert}, \ 0 < \alpha_k < 1, k = 1, 2, \cdots \end{align}\] Then update the Lagrange multipliers with \[\begin{align} u^{k+1} = u^k + s^k g(x^k) \end{align}\]
• Step 2: solve the relaxed problem with the updated multipliers.
• Step 3: checking stopping criteria. If satisfied, output the best lower bound \(lb\). Otherwise, go to step 1.

Bragin, Mikhail A., Peter B. Luh, Joseph H. Yan, Nanpeng Yu, and Gary A. Stern. 2015. “Convergence of the Surrogate Lagrangian Relaxation Method.” Journal of Optimization Theory and Applications 164 (1): 173–201. https://doi.org/10.1007/s10957-014-0561-3.

Fisher, Marshall L. 2004. “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science 50 (12_supplement): 1861–71. https://doi.org/10.1287/mnsc.1040.0263.

Polyak, B. T. 1969. “Minimization of Unsmooth Functionals.” USSR Computational Mathematics and Mathematical Physics 9 (3): 14–29. https://doi.org/10.1016/0041-5553(69)90061-5.