Compact linearization for binary quadratic problems

DOI10.1007/S10288-006-0015-3zbMath1211.90154OpenAlexW2060841252MaRDI QIDQ2477615

Leo Liberti

Publication date: 14 March 2008

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-006-0015-3

zbMATH Keywords

linearizationgraph partitioningbinary quadratic problem

Mathematics Subject Classification ID

Mixed integer programming (90C11) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items (15)

Dantzig-Wolfe reformulations for binary quadratic problems ⋮ Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays ⋮ Mathematical Programming Models and Exact Algorithms ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ Fast, flexible, and exact minimum flow decompositions via ILP ⋮ On a linearization technique for solving the quadratic set covering problem and variations ⋮ Inductive linearization for binary quadratic programs with linear constraints ⋮ Shortest paths with exclusive-disjunction arc pairs conflicts ⋮ Compact linearization for binary quadratic problems subject to assignment constraints ⋮ Inductive linearization for binary quadratic programs with linear constraints: a computational study ⋮ Optimal configuration of gamma ray machine radiosurgery units: The sphere covering subproblem ⋮ Evaluating the quality of image matrices in blockmodeling ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations ⋮ Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem

Uses Software

• AMPL
• CPLEX
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Compact mathematical formulation for graph partitioning
• On the quadratic assignment problem
• Location, scheduling, design and integer programming
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Tighter representations for set partitioning problems
• Assignment Problems and the Location of Economic Activities
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Exact Solution of the Quadratic Knapsack Problem
• Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
• A polynomial case of unconstrained zero-one quadratic optimization

This page was built for publication: Compact linearization for binary quadratic problems