In this paper we present a mathematical programming approach to tighten a Big-$M$ formulation ($P_M$) of a Mixed Integer Problem with Logical Implications ($P$). If $M_0$ is a valid vector (the optimal solutions of $P$ belong to the feasible solutions set of $P_{M_0}$) our procedures find a valid vector $M$ such that $M \leq M_0$. As a consequence, the upper bounds generated by using the linear relaxations of $P_M$ are stronger when $M \neq M_0$. As a result, an standard branch and cut algorithm can be used to try to solve $P$ by using $P_M$ with a high probability of obtaining better results than using $P_{M_0}$. Computational results are presented in order to show that our procedures are very promising.
Citation
Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela (August,2014).
Article
View Mathematical programming approach to tighten a Big-$ formulation