Target oriented branch & bound method for global optimization

Stix, Volker (2002) Target oriented branch & bound method for global optimization. Working Papers on Information Systems, Information Business and Operations, 01/2002. Institut für Informationsverarbeitung und Informationswirtschaft, WU Vienna University of Economics and Business, Vienna.

Preview

PDF document.pdf Download (185kB)

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)

Item Type:	Paper
Keywords:	global optimization / branch and bound / maximum clique problem / standard quadratic optimization
Divisions:	Departments > Informationsverarbeitung u Prozessmanag. > Informationswirtschaft
Depositing User:	Repository Administrator
Date Deposited:	27 Mar 2002 13:12
Last Modified:	22 Oct 2019 00:41
URI:	https://epub.wu.ac.at/id/eprint/1696

Actions

View Item

Downloads