B&B method for discrete partial order and quasiorder optimizations
DOI:
https://doi.org/10.15407/dopovidi2019.01.016Keywords:
branch and bound method, discrete optimization, nondominated solutions, partial order, quasiorderAbstract
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
How to Cite
Issue
Section
License
Copyright (c) 2023 Reports of the National Academy of Sciences of Ukraine

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.