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

  • Don Coppersmith
  • Oktay Gunluk
  • Jon Lee
  • Janny Leung
    • Categories 0-1 Programming Tags , Short URL: https://optimization-online.org/?p=9473

    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.

    Citation

    Earlier version, IBM Research Report RC21568

    Article

    Download

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