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

Question

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?

Answer 1

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.