Se mostró en el documento "Programación de enteros con un número fijo de variables" que las programaciones de enteros con un número constante de restricciones (o variables) son polinomialmente solucionables.
¿Esto es válido para la programación 0-1?
cc.complexity-theory
integer-programming
Regularidad
fuente
fuente
Respuestas:
Supongo que por "programación 0-1 con un número constante de restricciones" te refieres al siguiente problema:
Maximice alguna función lineal de (x_1, x_2, ..., x_n) sujeta a las restricciones de que cada x_i está en {0,1} y un número constante de restricciones lineales adicionales.
Este problema es NP-completo incluso con 1 restricción adicional ya que se puede escribir 0-1 mochila en este formulario.
fuente
Lenstra mostró en el documento mencionado que el problema de viabilidad del programa lineal entero
es polinomialmente solucionable, si nom es constante. (Obsérvese la ausencia de una función de objetivo). Este resultado se usa comúnmente en el análisis de problemas parametrizados, es decir, se puede usar para demostrar la trazabilidad de parámetros fijos mediante una reducción.
fuente
La programación de enteros 0-1 o la programación de enteros binarios (BIP) es el caso especial de la programación de enteros donde las variables deben ser 0 o 1 (en lugar de enteros arbitrarios). Este problema también se clasifica como NP-hard, y de hecho la versión de decisión es NP-Complete.
fuente
Además de lo que dijo Robin, si entendí la pregunta correctamente, si tenemos un número constante de variables que solo pueden tomar los valores 0 o 1, un algoritmo de fuerza bruta que prueba todas las posibilidades de para las variables y comprueba si cada posibilidad obedece a las restricciones que sería un algoritmo de tiempo polinómico.k 2k
fuente