Inductive linearization for binary quadratic programs with linear constraints

A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called inductive linearization, extends concepts for BQPs with particular equation constraints, that have been referred to as compact linearization before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers.

Automated summary

The paper presents a linearization technique called inductive linearization for binary quadratic programs with linear constraints. This technique extends concepts from BQPs with particular equation constraints to the general case and can automatically obtain inductive linearization. The linear programming relaxations obtained using this technique are proven to be at least as strong as classical linearization for various applications.