A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems

1986/10/01 by Warren P. Adams, Hanif D. Sherali · 254 citations
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Computer science #Control (management) #Facility Location and Emergency Management #Feedback linearization #Lagrangian relaxation #Linear programming #Linearization #Mathematical optimization #Mathematics #Nonlinear system #Optimization and Search Problems #Quadratic equation #Quadratic programming #Relaxation (psychology) #Set (abstract data type) #Vehicle Routing Optimization Methods #Zero (linguistics)

paper · doi:10.1287/mnsc.32.10.1274

published in Management Science 32(10), 1274-1290 (Institute for Operations Research and the Management Sciences)

openalex publication_date 1986/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper is concerned with the solution of linearly constrained zero-one quadratic programming problems. Problems of this kind arise in numerous economic, location decision, and strategic planning situations, including capital budgeting, facility location, quadratic assignment, media selection, and dynamic set covering. A new linearization technique is presented for this problem which is demonstrated to yield a tighter continuous or linear programming relaxation than is available through other methods. An implicit enumeration algorithm which uses Lagrangian relaxation, Benders' cutting planes, and local explorations is designed to exploit the strength of this linearization. Computational experience is provided to demonstrate the usefulness of the proposed linearization and algorithm.

Citations

• Generalized Benders decomposition

Cited by

• Mixed Integer Linear Programming Formulation Techniques
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Improving Lower Bounds for the Quadratic Assignment Problem by applying a Distributed Dual Ascent Algorithm
• Protein Threading Based on Nonlinear Integer Programming
• Efficient separation of RLT cuts for implicit and explicit bilinear terms
• Cross-Dock Door Design under Uncertainty: A two-stage DRO-based lower- and upper-bounding scheme
• An Exact Algorithm for Large-scale Non-convex Quadratic Facility Location
• Submodular maximization and its generalization through an intersection cut lens

Related

• A Tight Linearization Strategy for Zero-One Quadratic Programming Problems
• A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
• A Novel Algorithm for Linear Programming
• Algorithms for Convex Quadratic Programming
• Linear Programming Relaxations of Quadratically Constrained Quadratic Programs