Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds

The polyhedral structure of the convex hull of regions is investigated defined by a single mixed 0-1 row along with variable upper bound constraints on the continuous variables. A family of facet-defining valid inequalities is introduced for this problem formulation. A dual-based heuristic is presented to solve the separation problem related to these inequalities. Computational results show that a cutting plane algorithm based on this class of valid inequalities and on the separation heuristic provides an efficient tool to improve the formulation of mixed integer programs defined over these regions.