Optimization Online


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

Don Coppersmith (dcopper***at***us.ibm.com)
Oktay Gunluk (oktay***at***watson.ibm.com)
Jon Lee (jonlee***at***us.ibm.com)
Janny Leung (janny***at***se.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

  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 Programming Society