Automatic Dantzig-Wolfe reformulation of mixed integer programs
From MaRDI portal
Publication:2515047
DOI10.1007/s10107-014-0761-5zbMath1307.90114OpenAlexW2081444749WikidataQ57659046 ScholiaQ57659046MaRDI QIDQ2515047
Enrico Malaguti, Fabio Furini, Emiliano Traversi, Marco E. Lübbecke, Martin Bergner, Alberto Caprara, Alberto Ceselli
Publication date: 9 February 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-014-0761-5
column generationDantzig-Wolfe decompositionhypergraph partitioningblock-diagonal matrixautomatic reformulationmatrix re-ordering
Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Decomposition methods (49M27)
Related Items
Dantzig-Wolfe reformulations for binary quadratic problems, Consistency Cuts for Dantzig-Wolfe Reformulations, Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems, An exact algorithm for the partition coloring problem, A branch-and-price algorithm for capacitated hypergraph vertex separation, Decomposition Branching for Mixed Integer Programming, A decomposition heuristic for mixed-integer supply chain problems, Distributed asynchronous column generation, High-multiplicity \(N\)-fold IP via configuration LP, Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs, Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem, Integer programming column generation: accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems, A data driven Dantzig-Wolfe decomposition framework, Split cuts from sparse disjunctions, Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Structure Detection in Mixed-Integer Programs, Learning when to use a decomposition, Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework, Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation, Random sampling and machine learning to understand good decompositions, Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition, A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times, Parallel subgradient algorithm with block dual decomposition for large-scale optimization, A graph-based modeling abstraction for optimization: concepts and implementation in Plasmo.jl, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations
Uses Software
Cites Work
- Unnamed Item
- Stabilized column generation
- Partitioning mathematical programs for parallel solution
- A structure-conveying modelling language for mathematical and stochastic programming
- Dantzig-Wolfe decomposition and branch-and-price solving in G12
- MIPLIB 2003
- Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation
- A Structure-Exploiting Tool in Algebraic Modeling Languages
- Reformulation and Decomposition of Integer Programs
- Robust Locally Weighted Regression and Smoothing Scatterplots
- Decomposing Matrices into Blocks
- Permuting Sparse Rectangular Matrices into Block-Diagonal Form
- Computational Experience with Hypergraph-Based Methods for Automatic Decomposition in Discrete Optimization
- Column Generation
- A Primer in Column Generation
- Rearranging Matrices to Block-Angular form for Decomposition (And Other) Algorithms
- Benchmarking optimization software with performance profiles.
- A tightly integrated modelling and optimisation library: A new framework for rapid algorithm development
