An Implicit Enumeration Algorithm for Quadratic Integer Programming

R. D. McBride
R. D. McBride
University of Southern California
Search for more papers by this author
,
J. S. Yormark
J. S. Yormark
University of Southern California
Search for more papers by this author

R. D. McBride

University of Southern California

Search for more papers by this author

J. S. Yormark

University of Southern California

Search for more papers by this author

Published Online:1 Mar 1980https://doi.org/10.1287/mnsc.26.3.282

Abstract

We present an implicit enumeration algorithm for a nonseparable quadratic integer programming problem. We utilize fathoming criteria derived from Lemke's complementary pivot algorithm, and compare the use of pseudo-costs versus generalized penalties as a guide to branching. Computational experience is provided.

Cited by
- New techniques to improve neighborhood exploration in pareto local search
  Expert Systems with Applications, Vol. 254
- On the Effects of Smoothing Rugged Landscape by Different Toy Problems: A Case Study on UBQP
- Improving Pareto Local Search Using Cooperative Parallelism Strategies for Multiobjective Combinatorial Optimization
  IEEE Transactions on Cybernetics, Vol. 54, No. 4
- Positive semidefinite penalty method for quadratically constrained quadratic programming
  17 August 2020 | IMA Journal of Numerical Analysis, Vol. 41, No. 4
- Structured linear reformulation of binary quadratically constrained quadratic programs
  17 November 2018 | Optimization Letters, Vol. 14, No. 3
- PPLS/D: Parallel Pareto Local Search Based on Decomposition
  IEEE Transactions on Cybernetics, Vol. 50, No. 3
- PCI Planning Based on Binary Quadratic Programming in LTE/LTE-A Networks
  IEEE Access, Vol. 7
- A Neural Network Based Global Optimal Algorithm for Unconstrained Binary Quadratic Programming Problem
  18 November 2018
- A Parallel Tabu Search for the Unconstrained Binary Quadratic Programming problem
- Quadratic Unconstrained Binary Optimization (QUBO) on neuromorphic computing system
- Solving bi-objective unconstrained binary quadratic programming problem with multi-objective path relinking algorithm
- Polynomial time solvable algorithms to a class of unconstrained and linearly constrained binary quadratic programming problems
  Neurocomputing, Vol. 198
- An Effective Genetic Algorithm with Uniform Crossover for Bi-objective Unconstrained Binary Quadratic Programming Problem
  13 September 2016
- A Multi-parent Crossover Based Genetic Algorithm for Bi-Objective Unconstrained Binary Quadratic Programming Problem
  8 January 2017
- Parametric Lagrangian dual for the binary quadratic programming problem
  27 February 2014 | Journal of Global Optimization, Vol. 61, No. 2
- Ellipsoid Bounds for Convex Quadratic Integer Programming
  SIAM Journal on Optimization, Vol. 25, No. 2
- Polynomial time solvable algorithm to linearly constrained binary quadratic programming problems with Q being a five-diagonal matrix
- General Bibliography
  8 August 2014
- Integer Quadratic Knapsack Problems
  8 August 2014
- Optimization Methods for Mixed Integer Weakly Concave Programming Problems
  27 June 2014 | Journal of the Operations Research Society of China, Vol. 2, No. 2
- A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming
  Applied Soft Computing, Vol. 16
- A Polynomial Time Solvable Algorithm to Binary Quadratic Programming Problems with Q Being a Seven-Diagonal Matrix and Its Neural Network Implementation
  19 November 2014
- Probabilistic GRASP-Tabu Search algorithms for the UBQP problem
  Computers & Operations Research, Vol. 40, No. 12
- Backbone guided tabu search for solving the UBQP problem
  10 March 2011 | Journal of Heuristics, Vol. 19, No. 4
- Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems
  8 June 2011 | Journal of Heuristics, Vol. 19, No. 4
- Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization
  1 June 2011 | Journal of Heuristics, Vol. 19, No. 4
- Integer Quadratic Knapsack Problems
  13 February 2013
- Path relinking for unconstrained binary quadratic programming
  European Journal of Operational Research, Vol. 223, No. 3
- An iterated greedy algorithm for the binary quadratic programming problem
- Two-stage quadratic integer programs with stochastic right-hand sides
  1 October 2010 | Mathematical Programming, Vol. 133, No. 1-2
- An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach
  9 April 2011 | Journal of Global Optimization, Vol. 52, No. 4
- A Multilevel Algorithm for Large Unconstrained Binary Quadratic Optimization
- Lagrangean decompositions for the unconstrained binary quadratic programming problem
  2 February 2011 | International Transactions in Operational Research, Vol. 18, No. 2
- A hybrid metaheuristic approach to solving the UBQP problem
  European Journal of Operational Research, Vol. 207, No. 3
- Diversification-driven tabu search for unconstrained binary quadratic problems
  5 January 2010 | 4OR, Vol. 8, No. 3
- Polynomial time solvable algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix
- Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming
  Optimization, Vol. 59, No. 5
- Polynomially Solvable Cases of Binary Quadratic Programs
  5 May 2010
- A Study of Memetic Search with Multi-parent Combination for UBQP
- Geração de colunas com divisão em clusters para o problema de programação quadrática binária irrestrita
  Gestão & Produção, Vol. 16, No. 4
- Decomposições Lagrangeanas para o problema de programação quadrática binária irrestrita
  Pesquisa Operacional, Vol. 29, No. 1
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
  Discrete Applied Mathematics, Vol. 157, No. 6
