B&B method for discrete partial order and quasiorder optimizations

Authors

  • V.I. Norkin V.M. Glushkov Institute of Cybernetics

DOI:

https://doi.org/10.15407/dopovidi2019.01.016

Keywords:

branch and bound method, discrete optimization, nondominated solutions, partial order, quasiorder

Abstract

The paper extends the Branch and Bound (B&B) method to find all nondominated points in a partially or quasiordered space. The B&B method is applied to the so-called constrained partial/quasi order optimization problem, where the feasible set is defined by a family of partial/quasi order constraints. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are setvalued. For bounding, the method uses a set ordering in the following sense. One set is ''less or equal'' than the other set if, for any element of the first set, there is a ''greater or equal'' element in the second one. In the B&B method, the partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through the group evaluation of elements of the original space.

Downloads

References

Eichfelder, G. & Jahn, J. (2012). Vector optimization problems and their solution concepts. In Ansari, Q.H. & Yao, J.-C. (Eds.). Recent Developments in Vector Optimization (pp. 1-27). Berlin: Springer. doi: https://doi.org/10.1007/978-3-642-21114-0_1

Ehrgott, M. (2005). Multicriteria Optimization. 2nd ed. Berlin, Heidelberg: Springer.

Gorohovik, V.V. (1990). Convex and nonsmooth problems of vector optimization. Minsk: Navuka i tehnika (in Russian).

Sawaragi, S., Nakayama, H. & Tanino, T. (1985). Theory of multiobjective optimization. Orlando: Academic Press.

Fattore, M. & Bruggemann, R. (Eds.) (2017). Partial order concepts in applied sciences. Cham: Springer International Publishing AG. doi: https://doi.org/10.1007/978-3-319-45421-4

Dentcheva, D. & Ruszczyński, A. (2003). Optimization with stochastic dominance constraints. SIAM J. Optim., 14, pp. 548-566. doi: https://doi.org/10.1137/S1052623402420528

De Simone V., Marino, M. & Toraldo, G. (2009). Isotonic regression problems. In Floudas, C.A. & Pardalos, P.M. (Eds.). Encyclopedia of optimization. 2nd ed. (pp. 1774-1777). Boston, MA: Springer. doi: https://doi.org/10.1007/978-0-387-74759-0_311

Khan, A. A., Tammer, C. & Zălinescu, C. (2015). Set-valued optimization. An introduction with applications. Berlin, Heidelberg: Springer.

Gavanelli, M. (2001). Partially ordered constraint optimization problems. In: Walsh, T. (eds.). Principles and practice of constraint programming — CP 2001. CP 2001. Lecture Notes in Computer Science, Vol. 2239. Berlin, Heidelberg: Springer. doi: https://doi.org/10.1007/3-540-45578-7_64

Przybylski, P. & Gandibleux, X. (2017). Multi-objective Branch and Bound. Eur. J. Oper. Res. 260, Iss. 3, pp. 856-872. doi: https://doi.org/10.1016/j.ejor.2017.01.032

Norkin, V. I. (2017). B&B solution technique for multicriteria stochastic optimization problems. In Butenko, S., Pardalos, P. & Shylo V. (Eds.). Optimization methods and applications (pp. 345-378). Cham: Springer. doi: https://doi.org/10.1007/978-3-319-68640-0_17

Nishnianidze, Z. G. (1984). Fixed points of monotone multivalued operators. Soobshch. Akad. Nauk Gruzin. SSR, 114, No. 3, pp. 489-491.

Yang, X. Q. (1992). A Hahn—Banach theorem in ordered linear spaces and its applications. Optimization. 25, No. 1, pp. 1-9. doi: https://doi.org/10.1080/02331939208843803

Downloads

Published

28.03.2024

How to Cite

Norkin, V. . (2024). B&B method for discrete partial order and quasiorder optimizations. Reports of the National Academy of Sciences of Ukraine, (1), 16–22. https://doi.org/10.15407/dopovidi2019.01.016

Issue

Section

Information Science and Cybernetics