Glossario · approach
Programmazione a Vincoli
Paradigma di ottimizzazione centrato sul trovare una soluzione che soddisfi un insieme di vincoli — particolarmente forte per scheduling e assegnazione.
Constraint ProgrammingCP
La programmazione a vincoli (Constraint Programming — CP) è un approccio di ottimizzazione che definisce un problema come 'variabili + vincoli' e cerca soluzioni che soddisfino tutti i vincoli. Differenza dalla programmazione intera mista (MIP): MIP lavora su equazioni lineari e minimizza/massimizza una funzione di costo/beneficio; CP esprime vincoli logici direttamente e si concentra prima sul trovare una soluzione ammissibile, poi sul miglioramento. Per problemi con struttura 'prima zero conflitti, poi ottimizzare' — scheduling, orario lezioni, assegnazione, pianificazione turni, puzzle, configurazione — CP fornisce tipicamente soluzioni più velocemente del MIP. Sono disponibili diversi motori open-source maturi di programmazione a vincoli; esistono anche prodotti commerciali.
Örnek
Un orario scolastico: 50 docenti e 30 classi sotto molti vincoli. Il solver CP imposta 'variabili = ora + aula per ogni corso', 'vincoli = nessun conflitto'; prova assegnazioni di variabili e trova una soluzione in secondi o minuti.