Quadratic Optimization in 0–1 Variables
Alain Billionnet · 2014
This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.