Programowanie całkowitoliczbowe

Programowanie całkowitoliczbowe (PC; ang. integer programming, IP) — to dział optymalizacji matematycznej, w którym badane są zadania, gdzie niektóre lub wszystkie zmienne muszą przyjmować wyłącznie wartości całkowitoliczbowe.

Najlepiej zbadanym przypadkiem szczególnym jest całkowitoliczbowe programowanie liniowe (CPL; ang. integer linear programming, ILP), w którym funkcja celu i ograniczenia są liniowe. W odróżnieniu od programowania liniowego, gdzie zmienne mogą przyjmować dowolne wartości rzeczywiste, wymóg całkowitoliczbowości sprawia, że zadania PC są znacznie trudniejsze do rozwiązania.

Programowanie całkowitoliczbowe znajduje szerokie zastosowanie w ekonomii, logistyce, planowaniu produkcji oraz innych dziedzinach, w których zmienne mają z natury dyskretny charakter (na przykład liczba wyprodukowanych jednostek wyrobu lub liczba pracowników).

Definicja i terminologia

Ogólne zadanie całkowitoliczbowego programowania liniowego można zapisać następująco:

Znaleźć wektor $x$, który:

maksymalizuje (lub minimalizuje) $c^{T}x$

przy warunkach:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (wszystkie składowe wektora $x$ są liczbami całkowitymi)

gdzie $x$ — wektor zmiennych, $c$ i $b$ — wektory, a $A$ — macierz współczynników.

W zależności od wymagań stawianych zmiennym wyróżnia się następujące typy zadań:

• Całkowicie całkowitoliczbowe programowanie: wszystkie zmienne muszą być całkowite.
• Mieszane programowanie całkowitoliczbowe (ang. mixed-integer programming, MIP): tylko część zmiennych musi być całkowitoliczbowa.
• Programowanie boolowskie (0-1): zmienne przyjmują wyłącznie wartości 0 lub 1, co pozwala modelować logiczne decyzje typu „tak/nie".

Kluczowe właściwości i złożoność

Złożoność obliczeniowa

Zadanie całkowitoliczbowego programowania liniowego w ogólnym przypadku jest NP-trudne. Oznacza to, że nie istnieje znany algorytm zdolny do znalezienia dokładnego optymalnego rozwiązania dla dowolnego zadania PC w czasie wielomianowym. Złożoność wynika z kombinatorycznej natury zadania, ponieważ liczba możliwych rozwiązań całkowitoliczbowych może rosnąć wykładniczo wraz ze wzrostem liczby zmiennych.

Związek z programowaniem liniowym (relaksacja LP)

Dla każdego zadania PC można sformułować jego relaksację liniową — zadanie programowania liniowego (PL), w którym porzucono wymóg całkowitoliczbowości zmiennych. Rozwiązanie relaksacji LP posiada dwie ważne właściwości:

1. Można je znaleźć znacznie szybciej (w czasie wielomianowym).
2. Optymalna wartość funkcji celu relaksacji LP stanowi oszacowanie (górne ograniczenie dla zadania maksymalizacji i dolne dla minimalizacji) optymalnej wartości pierwotnego zadania całkowitoliczbowego.

Jednakże proste zaokrąglenie ułamkowego rozwiązania relaksacji LP do najbliższych liczb całkowitych z reguły nie prowadzi do optymalnego ani nawet dopuszczalnego rozwiązania zadania całkowitoliczbowego.

Właściwość całkowitej unimódularności

Istnieje ważna klasa zadań CPL, które rozwiązuje się równie łatwo jak ich relaksacje LP. Są to zadania, w których macierz ograniczeń $A$ jest całkowicie unimódularna (to znaczy wyznacznik każdej jej kwadratowej podmacierzy jest równy 0, +1 lub −1). Jeśli macierz $A$ jest całkowicie unimódularna, a wektor $b$ jest całkowitoliczbowy, to wszystkie wierzchołki wielościanu rozwiązań dopuszczalnych relaksacji LP będą automatycznie całkowitoliczbowe. W konsekwencji rozwiązanie znalezione metodą simpleks będzie całkowitoliczbowe. Przykładami takich zadań są zadanie transportowe i zadanie przydziału.

Metody rozwiązywania

Do rozwiązywania ogólnych zadań PC nieposiadających właściwości całkowitej unimódularności opracowano dokładne metody oparte na idei niejawnego przeglądu.

• Metoda podziału i ograniczeń (ang. Branch and Bound) — podstawowa metoda dokładna, opierająca się na systematycznym podziale zbioru rozwiązań dopuszczalnych na podzbiory (rozgałęzianie) i odcinaniu tych podzbiorów, które z pewnością nie zawierają optymalnego rozwiązania. Do oceny perspektywiczności podzbiorów stosuje się relaksację LP.

• Metoda płaszczyzn tnących (metoda Gomory'ego; ang. Cutting Plane Method) — iteracyjne podejście polegające na sukcesywnym dodawaniu do zadania nowych liniowych ograniczeń („cięć"). Cięcia te „odcinają" ułamkowe rozwiązania relaksacji LP, nie eliminując żadnego dopuszczalnego rozwiązania całkowitoliczbowego, stopniowo przybliżając obszar rozwiązań dopuszczalnych relaksacji LP do otoczki wypukłej rozwiązań całkowitoliczbowych.

Współczesne solwery zazwyczaj stosują algorytmy hybrydowe, takie jak metoda podziału i cięć (ang. Branch and Cut), która łączy zalety obu podejść.

Przykłady i obszary zastosowań

Programowanie całkowitoliczbowe pozwala modelować wiele klasycznych zadań optymalizacji kombinatorycznej.

• Zadanie plecakowe: klasyczne zadanie programowania 0-1, w którym należy wybrać zestaw przedmiotów o maksymalnej łącznej wartości, nie przekraczając przy tym ograniczenia na całkowitą wagę.
• Problem komiwojażera: zadanie wyznaczenia najkrótszej trasy przechodzącej przez zadany zbiór miast. Może być sformułowane jako zadanie programowania całkowitoliczbowego, w którym zmienne odpowiadają za włączenie krawędzi grafu do wynikowej trasy.

Dzięki swojej elastyczności PC jest jednym z najbardziej poszukiwanych narzędzi w badaniach operacyjnych i znajduje zastosowanie w takich dziedzinach jak:

• Logistyka i zarządzanie łańcuchami dostaw: optymalizacja tras transportu, lokalizacji magazynów, zarządzanie zapasami.
• Planowanie produkcji: układanie harmonogramów produkcji, przydział zasobów, obciążenie maszyn.
• Finanse i ekonomia: tworzenie portfela inwestycyjnego, budżetowanie nakładów kapitałowych.
• Telekomunikacja i energetyka: projektowanie sieci komunikacyjnych, planowanie pracy bloków energetycznych.

Zobacz też

• Programowanie liniowe
• Metoda podziału i ograniczeń