Volume Algorithm: Training Neural Networks and Solving Difficult Linear Programs

Subgradient methods have a long history of applications in Optimization. They are known for producing fast approximate solutions in cases where more exact methods are prohibitive to use. The Volume algorithm (VA) is a subgradient method, it was developed to deal with large-scale linear programs that were too difficult for traditional algorithms. Its main advantage is that it produces approximate primal solutions as well as dual solutions. It has also shown fast convergence in practice. Here we review this method and present experiments in three different areas, which demonstrate its good performance and wide applicability. First we deal with training neural networks. We show that replacing the widely used Stochastic Gradient Descent method with the VA leads to very good results. Then we study bus routing in a medium size city. Here we tackle a linear programming relaxation that is too large to be treated with traditional linear programming algorithms. Here the VA gives tight lower bounds, and the approximate primal solution is used as the starting point for several heuristics that produce the final routing. Finally we turn our attention to the p-median problem for restructuring semistructured data. We apply the VA to the linear programming relaxation, and we decompose it in a simple way so it can be treated in parallel. We use a parallel implementation combined with a heuristic. This heuristic starts with the approximate primal solution and derives an integer solution. We show experiments with large instances coming from semistructured databases. For the majority of these cases the gap from optimality was less than 1%.