On Finitely Terminating Branch-and-Bound Algorithms for Some Global Optimization Problems
Authors:
- Faiz A. Al-KhayyalFAFaiz A. Al-Khayyal
- Hanif D. SheraliHSHanif D. Sherali
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 10 (4) , 1049-1057
Abstract
Global optimization algorithms are typically terminated with an $\epsilon$-approximate solution after a finite number of iterations. This paper shows how existing infinitely convergent branch-and-bound algorithms can be augmented to guarantee finite termination with an exact global solution for problems having extreme point solutions.Keywords
This publication has 18 references indexed in Scilit:
- A finite concave minimization algorithm using branch and bound and neighbor generationJournal of Global Optimization, 1994
- Global Optimization1993
- Finite convergence of algorithms for nonlinear programs and variational inequalitiesJournal of Optimization Theory and Applications, 1991
- Note on solving linear complementarity problems as jointly constrained bilinear programsJournal of Mathematical Analysis and Applications, 1991
- Exhaustive Nondegenerate Conical Processes for Concave Minimization on Convex PolytopesMathematics of Operations Research, 1988
- A finite algorithm for concave minimization over a polyhedronNaval Research Logistics Quarterly, 1985
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Jointly Constrained Biconvex ProgrammingMathematics of Operations Research, 1983
- Khachiyan’s algorithm for linear programming1981
- Quasi-concave minimization subject to linear constraintsDiscrete Mathematics, 1974