Premium
An algorithm for quadratic zero‐one programs
Author(s) -
Kalantari Bahman,
Bagchi Ansuman
Publication year - 1990
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199008)37:4<527::aid-nav3220370407>3.0.co;2-p
Subject(s) - mathematics , hessian matrix , dimension (graph theory) , quadratic equation , measure (data warehouse) , upper and lower bounds , algorithm , function (biology) , zero (linguistics) , minification , mathematical optimization , combinatorics , computer science , mathematical analysis , philosophy , geometry , linguistics , database , evolutionary biology , biology
We present an algorithm for the quadratic zero‐one minimization by reformulation of the problem into an equivalent concave quadratic minimization. We then specialize an algorithm proposed by Kalantari and Rosen [13], which globally minimizes a concave quadratic function over arbitrary polytopes. The algorithm exploits the special structure of the problem. Given a set of conjugate directions to the Hessian, we construct a linear convex envelope over a “tight” containing parallelopiped, by solving 2 n linear programs each solvable in O(n) time, n being the dimension of the problem. A bound on the maximum difference in the value of the quadratic function and the convex envelope may be obtained, which provides a global measure of underestimation. A branch‐and‐bound method is presented in which subproblems are defined by fixing a variable at zero or one. For each subproblem, we obtain a lower bound by minimizing the linear convex envelope over the feasible region of the subproblem. Computational experience with the algorithm is also presented.