Hace poco intenté resolver un problema de programación entera de maximización mediante programación lineal por el suelo del punto máximo, pero obtuve una respuesta errónea. Me pregunto si alguien puede explicar matemáticamente por qué lo que hice está mal. Tengo una intuición subyacente pero no puedo expresarla matemáticamente.
Respuesta
¿Demasiados anuncios?
Si sus variables son enteras, las restricciones no forman un conjunto convexo. En efecto, si sólo se consideran dos enteros, todos los puntos entre estos enteros no forman parte del conjunto, por lo que éste no es convexo.
Esto tiene importantes consecuencias, ya que la convexidad es una propiedad importante en la optimización: garantiza que cualquier mínimo local es un mínimo global. La pérdida de esta propiedad dificulta la optimización de números enteros.
Sin embargo, esta dificultad se puede solucionar demostrando que trabajar con números enteros es equivalente a trabajar con el casco convexo de los números enteros, que es convexo. Pero la programación de enteros sigue siendo NP-dura (ningún algoritmo polinómico puede resolver un programa de enteros), mientras que la programación lineal es computable en tiempo polinómico.
