A Polytope for a Product of Real Linear Functions in 0/1 Variables

Don Coppersmith (dcopperus.ibm.com)
Oktay Gunluk (oktaywatson.ibm.com)
Jon Lee (jonleeus.ibm.com)
Janny Leung (jannyse.cuhk.edu.hk)

Abstract: In the context of integer programming, we develop a polyhedral method for linearizing a product of a pair of real linear functions in 0/1 variables. As an example, by writing a pair of integer variables in binary expansion, we have a technique for linearizing their product. We give a complete linear description for the resulting polytope, and we provide an efficient algorithm for the separation problem. Along the way to establishing the complete description, we also give a complete description for an extended-variable formulation, and we point out a generalization.

Keywords: integer programming, polyhedral analysis

Category 1: Integer Programming (0-1 Programming )

Citation: Earlier version, IBM Research Report RC21568

Download: [Postscript][PDF]

Entry Submitted: 12/15/2003
Entry Accepted: 12/15/2003
Entry Last Modified: 12/15/2003

Modify/Update this entry