Binär begränsning

En binär begränsning , i matematisk optimering , är en begränsning som involverar exakt två variabler.

Tänk till exempel på n-queens-problemet , där målet är att placera n schackdamer på ett n -by- n schackbräde så att ingen av damerna kan attackera varandra (horisontellt, vertikalt eller diagonalt). Den formella uppsättningen av begränsningar är därför "Queen 1 can't attack Queen 2", "Queen 1 can't attack Queen 3", och så vidare mellan alla par av damer. Varje begränsning i detta problem är binär, eftersom den bara tar hänsyn till placeringen av två individuella drottningar.

Linjära program där alla begränsningar är binära kan lösas i starkt polynomisk tid , ett resultat som inte är känt för att vara sant för mer allmänna linjära program.