Optymalizacja ograniczeń (lub programowanie ograniczeń) to nazwa nadana oznaczaniu możliwych rozwiązań na podstawie bardzo dużej grupy propozycji, w przypadku których problem można modelować pod kątem dowolnych ograniczeń. Problemy z CPG pojawiają się w wielu dyscyplinach naukowych i inżynieryjnych. Słowo „programowanie” jest trochę błędne, podobnie jak słowo „komputer”, które kiedyś oznaczało „osobę, która oblicza”. „programowanie” odnosi się w tym przypadku do układu planu, a nie do programowania w języku komputerowym).
Wskaźnik KPI opiera się na wykonalności (znalezieniu możliwego rozwiązania), a nie na optymalizacji (znajdowaniu optymalnego rozwiązania), i skupia się na ograniczeniach i zmiennych, a nie na funkcji celu. W rzeczywistości problem związany z CPG może nawet nie mieć funkcji obiektywnej – celem może być zawężenie bardzo dużego zestawu możliwych rozwiązań do podzbioru, który można łatwiej zarządzać, przez dodanie do niego ograniczeń.
Przykładem problemu, który dobrze sprawdza się w przypadku CP, jest planowanie pracy pracowników.
Problem ten pojawia się, gdy firmy działające nieprzerwanie – takie jak fabryki – muszą stworzyć dla swoich pracowników tygodniowy harmonogramy. Oto bardzo uproszczony przykład: firma prowadzi 3 8-godzinne zmiany dziennie i każdego dnia przypisuje 3 z 4 pracowników na różne zmiany, a czwarty ma dzień wolny. Nawet w tak małym przypadku liczba możliwych harmonogramów jest ogromna: każdego dnia możliwe jest 4! = 4 * 3 * 2 * 1 = 24 możliwych przydziałów pracowników, więc liczba możliwych harmonogramów tygodniowych wynosi 247, czyli 247.
Zwykle istnieją inne ograniczenia, które zmniejszają liczbę możliwych rozwiązań – na przykład to, że każdy pracownik pracuje co najmniej przez minimalną liczbę dni w tygodniu. Metoda CP pozwala śledzić, które rozwiązania pozostają możliwe po dodaniu nowych ograniczeń. Dzięki temu jest skutecznym narzędziem do rozwiązywania dużych rzeczywistych problemów z planowaniem.
CP ma liczną i bardzo aktywną społeczność na całym świecie, oferując czasopisma naukowe, konferencje i arsenał różnych technik rozwiązywania problemów. Wartość CP jest z powodzeniem stosowana do planowania, tworzenia harmonogramów i wielu innych domen z heterogenicznymi ograniczeniami.
Narzędzia,
Google oferuje kilka sposobów rozwiązania problemów z CP:
- Rozwiązanie CP-SAT: narzędzie do programowania ograniczeń, które wykorzystuje metody SAT (satisfiability).
- Oryginalne rozwiązanie do rozwiązywania problemów CP: narzędzie do programowania ograniczeń używane w bibliotece routingu.
Jeśli Twój problem można modelować z zastosowaniem celu liniowego z ograniczeniami liniowymi, masz problem z programowaniem liniowym i warto rozważyć narzędzie MPSolver. Jednak problemy z wyznaczaniem tras najlepiej rozwiązać, korzystając z naszej biblioteki tras przejazdu pojazdów, nawet jeśli można je przedstawić za pomocą modelu liniowego.
Przykłady
W następnej sekcji opisujemy narzędzie CP-SAT, które jest podstawowym narzędziem LUB-Tools do programowania z ograniczeniami. SAT oznacza satisfiability (rozwiązania do rozwiązywania problemów SAT oraz CPG).
Oto kilka przykładów problemów z planowaniem, które dobrze nadają się do rozwiązania CP-SAT:
Dwa klasyczne zadania CP to problem N-queen i łamigłówki kryptoarytmetyczne.