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

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, 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, 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