Exact and approximation algorithms for a soft rectangle packing problem

DOI10.1080/02331934.2012.728217zbMath1306.90101MaRDI QIDQ2926482

Konstanty Junosza-Szaniawski, Zbigniew Lonc, Armin Fügenschuh

Publication date: 24 October 2014

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331934.2012.728217

zbMATH Keywords

partitioning; mixed-integer linear programming; mixed-integer nonlinear programming; rectangle packing; geometric arrangement problems; soft rectangles

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C25: Convex programming

90C11: Mixed integer programming

68W35: Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)

52C15: Packing and covering in (2) dimensions (aspects of discrete geometry)

68W25: Approximation algorithms

Related Items

An approximation algorithm for optimal piecewise linear interpolations of bounded variable products, An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules, On three soft rectangle packing problems with guillotine constraints

Cites Work

• Unnamed Item
• An approximation algorithm for dissecting a rectangle into rectangles with specified areas
• Integer linear programming models for topology optimization in sheet metal design
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• Disjunctive Cuts for Nonconvex MINLP
• On the Solution of Discrete Programming Problems
• On the Significance of Solving Linear Programming Problems with Some Integer Variables
• Branching and bounds tighteningtechniques for non-convex MINLP
• The Decomposition of a Rectangle into Rectangles of Minimal Perimeter
• How good are slicing floorplans?
• PACKING SOFT RECTANGLES
• On Polyhedral Approximations of the Second-Order Cone