Spectral Projected Subgradient

Implementation of subgradient methods based on research papers and computational results tested on benchmark set-covering problems.

How to run

cd spectral-projected-subgradient
make
./build/bin/subgradient file_path to run spectral projected subgradient
./build/bin/subgradient file_path -b upperbound to run basic subgradient
make clean

References

Spectral Projected Subgradient (SPS)
[1] Crema, A., Loreto, M., & Raydan, M. (2007) Spectral projected subgradient with a momentum term for the Lagrangian dual approach. Computers and Operations Research, 34(10), 3174–3186.
Basic Subgradient Method (BSM)
[2] Beasley, J.E. (1990) A Lagrangian heuristic for set-covering problems. Naval Research Logistics, 37(1), 151–164.
Test problem sets
scpnre, scpnrf, scpnrg, scpnrh from Beasley’s OR library

Introduction

The set-covering problem (SCP) can be described as below.

One popular approach to solve SCP is branch-and-bound technique.
Branch: The original problem can be reduced to two subproblems by fixing one variable at 0 or 1. This can be applied recursively and forms a binary tree.
Bound: Since there are 2^n possible nodes in the binary tree, it is almost impossible to evaluate all nodes. We can prune or backtrack at a node if it is guaranteed that no better feasible primal solution can be found in its subtree. We can check this property by comparing lowerbound of the local optimal value of the subproblem with the current best primal solution which is a valid upperbound of the global optimal value.

Lowerbound: The optimal value of linear programming (LP) relaxation of the original problem is a valid lowerbound of the optimal value of the original problem. LP relaxation problem is the same as the original problem except variable can be a real number (i.e., x \in [0, 1])
Often, it is time-consuming to compute the optimal value of LP relaxation problem. Instead, we use dual of LP relaxation problem.

Because the dual problem is maximization problem, any feasible solution of the dual problem is less than or equal to the optimal value of the LP relaxation problem. Hence, it is a valid lowerbound.

Lagragian dual problem: In this project, we will use a subgradient method to compute the lowerbound. A subgradient method is an iterative algorithm to optimize a non-differential convex function. A better formulation for a subgradient method is the Lagragian dual problem.

It is known that the optimal value of the dual of LP relaxation is equal to the optimal value of the Lagragian dual problem. Hence, any feasible solution of the Lagragian dual problem is also a valid lowerbound.

In this project, I implemented two subgradient methods proposed in the literature, [1] and [2], and compared their performances. The experiments were conducted on the benchmark problems which are available on Beasley’s OR library.

The full SCP solver is under development. SPS is one componenet of the full SCP solver.

Pseudo-code

Subgradient vector

Initial Lagrangian multiplier vector