Premium
On the hierarchy of γ‐valid cuts in global optimization
Author(s) -
Porembski Marcus
Publication year - 2008
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20257
Subject(s) - decomposition , minification , mathematics , mathematical optimization , convergence (economics) , hierarchy , cutting plane method , degenerate energy levels , plane (geometry) , geometry , economics , integer programming , market economy , ecology , physics , quantum mechanics , biology , economic growth
Concavity Cuts play an important role in concave minimization. In Porembski, J Global Optim 15 (1999), 371–404 we extended the concept underlying concavity cuts which led to the development of decomposition cuts. In numerical experiments with pure cutting plane algorithms for concave minimization, decomposition cuts have been shown to be superior to concavity cuts. However, three points remained open. First, how to derive decomposition cuts in the degenerate case. Second, how to ensure dominance of decomposition cuts over concavity cuts. Third, how to ensure the finite convergence of a pure cutting plane algorithm solely by decomposition cuts. These points will be addressed in this paper. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008