In matematica, un vincolo è una condizione che limita i valori o le combinazioni di valori che una o più variabili possono assumere. Può essere espresso mediante un'equazione, una disequazione, l'appartenenza a un determinato insieme o una relazione tra variabili. Un'assegnazione di valori che rispetta un vincolo si dice che lo soddisfa.
I vincoli sono utilizzati in diversi ambiti della matematica e dell'informatica, tra cui la risoluzione di sistemi di equazioni, l'ottimizzazione matematica, la programmazione a vincoli e i problemi di soddisfacimento di vincoli.
Dato un insieme di variabili, ciascuna definita su un determinato dominio, un vincolo individua le combinazioni di valori considerate ammissibili. Un insieme di vincoli deve essere soddisfatto simultaneamente: le assegnazioni che rispettano tutte le condizioni costituiscono l'insieme delle soluzioni.
Ad esempio, la relazione
impone alle variabili reali e di assumere valori corrispondenti ai punti della circonferenza unitaria. La condizione
limita invece ai numeri reali non negativi.
I vincoli possono essere classificati in base alla forma delle condizioni imposte.
Un vincolo di uguaglianza richiede che un'espressione sia uguale a un determinato valore, per esempio:
Un vincolo di disuguaglianza delimita invece i valori ammissibili mediante una relazione d'ordine, per esempio:
Altri vincoli possono limitare il dominio delle variabili. Un vincolo di interezza, ad esempio, richiede che una o più variabili assumano esclusivamente valori interi. Più in generale, una condizione può imporre l'appartenenza di una variabile a un determinato insieme.
In un sistema di equazioni, ciascuna equazione rappresenta una condizione che deve essere soddisfatta simultaneamente alle altre. Analogamente, un sistema di disequazioni individua l'intersezione degli insiemi definiti dalle singole condizioni. Le soluzioni sono quindi i valori delle variabili compatibili con tutti i vincoli del sistema.
Nei problemi di ottimizzazione, i vincoli delimitano l'insieme nel quale viene cercato il massimo o il minimo di una funzione obiettivo. L'insieme dei punti che soddisfano tutti i vincoli è detto insieme ammissibile o regione ammissibile.
Un punto appartenente a tale insieme è detto ammissibile; un punto che non soddisfa almeno uno dei vincoli è invece detto inammissibile.
In un punto dato, un vincolo di disuguaglianza è detto attivo o vincolante se è soddisfatto come un'uguaglianza. È detto inattivo o non vincolante se è soddisfatto come disuguaglianza stretta.
In informatica, un problema di soddisfacimento di vincoli è definito da un insieme di variabili, dai rispettivi domini e da un insieme di relazioni che limitano le combinazioni ammissibili dei loro valori. Una soluzione assegna un valore a ogni variabile in modo da soddisfare simultaneamente tutti i vincoli.
Nella programmazione a vincoli, un vincolo globale esprime una relazione che coinvolge contemporaneamente più variabili. Un esempio è il vincolo alldifferent, soddisfatto quando le variabili considerate assumono valori differenti a coppie. I vincoli globali permettono di rappresentare in forma compatta condizioni che potrebbero essere espresse mediante più vincoli elementari.
Un vincolo rigido (dall'inglese hard constraint) deve essere necessariamente soddisfatto affinché una soluzione sia considerata ammissibile. Un vincolo soft esprime invece una condizione preferibile ma non obbligatoria e può rappresentare preferenze, costi o differenti gradi di soddisfacimento.
I vincoli soft sono utilizzati quando non è possibile o non è opportuno soddisfare contemporaneamente tutte le condizioni. Tra i modelli proposti per rappresentarli rientrano le gerarchie di vincoli, i problemi di soddisfacimento parziale, i problemi di soddisfacimento valutati e i formalismi basati sui semianelli.
Il formalismo basato sui semianelli, sviluppato da Stefano Bistarelli, Ugo Montanari e Francesca Rossi, fornisce un quadro algebrico comune per diverse classi di problemi, tra cui problemi di soddisfacimento classici, fuzzy, pesati e parziali.
Nei problemi MAX-CSP è consentito violare alcuni vincoli e la qualità della soluzione viene valutata in base al numero di vincoli soddisfatti.
Un semplice problema di ottimizzazione può essere espresso come:
soggetto ai vincoli:
e
dove indica il vettore .
La prima espressione definisce la funzione obiettivo da minimizzare; le altre due rappresentano rispettivamente un vincolo di disuguaglianza e uno di uguaglianza. In assenza dei vincoli, la funzione assumerebbe il valore minimo nel punto , che non appartiene però all'insieme ammissibile. La soluzione del problema vincolato è quindi .