Development of an exact method for zero-one linear programming model ; Разработка точного метода для модели ноль-один линейного программирования ; Розробка точного методу для моделі нуль-один лінійного програмування

Abstract

The paper presents a new method for solving the 0–1 linear programming problems (LPs). The general 0–1 LPs are believed to be NP-hard and a consistent, efficient general-purpose algorithm for these models has not been found so far. Cutting planes and branch and bound approaches were the earliest exact methods for the 0–1 LP. Unfortunately, these methods on their own failed to solve the 0–1 LP model consistently and efficiently. The hybrids that are a combination of heuristics, cuts, branch and bound and pricing have been used successfully for some 0–1 models. The main challenge with these hybrids is that these hybrids cannot completely eliminate the threat of combinatorial explosion for very large practical 0–1 LPs. In this paper, a technique to reduce the complexity of 0–1 LPs is proposed. The given problem is used to generate a simpler version of the problem, which is then solved in stages in such a way that the solution obtained is tested for feasibility and improved at every stage until an optimal solution is found. The new problem generated has a coefficient matrix of 0 s and 1 s only. From this study, it can be concluded that for every 0–1 LP with a feasible optimal solution, there exists another 0–1 LP (called a double in this paper) with exactly the same optimal solution but different constraints. The constraints of the double are made up of only 0 s and 1 s. It is not easy to determine this double 0–1 LP by mere inspection but can be obtained in stages as given in the numerical illustration presented in this paper. The 0–1 integer programming models have applications in so many areas of business. These include large economic/financial models, marketing strategy models, production scheduling and labor force planning models, computer design and networking models, military operations, agriculture, wild fire fighting, vehicle routing and health care and medical models ; В статье представлен новый метод решения задач 0–1 линейного программирования (ЛП). Общие 0–1 ЛП считаются NP-трудными, и до сих пор не найден последовательный эффективный общий алгоритм для этих моделей. Самыми ранними точными методами для 0–1 ЛП были метод секущих плоскостей и метод ветвей и границ. К сожалению, сами по себе эти методы не смогли последовательно и эффективно решить модель 0–1 ЛП. Гибриды, представляющие собой комбинацию эвристики, отсечений, ветвей и границ, а также ценообразования, успешно использовались для некоторых моделей 0–1. Основной проблемой гибридов является то, что они не могут полностью устранить угрозу комбинаторного взрыва для очень больших практических 0–1 ЛП. В данной статье предлагается метод снижения сложности 0–1 ЛП. Данная задача используется для создания более простой версии задачи, которая затем решается поэтапно таким образом, что полученное решение проверяется на осуществимость и совершенствуется на каждом этапе до тех пор, пока не будет найдено оптимальное решение. Новая задача имеет матрицу коэффициентов только 0 с и 1 с. Из данного исследования можно сделать вывод, что для каждой 0–1 ЛП с допустимым оптимальным решением существует еще одна 0–1 ЛП (называемая в данной статье двойником) с точно таким же оптимальным решением, но с другими ограничениями. Ограничения двойника состоят только из 0 с и 1 с. Двойника 0–1 ЛП непросто определить простым осмотром, но его можно получить поэтапно, как показано на числовом примере, представленном в этой статье. Модели 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 цілочисельного програмування знаходять застосування в багатьох сферах діяльності. До них відносяться великі економічні/фінансові моделі, моделі маркетингових стратегій, моделі планування виробництва та робочої сили, моделі комп'ютерного проектування та нетворкінгу, військові операції, сільське господарство, боротьба з лісовими пожежами, маршрутизація транспортних засобів, а також моделі охорони здоров'я та медицини