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

Igor S. Masich, Lev A. Kazakovtsev

DOI Number
https://doi.org/10.22190/FUMI1802337M
First page
337
Last page
360

Abstract


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.


Keywords

Pseudo-Boolean optimization problem, branch-and-bound method, Constrained pseudo-Boolean optimization problem.

Keywords


pseudo-Boolean optimization; comminatorial optimization; branch-and-bound method

Full Text:

PDF

References


S. Ahmed, M. Tawarmalani, N. V. Sahinidis: A finite branch-and-bound algorithm for two-stage stochastic integer programs. Mathematical Programming. 100(2) (2004), 355–377.

A. N. Antamoshkin: Regular Opimization of Pseudo-Boolean Functions. Krasnoyarsk University Press, Krasnoyarsk, 1989 (in Russian).

A. N. Antamoshkin, I. S. Masich: Heuristic search algorithms for monotone pseudo-boolean function conditional optimization. Engineering and automation problems. 5(1) (2006), 55–61.

A. Antamoshkin, I. Masich: (2007) Pseudo-Boolean Optimization in Case of an Unconnected Feasible Set. In: Models and Algorithms for Global Optimization (A. Torn, J. Zilinskas, eds.), Optimization and Its Applications, vol. 4. Springer, Boston, MA, 2007.

C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh,

P. H. Vance: Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research. 46(3) (1998), 316–329.

R. E. Bellman: Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.

C. Cotta, J. Troya: Embedding Branch and Bound within Evolutionary Algorithms. Applied Intelligence. 18 (2003), 137–153.

F. B. Cruz, G. R. Mateus, J. M. Smith: A Branch-and-Bound Algorithm

to Solve a Multi-level Network Optimization Problem. Journal of Mathematical Modelling and Algorithms. 2(1) (2003), 37–56.

J. Desrosiers, M. E. Lubbecke: Branch-Price-and-Cut Algorithms. Wiley Encyclopedia of Operations Research and Management Science, 2010.

M. A. Efroymson, T. L. Ray: A branch and bound algorithm for plant location. Operations Research. 14 (1996), 361–368.

M. Fischetti, A. Lodi, P. Toth: Solving Real-World ATSP Instances by Branch-and-Cut. Lecture Notes In Computer Science (2003), 64–77.

D. Feillet: A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR. 8(4), 407–424.

J. E. Gallardo, C. Cotta and A. J. Fernandez: A hybrid model of evolutionary algorithms and branch-and-bound for combinatorial optimization problems. 2005 IEEE Congress on Evolutionary Computation, 2005, vol. 3, pp. 2248–2254.

O. Gunluk: A branch-and-cut algorithm for capacitated network design problems. Mathematical Programming. 86(1) (1999), 17–39.

E. R. Hansen: Global optimization using interval analysis. Marcel Dekker New York, 2004.

K. Holmberg, D. Yuan: A Lagrangean Heuristic Based Branch-and-bound Approach for the Capacitated Network Design Problem. Operations Research. 48(3) (2000), 461–481.

A. H. Land, A. G. Doig: An automatic method of solving discrete programming problems. Econometrica 28 (1960), 397–520.

E. L. Lawler and D. E. Wood: Branch and bounds methods: A survey. Operations Research. 4(4) (1966), 669–719.

J. E. Mitchell: Branch and Cut. Wiley Encyclopedia of Operations Research and Management Science, 2011.

R. M. Nauss: An Improved Algorithm for the Capacitated Facility Location Problem. The Journal of the Operational Research Society. 29(12) (1978), 1195–1201.

M. Padberg, G. Rinaldi: A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Review. 33(1) (1991), 60–100.

N. Pascheuer, M. Junger, G. Reinelt. A Branch and Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Computational Optimization and Applications. 17(1) (2000), 61–84.

C. Pessan, J.-L. Bouquard, E. Neron: Genetic Branch-and-Bound or Exact Genetic Algorithm? In: Artificial Evolution (N. Monmarche, EG. Talbi, P. Collet, M. Schoenauer, E. Lutton, eds.), EA 2007. Lecture Notes in Computer Science, vol. 4926. Springer, Berlin, Heidelberg, 2008.

E. L. F. Senne, L. A. N. Lorena, M. A. Pereira: A branch-and-price approach to p-median location problems. Computers and Operations Research. 32(6) (2005), 1655–1664.

M. Tawarmalani, N. V. Sahinidis: Global optimization of mixed-integer non-linear programs: A theoretical and computational study. Mathematical Programming. 99(3) (2004), 563–591.

D. Vandenbussche, G. L. Nemhauser: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Mathematical Programming. 102(3) (2005), 559–575.




DOI: https://doi.org/10.22190/FUMI1802337M

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)