Finiteness Result for the Simplicial Branch-and-Bound Algorithm Based on ω-Subdivisions

M. Locatelli and U. Raber
Additional contact information
M. Locatelli: Universitá di Torino
U. Raber: University of Trier

Journal of Optimization Theory and Applications, 2000, vol. 107, issue 1, No 5, 88 pages

Abstract: Abstract The question of the finiteness of simplicial branch-and-bound algorithms employing only ω-subdivisions is considered. In Ref. 1, it was shown that this algorithm is convergent; here, it is proved that the algorithm is also finite if two assumptions are fulfilled. The first assumption requires the function values at vertices of the initial simplex to be lower than the optimal value of the problem. The second assumption requires each vertex of the initial simplex to violate at most one of the constraints defining the feasible polytope. The first assumption is mild from a theoretical point of view; the second assumption is strong, but holds always for instance when the feasible region is a hypercube.

Keywords: concave minimization; ω-subdivisions; finiteness (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1023/A:1004656716776 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:107:y:2000:i:1:d:10.1023_a:1004656716776

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1004656716776

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().