Dantzig-Wolfe reformulations for binary quadratic problems

DOI10.1007/s12532-021-00206-wzbMath1484.90048OpenAlexW4205253277MaRDI QIDQ2125570

Emiliano Traversi, Alberto Ceselli, Lucas Létocart

Publication date: 14 April 2022

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-021-00206-w

zbMATH Keywords

column generationdecomposition methodsbinary quadratic programmingquadratic convex reformulation

Mathematics Subject Classification ID

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

Uses Software

• CPLEX
• Gurobi
• Knapsack
• GloMIQO
• Biq Mac
• GCG
• BiqCrunch

Cites Work

• Unnamed Item
• GLOMIQO: global mixed-integer quadratic optimizer
• Semidefinite relaxations for non-convex quadratic mixed-integer programming
• Extending the QCR method to general mixed-integer programs
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• ``Miniaturized linearizations for quadratic 0/1 problems
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• The quadratic knapsack problem -- a survey
• Quadratic convex reformulations for quadratic 0-1 programming
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• An algorithm for the solution of the 0-1 knapsack problem
• Combining QCR and CHR for convex quadratic pure 0--1 programming problems with linear constraints
• Simplicial with truncated Dantzig-Wolfe decomposition for nonlinear multicommodity network flow problems with side constraints
• Random sampling and machine learning to understand good decompositions
• Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
• Compact linearization for binary quadratic problems
• A generic view of Dantzig--Wolfe decomposition in mixed integer programming
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• Partial Lagrangian relaxation for general quadratic programming
• Exact Solution Methods for the k-Item Quadratic Knapsack Problem
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• BiqCrunch
• Decomposition Principle for Linear Programs
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• L’algebre de Boole et ses applications en recherche operationnelle
• A duality theorem for non-linear programming
• An Algorithm for Large Zero-One Knapsack Problems
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Exact Solution of the Quadratic Knapsack Problem
• FiberSCIP—A Shared Memory Parallelization of SCIP
• Column Generation
• A geometric study of dual gaps, with applications

This page was built for publication: Dantzig-Wolfe reformulations for binary quadratic problems