Podręcznik
1. Programowanie w ograniczeniach
1.5. Programowanie w ograniczeniach vs programowanie matematyczne
Poniższa tabela charateryzuje programowanie w ograniczeniach na tle programowania matematycznego.
| Programowanie matematyczne | Programowanie w ograniczeniach |
|---|---|
| Obliczenia numeryczne | Przetwarzanie w logice |
| Relaksacja | Inferencja (propagacja ograniczeń) |
| M. in. metoda podziału | Metoda podziału |
| Ograniczenia liniowe | Wysokopoziomowe modelowania |
| Niezależność od modelu | Przetwarzanie bazujące na ograniczeniach |
W programowaniu matematycznym ograniczenia opisują problem, ale w ogólnej sytuacji, nie określają jak problem można rozwiązać. W programowaniu w ogrniczeniach, każdego ograniczenie uruchamia procedurę, która odcina rozwiązania niedopuszczalne. Rozwiązywanie problemu w programowaniu matematycznym to przede wszystkim przekształcenia algebraiczne, podczas gdy w programowaniu w ograniczeniach znaczącą rolę odgrywa dedukcja logiczna dotycząca dopuszczalności i zawężania domen zmiennych. Jednym z podstawowych narzędzie w programowaniu matematycznym, w szczególności ze zmiennymy całkowitoliczbowymi, jest relaksacja ograniczeń i rozwiązanie tak otrzymanego zadania. Dla programowania w ograniczeniach podstawowym narzędziem jest wnioskowanie, inferencja w oparciu o ograniczenia przy zadanym cząstkowym rozwiązaniu. Oba podejścia często wykorzystują metodę podziału domeny zmiennych, przy czym dla programowania matematycznego jest to rozwiązanie opcjonalne (istnieją inne metody), a dla programowania w ograniczeniach jest to podejście centralne.
Programowanie matematyczne często wymaga liniowości ograniczeń (programowanie liniowe), co powoduje, że może być niezbędne zastosowanie pewnych zabiegów związanych z modelowaniem, w szczególności wymagających wprowadzenia dodatkowych zmiennych lub ograniczeń. Ograniczenia w programowaniu w ograniczeniach mogą mieć dość dowolny charakter i w szczególności przedstawiać zależności logiczne, które w programowaniu liniowym mogą wymagać specjalnego modelowania.
Nie można powiedzieć, że któreś z obydwu podejść jest lepsze w ogólnym przypadku. Programowanie w ograniczeniach bywa często bardziej efektywne w zadaniach harmonogramowania, szczególnie, gdy relaksacja okazuje się słabym narzędziem. Język modelowania w przypadku programowania w ograniczeniach jest bardziej elastyczny i ekspresyjny, dzięki czemu modele często są mniejsze, bardzie zwarte i jednocześnie czytelniejsze i bardziej podatne na zmiany. Z drugiej strony programowanie w ograniczeniach ma trudności ze zmiennymi ciągłymi, choć prowadzi do znalezienia rozwiązań dopuszczalnych to może być nie wystarczające do znalezienia rozwiązań optymalnych. Wymaga również dobrej propagacji ograniczeń, tzn. propagacji, która będzie efektywnie zawężać domeny zmiennych, co nie zawsze ma miejsce. Właściwości obu metod skłaniają do pomysłu integracji programowania matematycznego i programowania w ograniczeniach, np. w postaci rozszerzenia metody podziału i oszacowań o propagacje ograniczeń lub wykorzystania propagacji ograniczeń do generowania silniejszych cięć w metodzie płaszczyzn tnących.