Optimization Online


Mathematical programming approach to tighten a Big-$M$ formulation

Alejandro Crema (alejandro.crema***at***ciens.ucv.ve)

Abstract: 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.

Keywords: Integer Programming, Big-$M$ formulation

Category 1: Integer Programming

Citation: Escuela de ComputaciĆ³n, Facultad de Ciencias, Universidad Central de Venezuela (August,2014).

Download: [PDF]

Entry Submitted: 08/07/2014
Entry Accepted: 08/07/2014
Entry Last Modified: 08/11/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society