Optimization Online


Chvatal rank in binary polynomial optimization

Alberto Del Pia (delpia***at***wisc.edu)
Silvia Di Gregorio (sdigregorio***at***wisc.edu)

Abstract: Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, in order to derive deeper cutting planes, we consider hypergraphs that contain beta-cycles. In particular, we introduce a novel class of valid inequalities arising from odd beta-cycles, that generally have Chvatal rank 2. These cuts subsume odd-cycle inequalities for binary quadratic optimization. We then provide an indication of their theoretical power by showing that they yield the multilinear polytope of cycle hypergraphs. To obtain this result, we introduce a novel proof technique that allows us to iteratively obtain multilinear polytopes of increasingly complex hypergraphs.

Keywords: Binary polynomial optimization; Chvatal-Gomory cuts; Chvatal rank; Integer nonlinear optimization; Polyhedral relaxations; Multilinear polytope

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Global Optimization (Theory )

Citation: Manuscript

Download: [PDF]

Entry Submitted: 11/20/2018
Entry Accepted: 11/20/2018
Entry Last Modified: 02/14/2020

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