### 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 language | English (US) |
---|---|

Pages (from-to) | 527-538 |

Number of pages | 12 |

Journal | Naval Research Logistics (NRL) |

Volume | 37 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 1990 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Cite this

*Naval Research Logistics (NRL)*,

*37*(4), 527-538. https://doi.org/10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO;2-P

}

*Naval Research Logistics (NRL)*, vol. 37, no. 4, pp. 527-538. https://doi.org/10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO;2-P

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

Research output: Contribution to journal › Article

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

AN - SCOPUS:84989694511

VL - 37

SP - 527

EP - 538

JO - Naval Research Logistics

JF - Naval Research Logistics

SN - 0894-069X

IS - 4

ER -