# How to Speed Up the subgradient optimization procedure in a Lagrangian Relaxation Scheme

I'm currently working on the following problem (a variant of maximal k-covering problem): \begin{align} \max&\quad z =\sum\limits_{\omega\in \Omega}x_{\omega} \label{imbip3a} \\ \text{s.t.}&\quad \sum\limits_{i\in \mathcal{V}}y_{i} = k & \label{imbip3b} \\ &\quad x_{\omega}\leq\sum\limits_{j\in P_\omega}y_{j} & \: \omega \in \Omega \label{imbip3c} \\ &\quad x_{\omega}, y_i \in \left\{0,1\right\} & \:i\in \mathcal{V}, \omega \in \Omega \label{imbip3d} \end{align}

My instances are typically very large with millions of variables so commercial solvers are usually get stuck. For this reason I'm using Lagrangian Relaxation where I relax the second set of constraints to obtain the following sub-problem : \begin{align} \max&\quad z_{\rm LR} =\sum\limits_{\omega\in \Omega}\left(1-\lambda_{\omega}\right)x_{\omega} + \left(\sum\limits_{\omega\in \Omega_i} \lambda_{\omega} \right)y_i \label{imbip5a} \\ \text{s.t.}&\quad \sum\limits_{i\in \mathcal{V}}y_{i} = k \label{imbip5b} \\&\quad x_{\omega}, y_i \in \left\{0,1\right\},\quad i\in \mathcal{V}, \omega \in \Omega \label{imbip5d} \end{align}

The relaxed problem can be solved by inspection: if $$1-\lambda_{\omega}\geq 0$$, we set $$x_{\omega}$$ to one and zero otherwise. Similarly, we compute $$\sum\limits_{\omega\in \Omega_i} \lambda_{\omega}$$ values for each $$i$$ and then rank them in a descending order and pick top $$k$$ of them and set the corresponding $$y_i$$ to one. Together with subgradient optimization to update the Lagrangian parameters $$\lambda_{\omega}$$ a scalable algorithm is obtained with no need for a commercial solver.

I'm applying the classical (basic) sub-gradient method where I face a lot of zigzagging and slow convergence. I've been checking the LR and sub-gradient optimization literature and I've seen various methods to speed-up and avoid zigzagging, such as using deflected directions, bundle methods, incremental subgradients, surrogate LR..etc. I'm not sure which would help me the best and before diving to the details of each of these methods (and coding them) I would like to ask the community. So if you have any experience on these speeding methods, what would you recommend?

• what is $\Omega$ ? Jan 28, 2020 at 21:22
• I do not have experience with all the sub-gradient variants you mentioned. In my experience, I found that the variant described in the paper Accelerating the convergence of subgradient optimisation" by Baker, B.M., Sheasby, J, to perform significantly faster than the polyak step size rule. Bundle methods may work well for your case, but for smooth functions the general belief is that they are slow, as far as i know. Jan 29, 2020 at 2:14
• Thanks, I will check that paper. Here $\Omega$ is the set of samples and $V$ is set of nodes. This is a stochastic network (probabilities on the edges) and we do Monte Carlo kind of sampling to get an approximate deterministic representation of the original network. Jan 29, 2020 at 6:33

In my experience, this sort of thing just requires a lot of trial and error. An SO variant that works well for one problem may not work as well for another, so you just have to implement and test a lot of stuff.

Having said that, one important thing to determine is how good the (upper) bound is. That is, if you could find the optimal multipliers, how tight would the bound that they provide be? Your subproblem has the integrality property, so the bound will be the same as the LP relaxation bound. So you can test the LR bound just by solving the LP relaxation and comparing it to the known optimal IP solution.

If the LR bound is weak, then no amount of SO tweaking is going to help you too much. You'll have to focus instead on tightening the bound, or finding a good branching scheme.

(Actually, I suspect that your bound is relatively tight, since the max covering problem usually has tight LP bounds, and your problem is basically identical to a max-cover problem if you interpret the scenarios as customers.)

You probably already know, but Galvao and ReVelle (EJOR 1996) propose exactly the LR algorithm you are discussing. I haven't read that paper in a long time and I can't remember if they discuss solving large instances, but you could check.

• Thanks for the answer Larry. I checked the Galvao paper once more and they are discussing only the classical parameters (halving rule and initial dual values..etc). So they dont mention any insight about the newer SO variants...etc. Jan 29, 2020 at 17:35
• I had a paper proposing an LP rounding for this problem and in there we report that the LP bounds are really strong (for most of the small-sized real-life social network data that we've tested). For the worst case it can be as bad as $1-1/e$, which requires extreme level symmetry. Other than that it is almost always within 1-2% of the optimal solution and in many cases I can even get the integer solution directly.. However, my new challenge is solving for large social network, the original problem is too large to solve it as an LP. So playing with SO would still be meaningful for scaling up. Jan 29, 2020 at 17:35
• Very interesting. Sorry I can't be more help here. I hope someone else can, and I'm looking forward to seeing the successful results! Jan 29, 2020 at 18:11