inestabilidad numérica de la programación entera

Question

Supongamos que la función objetivo $f$ de algunas IP tiene el siguiente aspecto $$ f = \sum x_i + \varepsilon \sum y_i.$$ Con $\varepsilon$ siendo muy pequeño ( $\approx 0.00001$ ) y $x_i$ y $y_i$ algunas variables. También puede haber algunas restricciones, pero no nos centremos en ellas. Parece que los solucionadores de PI tienen problemas para resolver este tipo de PI, debido a la inestabilidad numérica. (No soy en absoluto un experto en solucionadores de PI).

¿Existe alguna forma de reformular el PI, de forma que éste pueda seguir resolviéndose de forma eficiente?

El objetivo del pequeño $\varepsilon$ es hacer que la minimización de la $\sum y_i$ una prioridad secundaria. En otras palabras, entre las soluciones que minimizan $\sum x_i$ , intenta minimizar $\sum y_i$ .

Answer 1

Puedes intentar hacerlo en dos etapas. Primero resolver el problema con el objetivo original de minimizar $\sum x_i$ y limitaciones originales. Supongamos que la solución óptima tiene $\sum x_i = s$ . A continuación, resuelva el problema con la restricción adicional $\sum x_i = s$ y el objetivo de minimizar $\sum y_i$ .

Answer 2

Creo que efectivamente el pequeño valor de epsilon es el problema. Mi sugerencia es cambiar el objetivo a $M \sum x_i + \sum y_i$ , donde $M$ es un número grande (al menos lo suficientemente grande como para priorizar $\sum x_i$ en $\sum y_i$ . Esto se ha aplicado en ejemplos en los que $x_i >0$ significa inviabilidad, por ejemplo, porque $x_i$ señala que algo está sin asignar.