Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках
DOI:
https://doi.org/10.15407/dopovidi2019.01.016Ключові слова:
дискретна оптимізація, квазіпорядок, метод гілок та меж, недоміновані розв’язки, частковий порядокАнотація
У роботi метод гiлок i меж/оцiнок (B&B-метод) поширюється на задачi пошуку недомiнованих елементiв у частково або квазiупорядкованій множині. B&B-метод застосовується до задач оптимiзацiї, де допустима множина сама визначається сiмейством квазiпорядкiв. Структура узагальненого B&B-методу є стандартною: вiн включає в себе розбиття на пiдзадачi, оцiнювання пiдзадач i вiдбраковування пiдзадач, але оцiнки пiдзадач вiдрiзняються, вони можуть бути множинами. Для оцiнювання пiдзадач метод використовує впорядкування множин у такому сенсi. Одна множина “менша або дорiвнює” iншій, якщо для будьякого елемента першої множини iснує “бiльший або рiвний” елемент у другiй. У B&B-методi розбиття застосовується до пiдзадач з недомiнованими верхнiми оцiнками. Пiдзадачi з малими верхнiми оцiнками (менше деякої нижньої оцiнки) видаляються. Встановлено збiжнiсть методу до множини всiх недомiнованих елементiв. Прискорення по вiдношенню до переборного пошуку досягається за рахунок групової оцiнки елементiв вихiдного простору.
Завантаження
Посилання
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
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2023 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
