Webinar: Graph-based Approaches to Solving Binary Quadratic Programs

Event Recap

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.

Meet the Experts

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search

Gurobi Optimization