A Potential Reduction Algorithm Allowing Column Generation
Yinyu Ye · SIAM Journal on Optimization · 1992
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Optimization · Society for Industrial and Applied Mathematics · article · 1992
Abstract
Using the Dantzig–Wolfe decomposition technique, a potential reduction algorithm allowing column generation for the linear feasibility (LF) problem is developed. The point of departure is a simple containing polytope and its analytic center. In each iteration, an inequality violated at the current center is selected, used to cut the polytope, and then used to find the new center for the shrunken polytope. The potential value associated with the containing polytope is reduced by a constant at each step, and the algorithm is terminated in a polynomial time that depends only on the number and data length of the inequalities generated in the iterative process.
Open the resolved locator · 10.1137/0802002
Metadata licence: OpenAlex metadata (CC0)