Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
Warren P. Adams, Hanif D. Sherali
Operations Research · 1990 · Volume 38 · Issue 2
Abstract
This paper is concerned with a new linearization strategy for a class of zero-one mixed integer programming problems that contains quadratic cross-product terms between continuous and binary variables, and between the binary variables themselves. This linearization scheme provides an equivalent mixed integer linear programming problem which yields a tighter continuous relaxation than that obtainable via the alternative linearization techniques available in the literature. Moreover, the proposed technique provides a unifying framework in the sense that all the alternate methods lead to formulations that are accessible through appropriate surrogates of the constraints of the new linearized formulation. Extensions to various other types of mixed integer nonlinear programming problems are also discussed.
Keywords
programming: linear reformulations of nonlinear integer programs, programming, integer, nonlinear: mixed integer programming problems
Enable JavaScript for citation tools and additional paper interactions.