L'ottimizzazione del vincolo, o programmazione del vincolo (CP), è il nome assegnato all'identificazione di soluzioni attuabili tra un insieme molto ampio di candidati, in cui il problema può essere modellato in termini di vincoli arbitrari. I problemi di CP sorgono in molte discipline scientifiche e ingegneristiche. (La parola "programmazione" è un po' un nome improprio, un po' come "computer" significava "una persona che lavora". In questo caso, "programmazione" si riferisce alla disposizione di un piano, piuttosto che alla programmazione in un linguaggio informatico).
La metrica CP si basa sulla fattibilità (trova una soluzione fattibile) piuttosto che sull'ottimizzazione (trovare una soluzione ottimale) e si concentra sui vincoli e sulle variabili anziché sulla funzione obiettivo. Infatti, un problema CP potrebbe non avere nemmeno una funzione obiettivo: l'obiettivo può essere restringere un insieme molto ampio di soluzioni possibili a un sottoinsieme più gestibile aggiungendo vincoli al problema.
Un esempio di problema particolarmente efficace per le unità di pagamento è la pianificazione dei dipendenti.
Il problema si presenta quando le aziende che operano in modo continuo, come le fabbriche, devono creare orari settimanali per i propri dipendenti. Ecco un esempio molto semplice: un'azienda fa tre turni di otto ore al giorno e assegna a tre dei suoi quattro turni diversi ogni giorno, assegnando il quarto giorno libero. Anche in un caso così piccolo, il numero di orari possibili è enorme: ogni giorno esistono 4! = 4 * 3 * 2 * 1 = 24 incarichi possibili per i dipendenti, quindi il numero di orari settimanali possibili è pari a 247, ovvero oltre quattro miliardi.
Di solito esistono altri vincoli che riducono il numero di soluzioni attuabili, ad esempio il fatto che ogni dipendente lavori almeno un numero minimo di giorni a settimana. Il metodo CP tiene traccia delle soluzioni che sono attuabili quando si aggiungono nuovi vincoli, il che lo rende un potente strumento per la risoluzione di grandi problemi di pianificazione reali.
CP ha una comunità diffusa e molto attiva in tutto il mondo con riviste scientifiche dedicate, conferenze e un arsenale di diverse tecniche di risoluzione. La tecnologia CP è stata applicata con successo nella pianificazione, nella pianificazione e in numerosi altri domini con vincoli eterogenei.
Strumenti
Google offre diversi modi per risolvere i problemi CP:
- Risolutore CP-SAT: un risolutore di programmazione dei vincoli che utilizza metodi SAT (soddisfabilità).
- Risolutore CP originale: un risolutore di programmazione dei vincoli utilizzato nella libreria di routing.
Se il tuo problema può essere modellato con un obiettivo lineare e vincoli lineari, hai un problema di programmazione lineare e dovresti prendere in considerazione MPSolver. Tuttavia, i problemi relativi ai percorsi vengono in genere risolti meglio con la nostra libreria di percorsi dei veicoli, anche se possono essere rappresentati con un modello lineare.
Esempi
Nella sezione successiva viene descritto il risolutore CP-SAT, il risolutore principale degli strumenti OR per la programmazione di vincoli. (SAT sta per satisfiability: il risolutore utilizza tecniche per risolvere i problemi SAT insieme ai metodi CP).
Ecco alcuni esempi di problemi di pianificazione particolarmente adatti per il risolutore CP-SAT:
Due classici problemi di CP sono il problema delle N-queen e i rompicapi di crittografia.