Target oriented branch & bound method for global optimization

Publication: Working/Discussion PaperWU Working Paper

3 Downloads (Pure)

Abstract

We introduce a very simple but efficient idea for branch & bound (B&B) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new B&B approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used B&B techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical B&B techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. (author's abstract)
Original languageEnglish
Place of PublicationVienna
PublisherInstitut für Informationsverarbeitung und Informationswirtschaft, WU Vienna University of Economics and Business
Publication statusPublished - 2002

Publication series

SeriesWorking Papers on Information Systems, Information Business and Operations
Number01/2002

WU Working Paper Series

  • Working Papers on Information Systems, Information Business and Operations

Cite this