Abstract.
We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: June 15, 1998 / Accepted: November 15, 1999¶Published online March 15, 2000
Rights and permissions
About this article
Cite this article
Barahona, F., Anbil, R. The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385–399 (2000). https://doi.org/10.1007/s101070050002
Issue Date:
DOI: https://doi.org/10.1007/s101070050002