Inductive linearization for binary quadratic programs with linear constraints
- PDF / 427,335 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 268 Views
Inductive linearization for binary quadratic programs with linear constraints Sven Mallach1 Received: 21 May 2020 / Revised: 21 May 2020 © The Author(s) 2020
Abstract 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. Keywords Non-linear programming · Binary quadratic programming · Mixed-integer programming · Linearization Mathematics Subject Classification 68R01 · 90C05 · 90C09 · 90C10 · 90C11 · 90C20 · 90C30
1 Introduction In this paper, we present a linearization technique for binary quadratic programs (BQPs) that comprise linear and possibly also quadratic constraints. A general form of the problems addressed could be written as follows:
Most of this work was done while the author was at the University of Cologne, Germany.
B 1
Sven Mallach [email protected] High Performance Computing and Analytics Lab, University of Bonn, Endenicher Allee 19A, 53115 Bonn, Germany
123
S. Mallach
min x T Q 0 x + c T x s.t. x T Q k x + dkT x ≤ βk
k = 1, . . . , m Q
Ax ≤ b x ∈ {0, 1}n Here, x ∈ {0, 1}n are the binary variables whose index set is denoted with N := {1, . . . , n} in the sequel. The set of products P occurring in the BQP is established by the matrices Q k ∈ Rn×n , k ∈ {0, . . . , m Q }, in the objective function and the m Q ∈ N0 quadratic restrictions as follows: P := {(i, j) ⊆ N × N | ∃ k ∈ {0, . . . , m Q } : Q ki j = 0} Despite using the term “binary quadratic program”, the case where m Q > 0 and Q 0 is all zero, i.e. the problem is rather a quadratically-constrained binary linear program, is explicitly permitted. Moreover, since xi x j = x j xi for i, j ∈ N , i = j, and xi = xi2 for all i ∈ N , we may assume the matrices Q k , k ∈ {0, . . . , m Q }, to be strictly upper triangular, and thus i < j for (i, j) ∈ P. While quadratic constraints may or may not exist, the linear constraints Ax ≤ b are in the center of the linearization technique proposed in this paper, and their presence is hence necessary to apply it. More precisely, we will require that each variable xi , i ∈ N , that is a factor of a product in P (to be linearized with the technique proposed), arises in at least one linear constraint (with a non-zero coefficient). In a binary program, this can be assumed (or established) without of loss of generality (see also the appendix). Moreover, if this requirement is neither fulfilled in the orig
Data Loading...
