Nella parte dei vincoli che si vede nella soluzione qui sotto, ce ne sono di due tipi: quelli a 2 variabili e quelli a 3 variabili.
I vincoli a 2 variabili riguardano le coppie di ragazze che sono amiche. Ad esempio, Pamela e Naomi fanno parte di una coppia. Ma nel testo notiamo che ci sono anche triplette di amiche. Possiamo allora raggruppare i vincoli in triplette. La cosa di per sé non cambia il risultato, ma c'è un'osservazione da fare.
Prendiamo i primi tre vincoli:
x1 + x2 <= 1
x1 + x3 <= 1
x2 + x3 <= 1
Se voglio raggrupparli in un vincolo solo, potrei scrivere
2x1 + 2x2 + 2x3 <= 3
da cui tiro fuori, dividendo per due:
x1 + x2 + x3 <= 1.5
E questo significa che il mio incolo di binarietà non è propriamente espresso dal vincolo. Infatti, il fatto che ho un gruppo di 3 amiche vuol dire che devo invitarne solo 1 di quel gruppo. D'accordo che le variabili sono dichiarate binarie, e che quindi i valori non interi saranno scartati, ma se scrivo le cose per bene, ovvero
x1 + x2 + c3 <= 1
allora il solutore trova subito un upper bound migliore, rispetto a prima, mettendoci meno tempo.
Per gli amanti delle definizione, questo vincolo triplo si chiama vincolo di clique, dove la clique è un sottografo completo di un grafo. E infatti questo vincolo rappresenta proprio una clique di amiche di cui solo una va prescelta.