Se sabe que los programas lineales con una matriz de sistema totalmente unimodular tienen un punto óptimo entero. Por lo tanto, son resolubles mediante la relajación de las restricciones enteras a intervalos.
Otro fenómeno interesante se produce en las relajaciones de la programación lineal a funciones pseudobooleanas cuadráticas. Si esas relajaciones tienen un punto óptimo $x$ para lo cual $x_i=0$ entonces existe una solución óptima para el problema original $x^* $ para lo cual $x^*_i=0$ . La analogía es válida para $x_i=1$ . Es decir, aunque la solución no sea integral (booleana), los puntos que lo son siguen diciendo algo sobre la solución del problema original.
¿Existe una propiedad general de los programas enteros (0/1), similar a la unimodularidad total, que permita sacar conclusiones sobre soluciones parcialmente óptimas como ésta?