- An Efficient Maximization Algorithm With Implications in Min-Max Predictive Control
  IEEE Transactions on Automatic Control, Vol. 53, No. 9
- The spherical constraint in Boolean quadratic programs
  6 June 2007 | Journal of Global Optimization, Vol. 39, No. 4
- Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)
  21 February 2007 | Journal of Heuristics, Vol. 13, No. 2
- Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem
  2 June 2006 | Mathematical Programming, Vol. 109, No. 1
- Lower Bound Improvement and Forcing Rule for Quadratic Binary Programming
  18 October 2005 | Computational Optimization and Applications, Vol. 33, No. 2-3
- An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem
  Annals of Operations Research, Vol. 139, No. 1
- Memetic algorithms for the unconstrained binary quadratic programming problem
  Biosystems, Vol. 78, No. 1-3
- Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem
  Annals of Operations Research, Vol. 131, No. 1-4
- Solving Combinatorial Optimization Problems Via Reformulation and Adaptive Memory Metaheuristics
- One-pass heuristics for large-scale unconstrained binary quadratic problems
  European Journal of Operational Research, Vol. 137, No. 2
- Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming
  Journal of Heuristics, Vol. 8, No. 2
- Exact Algorithms for Global Optimization of Mixed-Integer Nonlinear Programs
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
  European Journal of Operational Research, Vol. 134, No. 1
- Solving large scale assignment problems in high-level synthesis by approximative quadratic programming
  1 March 2001
- An evolutionary heuristic for quadratic 0–1 programming
  European Journal of Operational Research, Vol. 119, No. 3
- Simulated annealing for the unconstrained quadratic pseudo-Boolean function
  European Journal of Operational Research, Vol. 108, No. 3
- Adaptive Memory Tabu Search for Binary Quadratic Programs
  Fred Glover,
  Gary A. Kochenberger,
  Bahram Alidaee,
  1 March 1998 | Management Science, Vol. 44, No. 3
- Ranking in quadratic integer programming problems
  European Journal of Operational Research, Vol. 95, No. 1
- Chemical plant layout via graph partitioning—II. Multiple levels
  Computers & Chemical Engineering, Vol. 20, No. 5
- A parallel computation network for the maximum clique problem
- A parallel computation network for the maximum clique problem
- Optimal design of a distributed network with a two-level hierarchical structure
  European Journal of Operational Research, Vol. 62, No. 1
- Reformulating nonlinear combinatorial optimization problems for higher computational efficiency
  European Journal of Operational Research, Vol. 58, No. 2
- An algorithm for indefinite integer quadratic programming
  Computers & Mathematics with Applications, Vol. 21, No. 6-7
- Graph separation techniques for quadratic zero-one programming
  Computers & Mathematics with Applications, Vol. 21, No. 6-7
- A parallel neural network computing for the maximum clique problem
- An algorithm for quadratic zero-one programs
  Naval Research Logistics, Vol. 37, No. 4
- Computational aspects of a branch and bound algorithm for quadratic zero-one programming
  Computing, Vol. 45, No. 2
- On duality for Boolean programming
  European Journal of Operational Research, Vol. 46, No. 3
- Approximating finite weighted point sets by hyperplanes
  8 June 2005
- CON due-date determination and sequencing
  Computers & Operations Research, Vol. 17, No. 4
- The hierarchical‐hub model for airline networks
  Transportation Planning and Technology, Vol. 14, No. 4
- Models and methods of solution of quadratic integer programming problems
  Cybernetics, Vol. 23, No. 3
- A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm 1
  Optimization, Vol. 19, No. 5
- A quadratic integer program for the location of interacting hub facilities
  European Journal of Operational Research, Vol. 32, No. 3
- Evaluating Interrelated Capital Projects: An Alternative Framework
  The Engineering Economist, Vol. 33, No. 1
- An exact penalty function approach for nonlinear integer programming problems
  European Journal of Operational Research, Vol. 27, No. 1
- Abandonment value in capital budgeting: A mathematical programming approach
  Computers & Operations Research, Vol. 13, No. 6
- Integer quadratic optimization
  European Journal of Operational Research, Vol. 19, No. 2
- Ein effektiver Branch and Bound‐Algorithmus für Boolesche quadratische Optimierungsprobleme
  22 November 2006 | ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 65, No. 8
- The indefinite zero-one quadratic problem
  Discrete Applied Mathematics, Vol. 7, No. 1
- Comparaison de deux méthodes de résolution d'un problème combinatoire quadratique
  29 March 2011 | RAIRO - Operations Research, Vol. 17, No. 3
- Nonlinear integer programming for various forms of constraints
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 29, No. 4
- Mixed-integer quadratic programming
  Mathematical Programming, Vol. 22, No. 1
- Zur effektiven Lösung von booleschen, quadratischen Optimierungsproblemen
  Numerische Mathematik, Vol. 40, No. 1
- Resolution of a quadratic combinatorial problem by dynamic programming
- Mean-variance analysis for indivisible assets
  Omega, Vol. 9, No. 1

Volume 26, Issue 3

March 1980

Pages 229-344

Article Information

Metrics

Information

Published Online:March 01, 1980

Cite as

R. D. McBride, J. S. Yormark, (1980) An Implicit Enumeration Algorithm for Quadratic Integer Programming. Management Science 26(3):282-296.

https://doi.org/10.1287/mnsc.26.3.282

Keywords

quadratic integer programming

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

An Implicit Enumeration Algorithm for Quadratic Integer Programming

Abstract

Volume 26, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News