A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
From MaRDI portal
Publication:3762072
DOI10.1287/MNSC.32.10.1274zbMATH Open0623.90054OpenAlexW2128971018WikidataQ60395649 ScholiaQ60395649MaRDI QIDQ3762072FDOQ3762072
Hanif D. Sherali, Warren P. Adams
Publication date: 1986
Published in: Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/mnsc.32.10.1274
implicit enumerationLagrangian relaxationlinearization techniqueszero-one quadratic programmingBenders' cutting planesmixed-integer linear programming problem
Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Applications of mathematical programming (90C90) Integer programming (90C10) Mixed integer programming (90C11) Boolean programming (90C09)
Cited In (only showing first 100 items - show all)
- RLT insights into lift-and-project closures
- Theoretical and computational study of several linearisation techniques for binary quadratic problems
- Restricted risk measures and robust optimization
- A Decomposition Method for Quadratic Zero-One Programming
- Approximated perspective relaxations: a project and lift approach
- RLT: A unified approach for discrete and continuous nonconvex optimization
- An improved linearization strategy for zero-one quadratic programming problems
- Linear Reformulations of Integer Quadratic Programs
- Partial Lagrangian relaxation for general quadratic programming
- An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
- Constrained 0-1 quadratic programming: basic approaches and extensions
- Pseudo-Boolean optimization
- Selected topics on assignment problems
- Integer programming approaches to the multiple team formation problem
- Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
- Queueing maximal covering location-allocation problem: an extension with \textit{M/G/1} queueing systems
- Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
- Best reduction of the quadratic semi-assignment problem
- An algorithm for indefinite integer quadratic programming
- Fractional 0-1 programming: applications and algorithms
- Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
- Two-stage quadratic integer programs with stochastic right-hand sides
- Linear programming insights into solvable cases of the quadratic assignment problem
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
- A survey for the quadratic assignment problem
- Reformulations in Mathematical Programming: Definitions and Systematics
- A continuous approch for globally solving linearly constrained quadratic
- The multi-story space assignment problem
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
- A level-2 reformulation-linearization technique bound for the quadratic assignment problem
- Extending the QCR method to general mixed-integer programs
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- Reformulating nonlinear combinatorial optimization problems for higher computational efficiency
- An algorithm for the generalized quadratic assignment problem
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
- Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
- An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms
- Mixed integer linear programming formulation techniques
- Lower bounding procedure for the asymmetric quadratic traveling salesman problem
- An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs
- Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
- An improved linearization technique for a class of quadratic 0-1 programming problems
- Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
- Biconvex Models and Algorithms for Risk Management Problems
- Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations
- A solvable class of quadratic 0-1 programming
- An enumerative algorithm framework for a class of nonlinear integer programming problems
- A Branch-and-Bound Algorithm for Team Formation on Social Networks
- Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
- New formulations of the multiple sequence alignment problem
- A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems
- Location coverage models with demand originating from nodes and paths: Application to cellular network design
- Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
- A study of the quadratic semi-assignment polytope
- A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem
- Univariate parameterization for global optimization of mixed-integer polynomial problems
- Mathematical Programming Models and Exact Algorithms
- A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
- The quadratic knapsack problem -- a survey
- Designing cost-effective content distribution networks
- Exact solution of emerging quadratic assignment problems
- A mathematical program to refine gene regulatory networks
- Linear programming for the \(0-1\) quadratic knapsack problem
- The quadratic three-dimensional assignment problem: exact and approximate solution methods
- Global optimization of a quadratic function subject to a bounded mixed integer constraint set
- Lagrangian solution of maximum dispersion problems
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
- Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches
- Bivalent quadratic programming problem - A computational study
- A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem
- A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
- Tighter representations for set partitioning problems
- A new relaxation framework for quadratic assignment problems based on matrix splitting
- A revised reformulation-linearization technique for the quadratic assignment problem
- A roof linearization algorithm to obtain a tight upper bound for integer nonseparable quadratic programming
- A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
- Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
- Valid inequalities for quadratic optimisation with domain constraints
- The linearization problem of a binary quadratic problem and its applications
- Enabling research through the SCIP Optimization Suite 8.0
- Structured linear reformulation of binary quadratically constrained quadratic programs
- Dantzig-Wolfe reformulations for binary quadratic problems
- Wave order picking under the mixed-shelves storage strategy: a solution method and advantages
- An LP-based characterization of solvable QAP instances with chess-board and graded structures
- An efficient compact quadratic convex reformulation for general integer quadratic programs
- SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY
- The generalized vertex cover problem and some variations
- Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem
- An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations
- Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Strong SDP based bounds on the cutwidth of a graph
- An integer linear programming approach for a class of bilinear integer programs
- Short paper -- The binary linearization complexity of pseudo-Boolean functions
- Optimal Genetic Screening for Cystic Fibrosis
- Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- Efficient separation of RLT cuts for implicit and explicit bilinear products
- On a linearization technique for solving the quadratic set covering problem and variations
Recommendations
- An improved linearization strategy for zero-one quadratic programming problems 👍 👎
- Bivalent quadratic programming problem - A computational study 👍 👎
- QUAD01: A data-structured implementation of Hansen's quadratic zero-one programming algorithm 👍 👎
- Constrained 0-1 quadratic programming: basic approaches and extensions 👍 👎
- A continuous approch for globally solving linearly constrained quadratic 👍 👎
This page was built for publication: A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3762072)
