A BRANCH-AND-BOUND ALGORITHM FOR A PSEUDO-BOOLEAN OPTIMIZATION PROBLEM WITH BLACK-BOX FUNCTIONS

Autor:	I S Masich, Lev A. Kazakovtsev
Rok vydání:	2018
Předmět:	Mathematical optimization Random search Optimization problem Branch and bound Computer science Feasible region Boundary (topology) Monotonic function Greedy algorithm Unimodality
Zdroj:	Facta Universitatis, Series: Mathematics and Informatics. 33:337
ISSN:	2406-047X 0352-9665
Popis:	We consider a conditional pseudo-Boolean optimization problem with both the objective function and all constraint functions given algorithmically (black-box functions) and defined on {0, 1}n only. We suppose that these functions have certain properties, for example, unimodality and monotonicity. To solve problems of this type, we propose an optimization algorithm based on finding boundary points of the feasible region and the branch-and-bound method. The developed algorithm is aimed at the reception of an exact solution of an optimization problem. In addition, this algorithm can be used as an improvement of approximate algorithms such as the greedy heuristic and the random search algorithms for finding boundary points. Even after a small number of iterations (branchings), a significant improvement of the found feasible solution is achieved.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f9ca092aa53368488536c98c4c868f98 https://doi.org/10.22190/fumi1802337m Zobrazit plný text záznamu Plný text ve formátu PDF