Lagrangian Relaxation The Weak Lower Bound

Question

I am applying Lagrangian Relaxation with Subgradient Optimization Method and trying to solve a MIP model. Before testing the large-scale instances, I wanted to see how it performs on small-size ones. I have a great problem which makes me desperate for days and I need the ideas of experienced people in OR Community of SE. I know that in SO method, choosing the good values for the parameters is highly important. Even if I apply many trial and fail tests , I get the same result: The lower bound converges well until a certain point and when the best lower bound is found as 0, (the optimum value is 1) it is getting stuck there. After that moment in the following iterations, the newly found lower bounds change slightly such as from -3,9677 to -3,8599 , so best lower bound is kept as 0. It never goes beyond 0 towards to optimum value which is 1. I got stuck at this point and I do not know which path should I follow now. I checked the evolution of multipliers etc, they all correct.

If anyone who experienced the same issue or has knowledge about this case, shares ideas with me, I will be very happy , what should I do know?

Thank you so much

Answer 1

A problem with subgradient optimization is the phenomenon of “zigzagging” in the vicinity of the optimal solution. That is, it is often seen that the direction of search in one step is almost opposite to the search direction in the previous step. This often yields very slow convergence. Many different schemes to prevent this behavior have been proposed in the literature. I will focus on two schemes proposed in (Baker and Sheasby, 1999) and (Camerini, Fratta and Maffioli, 1975). The method proposed by Baker and Sheasby is known as exponential smoothing and works as follows: In iteration $k$ of the subgradient procedure, a subgradient is found given $g^k$. In stead of moving in the direction of $g^k$, an alternative direction given by \begin{equation} h^k=(1-\alpha)h^{k-1} +\alpha g^k \end{equation} is used. Here $\alpha\in(0,1)$ and $h^0:= g^1$, meaning that we are search in the direction of the subgradient only in the first iteration.

Antoher method, with some more theoretical justification, is propsoed in Camerini et al.. Here the subgradient at iteration $k$, $g^k$, is deflected as follows \begin{equation} h^k = g^k-\delta_kh^{k-1} \end{equation} where $\delta\geq 0$ is given by the expression \begin{equation} \delta_k=\begin{cases} \gamma_k\frac{h^{k-1}\cdot g^k}{\Vert h^{k-1}\Vert^2}, &\text{if}\ h^{k-1}\cdot g^k<0\\ 0,&\text{otherwise} \end{cases} \end{equation} The parameter $\gamma_k$ should be taken from the interval $[0,2]$ for convergence to be guaranteed. Camerini et al. show that this scheme is not worse than plain subgradient optimization.

The good thing with these strategies is that they are extremely easy to implement when you have your subgradient procedure up and running. So it will only take you a couple of hours to see if it works for you.