Розробка точного методу для моделі нуль-один лінійного програмування

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2020.211793

Ключові слова:

0–1 ЛП, унімодулярний, нерівності клік, перевірка здійсненності, змінна сума, двійник

Анотація

У статті представлений новий метод вирішення задач 0–1 лінійного програмування (ЛП). Загальні 0–1 ЛП вважаються NP-важкими, і до цих пір не знайдений послідовний ефективний загальний алгоритм для цих моделей. Найбільш ранніми точними методами для 0–1 ЛП були метод січних площин і метод гілок і меж. На жаль, самі по собі ці методи не змогли послідовно і ефективно вирішити модель 0–1 ЛП. Гібриди, що представляють собою комбінацію евристики, вiдсiчень, гілок і меж, а також ціноутворення, успішно використовувалися для деяких моделей 0–1. Основною проблемою гібридів є те, що вони не можуть повністю усунути загрозу комбінаторного вибуху для дуже великих практичних 0–1 ЛП. У даній статті пропонується метод зниження складності 0–1 ЛП. Дана задача використовується для створення більш простої версії задачi, яка потім вирішується поетапно таким чином, що отримане рішення перевіряється на здійсненність і вдосконалюється на кожному етапі до тих пір, поки не буде знайдено оптимальне рішення. Нова задача має матрицю коефіцієнтів тільки 0 с і 1 с. З даного дослідження можна зробити висновок, що для кожної 0–1 ЛП з допустимим оптимальним рішенням існує ще одна 0–1 ЛП (звана в даній статті двійником) з точно таким же оптимальним рішенням, але з іншими обмеженнями. Обмеження двійника складаються тільки з 0 с і 1 с. Двійника 0–1 ЛП непросто визначити простим оглядом, але його можна отримати поетапно, як показано на числовому прикладі, представленому в цій статті. Моделі 0–1 цілочисельного програмування знаходять застосування в багатьох сферах діяльності. До них відносяться великі економічні/фінансові моделі, моделі маркетингових стратегій, моделі планування виробництва та робочої сили, моделі комп'ютерного проектування та нетворкінгу, військові операції, сільське господарство, боротьба з лісовими пожежами, маршрутизація транспортних засобів, а також моделі охорони здоров'я та медицини

Спонсор дослідження

  • We are grateful to the editor and the anonymous referees. We also take this opportunity to thank NWU Faculty of Economic and Management Sciences (FEMS) for the unwavering research support.

Біографія автора

Elias Munapo, North West University Mmabatho Unit 5, Mahikeng, 2790, Mafikeng, South Africa

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences

Посилання

  1. Land, A. H., Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28 (3), 497. doi: https://doi.org/10.2307/1910129
  2. Dakin, R. J. (1965). A tree-search algorithm for mixed integer programming problems. The Computer Journal, 8 (3), 250–255. doi: https://doi.org/10.1093/comjnl/8.3.250
  3. Al-Rabeeah, M., Munapo, E., Al-Hasani, A., Kumar, S., Eberhard, A. (2019). Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models. International Journal of Mathematical, Engineering and Management Sciences, 4 (5), 1140–1153. doi: https://doi.org/10.33889/ijmems.2019.4.5-090
  4. Djeumou Fomeni, F., Kaparis, K., Letchford, A. N. (2020). A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optimization, 100579. doi: https://doi.org/10.1016/j.disopt.2020.100579
  5. Brunetta, L., Conforti, M., Rinaldi, G. (1997). A branch-and-cut algorithm for the equicut problem. Mathematical Programming, 78 (2), 243–263. doi: https://doi.org/10.1007/bf02614373
  6. Mitchell, J. E. (2001). Branch and cut algorithms for integer programming. Encyclopedia of Optimization. Kluwer Academic Publishers.
  7. Padberg, M., Rinaldi, G. (1991). A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Review, 33 (1), 60–100. doi: https://doi.org/10.1137/1033004
  8. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46 (3), 316–329. doi: https://doi.org/10.1287/opre.46.3.316
  9. Savelsbergh, M. (1997). A Branch-and-Price Algorithm for the Generalized Assignment Problem. Operations Research, 45 (6), 831–841. doi: https://doi.org/10.1287/opre.45.6.831
  10. Barnhart, C., Hane, C. A., Vance, P. H. (2000). Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems. Operations Research, 48 (2), 318–326. doi: https://doi.org/10.1287/opre.48.2.318.12378
  11. Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. de, Reis, M., Uchoa, E., Werneck, R. F. (2005). Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106 (3), 491–511. doi: https://doi.org/10.1007/s10107-005-0644-x
  12. Ladányi, L., Ralphs, T. K., Trotter, L. E. (2001). Branch, Cut, and Price: Sequential and Parallel. Computational Combinatorial Optimization, 223–260. doi: https://doi.org/10.1007/3-540-45586-8_6
  13. Taha, H. A. (2017). Operations Research: An Introduction. Pearson Educators.
  14. Winston, W. L. (2004). Operations Research Applications and Algorithms. Duxbury Press.
  15. Arbib, C., Pınar, M. Ç., Rossi, F., Tessitore, A. (2020). Codon optimization by 0-1 linear programming. Computers & Operations Research, 119, 104932. doi: https://doi.org/10.1016/j.cor.2020.104932
  16. Han, B., Li, Y., Geng, S. (2017). 0–1 Linear programming methods for optimal normal and pseudo parameter reductions of soft sets. Applied Soft Computing, 54, 467–484. doi: https://doi.org/10.1016/j.asoc.2016.08.052
  17. Kodama, A., Nishi, T. (2017). Petri net representation and reachability analysis of 0–1 integer linear programming problems. Information Sciences, 400-401, 157–172. doi: https://doi.org/10.1016/j.ins.2017.03.014
  18. Demiröz, B. E., Altınel, İ. K., Akarun, L. (2019). Rectangle blanket problem: Binary integer linear programming formulation and solution algorithms. European Journal of Operational Research, 277 (1), 62–83. doi: https://doi.org/10.1016/j.ejor.2019.02.004
  19. Bakhshi–Jafarabadi, R., Sadeh, J., Soheili, A. (2019). Global optimum economic designing of grid-connected photovoltaic systems with multiple inverters using binary linear programming. Solar Energy, 183, 842–850. doi: https://doi.org/10.1016/j.solener.2019.03.019
  20. Commoner, F. G. (1973). A sufficient condition for a matrix to be totally unimodular. Networks, 3 (4), 351–365. doi: https://doi.org/10.1002/net.3230030406

##submission.downloads##

Опубліковано

2020-10-31

Як цитувати

Munapo, E. (2020). Розробка точного методу для моделі нуль-один лінійного програмування. Eastern-European Journal of Enterprise Technologies, 5(4 (107), 6–10. https://doi.org/10.15587/1729-4061.2020.211793

Номер

Том 5 № 4 (107) (2020): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2020 Elias Munapo

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.