¿Por qué no se incluye el problema de mochila en la categoría de algoritmos de programación lineal a pesar de que el enunciado del problema de mochila parece similar a los problemas en programación lineal.?¿Por qué resolver Knapsack probl. no se considera como programación lineal?
Knapsack se puede escribir como programa de programación lineal entero programa. A diferencia de la programación lineal normal, este problema requiere que las variables en la solución sean números enteros. Se sabe que la programación lineal se puede resolver en tiempo polinomial, mientras que la programación lineal entera es NP-completa.
Ejercicio para el lector: demuestre que 3SAT se puede reducir a la programación lineal entera.
Trivia: existen algoritmos de aproximación para problemas tales como MAX-3SAT (una variante de 3SAT donde queremos maximizar el número de cláusulas satisfechas). Primero escribe MAX-3SAT como un programa lineal entero. Entonces, usted relaje en el programa lineal, eliminando la restricción de entero. Luego, resuelve el programa lineal en tiempo polinomial. Finalmente, dada real x i ∈ [0,1], que ellos ronda para números enteros, o Generar solución entero aleatorio y i donde probabilidad de y i = 1 es x i.
Como complemento: http://stackoverflow.com/q/3128001/395857 –
Vale la pena señalar que, en general, a menudo es relativamente fácil reducir un problema NP dado a ILP. –
@ yes123 En la programación lineal, son las restricciones que son lineales, no el tiempo. – fgb