Rozwiązywanie zadań programowania całkowitoliczbowego metodą nierówności odcinających - podejście korzystające z prymalnego algorytmu sympleksowego

Programowanie całkowitoliczbowe pozwala na sformułowanie wielu NP-trudnych problemów kombinatorycznych w przejrzysty i naturalny sposób. Do rozwiązywania zadań programowania całkowitoliczbowego zostały wynalezione dwie główne techniki: metoda podziału i ograniczeń oraz metoda nierówności odcinających. W tej pracy skupimy się na nierównościach odcinających pierwotnie zaprezentowanych przez Ralpha Gomory'ego w 1956 roku. Ostatnio, He oraz Lee przedstawili nowe podejście do nierówności odcinających wykorzystujące prymalny algorytm sympleksowy zamiast dualnego algorytmu sympleksowego używanego przez Gomory'ego. Rozszerzamy to podejście na bardziej powszechną formę programów całkowitoliczbowych, standardową formę wraz z ograniczeniami dla pojedynczych zmiennych, oraz omawiamy dlaczego nasza propozycja wydaje się być bardziej odpowiednia. Dodatkowo, implementujemy oba podejścia w C++, standardowe Gomory'ego oraz nowe He i Lee. Obie techniki są porównywane na zbiorze instancji z MIPLIB oraz na instancjach problemu znajdowania maksymalnego skojarzenia ważonego.

Integer programming allows us to formulate many NP-hard combinatorial problems in a clear and natural way. Two main techniques for solving integer programming problems have been invented: branch-and-bound and cutting planes. In this thesis, we will focus on the cutting-plane method initially introduced by Ralph Gomory in 1956. Recently, He and Lee outlined new idea to cutting planes involving the primal simplex algorithm rather than the dual simplex algorithm used by Gomory. We extend this approach to the more common form of integer programs, the standard form coupled with variable bounds, and discuss why our proposition seems more suitable. Finally, we implement both ideas in C++, the standard Gomory one and the new one by Lee and He. Both approaches are compared on the battery of instances from MIPLIB as well as on instances of Maximum Weight Matching problem.