Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation

DOI10.1007/978-3-642-20807-2_4zbMath1339.90242OpenAlexW1514691415WikidataQ57659082 ScholiaQ57659082MaRDI QIDQ3009749

Enrico Malaguti, Marco E. Lübbecke, Fabio Furini, Martin Bergner, Alberto Caprara, Emiliano Traversi

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_4

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

An exact algorithm for the partition coloring problem, Primal Heuristics for Branch-and-Price Algorithms, Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation, Automatic Dantzig-Wolfe reformulation of mixed integer programs, Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times, A decomposition method for large scale MILPs, with performance guarantees and a power system application

Uses Software

• MIPLIB
• MIPLIB2003
• DIP
• BaPCod
• GCG

Cites Work

• Computing with multi-row gomory cuts
• Partitioning mathematical programs for parallel solution
• Partial convexification cuts for 0--1 mixed-integer programs
• Dantzig-Wolfe decomposition and branch-and-price solving in G12
• MIPLIB 2003
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation