Restricción binaria

En optimización matemática , una restricción binaria es una restricción que involucra exactamente dos variables .

Por ejemplo, consideremos el problema de las n reinas , donde el objetivo es colocar n reinas de ajedrez en un tablero de n x n de manera que ninguna de ellas pueda atacar a otra (horizontal, vertical o diagonalmente). El conjunto formal de restricciones es, por lo tanto, "La reina 1 no puede atacar a la reina 2", "La reina 1 no puede atacar a la reina 3", y así sucesivamente entre todos los pares de reinas. Cada restricción en este problema es binaria, ya que solo considera la colocación de dos reinas individuales. ^{[ 1 ]}

Los programas lineales en los que todas las restricciones son binarias pueden resolverse en tiempo fuertemente polinomial , un resultado que no se sabe que sea cierto para programas lineales más generales. ^{[ 2 ]}