B&B method for discrete partial order and quasiorder optimizations

Norkin, VI
Dopov. Nac. akad. nauk Ukr. 2019, 1:16-22
Section: Information Science and Cybernetics
Language: English

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.

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

1. 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
2. Ehrgott, M. (2005). Multicriteria Optimization. 2nd ed. Berlin, Heidelberg: Springer.
3. Gorohovik, V.V. (1990). Convex and nonsmooth problems of vector optimization. Minsk: Navuka i tehnika (in Russian).
4. Sawaragi, S., Nakayama, H. & Tanino, T. (1985). Theory of multiobjective optimization. Orlando: Academic Press.
5. 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
6. 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
7. 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
8. Khan, A. A., Tammer, C. & Zălinescu, C. (2015). Set-valued optimization. An introduction with applications. Berlin, Heidelberg: Springer.

9. 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
10. 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
11. 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
12. Nishnianidze, Z. G. (1984). Fixed points of monotone multivalued operators. Soobshch. Akad. Nauk Gruzin. SSR, 114, No. 3, pp. 489-491.
13. 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