Rectangle blanket problem: binary integer linear programming formulation and solution algorithms
From MaRDI portal
Abstract: A rectangle blanket is a set of non-overlapping axis-aligned rectangles, used to approximately represent the two dimensional image of a shape approximately. The use of a rectangle blanket is a widely considered strategy for speeding-up the computations in many computer vision applications. Since neither the rectangles nor the image have to be fully covered by the other, the blanket becomes more precise as the non-overlapping area of the image and the blanket decreases. In this work, we focus on the rectangle blanket problem, which involves the determination of an optimum blanket minimizing the non-overlapping area with a given image subject to an upper bound on the total number of rectangles the blanket can include. This problem has similarities with rectangle covering, rectangle partitioning and cutting / packing problems. The image replaces an irregular master object by an approximating set of smaller axis-aligned rectangles. The union of these rectangles, namely, the rectangle blanket, is neither restricted to remain entirely within the master object, nor required to cover the master object completely. We first develop a binary integer linear programming formulation of the problem. Then, we introduce four methods for its solution. The first one is a branch-and-price algorithm that computes an exact optimal solution. The second one is a new constrained simulated annealing heuristic. The last two are heuristics adopting ideas available in the literature for other computer vision related problems. Finally, we realize extensive computational tests and report results on the performances of these algorithms.
Recommendations
Cites work
- scientific article; zbMATH DE number 5291457 (Why is no real title available?)
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 1062478 (Why is no real title available?)
- scientific article; zbMATH DE number 1175962 (Why is no real title available?)
- A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms
- A minimax theorem on intervals
- A population heuristic for constrained two-dimensional non-guillotine cutting
- A typology of cutting and packing problems
- Algorithms for nesting with defects
- An Algorithm for Two-Dimensional Cutting Problems
- An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
- An improved typology of cutting and packing problems
- Approximation schemes for covering and packing problems in image processing and VLSI
- Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
- Bounds for Two-Dimensional Cutting
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing Maximum-Scoring Segments in Almost Linear Time
- Covering Polygons Is Hard
- Covering Regions by Rectangles
- Covering a polygonal region by rectangles
- Covering orthogonal polygons with star polygons: The perfect graph approach
- Cutting stock problems and solution procedures
- ECAI 2006. 17th European conference on artificial intelligence, Riva del Garda, Italy, August 29 -- September 1, 2006. Proceedings.
- Implementing Mixed Integer Column Generation
- Integer Programming
- Mixed-integer programming models for nesting problems
- Optimal packing and covering in the plane are NP-complete
- Perfect Graphs and Orthogonally Convex Covers
- Polyominos and perfect graphs
- Reducibility among combinatorial problems
- Reformulation and decomposition of integer programs
- Robust mixed-integer linear programming models for the irregular strip packing problem
- Simulated annealing with asymptotic convergence for nonlinear constrained optimization
- Solution approaches to irregular nesting problems
- Solving irregular strip packing problems by hybridising simulated annealing and linear program\-ming
- The geometry of nesting problems: a tutorial
- Tools of mathematical modeling of arbitrary object packing problems
- Totally-Balanced and Greedy Matrices
- Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
- \(\Phi\)-functions for complex 2D-objects
Cited in
(3)
This page was built for publication: Rectangle blanket problem: binary integer linear programming formulation and solution algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735167)
