Binary quadratic and quadratically constrained programs (BQPs and BQCPs) have some unique characteristics among integer programs that have motivated various specialized strategies to solve them more efficiently.  While they can be reformulated as binary integer programs (BIPs) or unconstrained binary quadratic programs (QUBOS), examination of the original binary quadratic formulation before any such transformations can help improve performance.  Graphs can often facilitate this process.  The product graph from Padberg’s Boolean Quadric Polytope paper in 1989 is probably the most well-known example.  Padberg’s work focused on deriving cuts from the product graph and just the quadratic objective of the BQP.

In this webinar, we will consider incorporating constraints in the BQP or BQCP to derive cuts.  We will then consider some other graph based approaches, and illustrate with some examples on some challenging publicly available problems.

View the presentation slides here.