An algorithm for quadratic zero‐one programs

Bahman Kalantari and Ansuman Bagchi

Naval Research Logistics (NRL), 1990, vol. 37, issue 4, 527-538

Abstract: 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 2n 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.

Date: 1990
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199008)37:43.0.CO;2-P

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:37:y:1990:i:4:p:527-538

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().