Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition

DOI10.1007/s10479-018-3115-5OpenAlexW3104239225WikidataQ128756246 ScholiaQ128756246MaRDI QIDQ2288982

Benjamin Müller, Stephen J. Maher, Ambros M. Gleixner, João Pedro Pedroso

Publication date: 20 January 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.07799

zbMATH Keywords

global optimizationDantzig-Wolfe decompositionsymmetry breakingmixed-integer nonlinear programmingrecursive circle packing

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Numerical methods in optimal control (49Mxx) Numerical methods for mathematical programming, optimization and variational techniques (65Kxx)

Uses Software

• BARON
• SCIP
• MUMPS
• CPLEX
• COIN-OR
• Ipopt
• CppAD
• DIP
• GCG
• kepler98

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• kepler98
• Packing ellipsoids into volume-minimizing rectangular boxes
• A literature review on circle and sphere packing problems: models and methodologies
• Solving circle packing problems by global optimization: numerical results and industrial applications
• Cutting circles and polygons from area-minimizing rectangles
• Solving binary cutting stock problems by column generation and branch- and-bound
• An exact algorithm for IP column generation
• Branch-and-price algorithms for the one-dimensional cutting stock problem
• On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square
• BARON: A general purpose global optimization software package
• Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• The two-dimensional bin packing problem with variable bin sizes and costs
• Recursive circle packing problems
• Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints
• Decomposition Principle for Linear Programs
• A Linear Programming Approach to the Cutting-Stock Problem
• Reformulation and Decomposition of Integer Programs
• A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
• Selected Topics in Column Generation
• Multistage Cutting Stock Problems of Two and More Dimensions