An algorithm for quadratic zero‐one programs

Bahman Kalantari, Ansuman Bagchi

Research output: Contribution to journalArticle

13 Citations (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)527-538
Number of pages12
JournalNaval Research Logistics (NRL)
Volume37
Issue number4
DOIs
StatePublished - Jan 1 1990

Fingerprint

Quadratic Program
Convex Envelope
Quadratic Function
Conjugate Directions
Feasible region
Concave function
Polytopes
Reformulation
Linear Program
Lower bound
Minimise
Zero
Arbitrary

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this

Kalantari, Bahman ; Bagchi, Ansuman. / An algorithm for quadratic zero‐one programs. In: Naval Research Logistics (NRL). 1990 ; Vol. 37, No. 4. pp. 527-538.
@article{cd9c82be024745b9b86467dbdd6ce723,
title = "An algorithm for quadratic zero‐one programs",
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.",
author = "Bahman Kalantari and Ansuman Bagchi",
year = "1990",
month = "1",
day = "1",
doi = "10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO;2-P",
language = "English (US)",
volume = "37",
pages = "527--538",
journal = "Naval Research Logistics",
issn = "0894-069X",
publisher = "John Wiley and Sons Inc.",
number = "4",

}

An algorithm for quadratic zero‐one programs. / Kalantari, Bahman; Bagchi, Ansuman.

In: Naval Research Logistics (NRL), Vol. 37, No. 4, 01.01.1990, p. 527-538.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An algorithm for quadratic zero‐one programs

AU - Kalantari, Bahman

AU - Bagchi, Ansuman

PY - 1990/1/1

Y1 - 1990/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84989694511&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84989694511&partnerID=8YFLogxK

U2 - 10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO;2-P

DO - 10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO;2-P

M3 - Article

VL - 37

SP - 527

EP - 538

JO - Naval Research Logistics

JF - Naval Research Logistics

SN - 0894-069X

IS - 4

ER -