• Optimización de enteros

Los problemas de optimización lineal que requieren que algunas de las variables sean números enteros se denominan programas de números enteros mixtos (MIP).

Estas variables pueden surgir de dos maneras:

  • Variables de número entero que representan números de artículos, como automóviles o equipos de televisión. El problema es decidir cuántos de cada artículo se fabricarán para maximizar las ganancias.
    Por lo general, estos problemas se pueden configurar como problemas de optimización lineal estándar, con el requisito adicional de que las variables deben ser números enteros. En la siguiente sección, se muestra un ejemplo de este tipo de problema.

  • Variables booleanas que representan decisiones con valores del 0 al 1.
    Como ejemplo, considera un problema que implica asignar trabajadores a tareas (consulta Asignación). Para configurar este tipo de problema, puedes definir variables booleanas xi,j que equivalen a 1 si el trabajador i se asigna a la tarea j y 0 en el caso contrario.

Para obtener una buena introducción a la optimización de números enteros, te recomendamos la guía de soluciones sobre el modelado de Mosek.

Herramientas

Google proporciona algunas formas de resolver los problemas de MIP:

  • MPSolver: Es un wrapper para varios divisores de MIP de terceros, que usan técnicas estándar vinculadas y de ramas.
  • Resolución de CP-SAT: Es un agente de resolución de programación de restricciones que usa métodos de SAT (satisfacción).
  • Resolución de problemas de CP original: Es un solucionador de programación de restricciones.

¿Qué solucionador de problemas debo usar?

No hay ninguna regla estándar para decidir si se usará un solucionador de MIP o el CP-SAT. A modo de guía:

  • Los solucionadores de MIP son más adecuados para problemas que se pueden configurar como una LP estándar, pero con variables de números enteros arbitrarias, como el primer ejemplo anterior.
  • El solucionador de CP-SAT es más adecuado para problemas en los que la mayoría de las variables son booleanas, como el segundo ejemplo anterior.

En los MIP típicos que tienen variables de números enteros y booleanas, a menudo no hay una diferencia clara en la velocidad entre los dos solucionadores, por lo que tu elección puede basarse en tu preferencia personal.

Si quieres ver ejemplos en los que se usan los solucionadores MIP y CP-SAT, consulta Cómo resolver un problema de asignación y las otras secciones sobre asignaciones.

Otra forma de resolver problemas de programación de números enteros es mediante un solucionador de flujo de red.
Consulta Asignación como un problema de flujo de costo mínimo para ver un ejemplo.
En el caso de un problema que se puede configurar como un flujo de red, el solucionador de flujo de costo mínimo puede ser más rápido que los solucionadores MIP o CP-SAT. Sin embargo, no todos los MIP se pueden configurar de esta manera.