Integer programming formulations for approximate packing circles in a rectangular container

DOI10.1155/2014/317697MaRDI QIDQ1718120zbMATH OpenOpenAlexWikidataFDO

Authors Edith Lucero Ozuna Espinosa, I. Litvinchev

Publication date 8 February 2019

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.1155/2014/317697

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

Summary: A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace, and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with local search procedures. New formulations are proposed for approximate solution of packing problem. The container is approximated by a regular grid and the nodes of the grid are considered as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. Nesting circles inside one another is also considered. The resulting binary problem is then solved by commercial software. Numerical results are presented to demonstrate the efficiency of the proposed approach and compared with known results.

Recommendations

• Packing circular-like objects in a rectangular container
• Approximate packing: integer programming models, valid inequalities and nesting
• Packing different-sized circles into a rectangular container
• A heuristic for the circle packing problem with a variety of containers
• A formulation space search heuristic for packing unequal circles in a fixed size circular container

Cites work

• A heuristic for the circle packing problem with a variety of containers
• A Lagrangian bound for many-to-many assignment problems
• A literature review on circle and sphere packing problems: models and methodologies
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Annealing, Cylinder Packing By Simulated
• Integrated container loading software for pulp and paper industry
• Linear models for the approximate solution of the problem of packing equal circles into a given domain
• Multiple Container Packing: A Case Study of Pipe Packing
• New and improved results for packing identical unitary radius circles within triangles, rectangles and strips
• Optimizing the packing of cylinders into a rectangular container: A nonlinear approach
• Packing congruent spheres into a multi‐connected polyhedral domain
• Packing unequal circles using formulation space search
• Solving circle packing problems by global optimization: numerical results and industrial applications
• Solving the circular open dimension problem by using separate beams and look-ahead strategies
• The distributor's three-dimensional pallet-packing problem: a human intelligence-based heuristic approach

Cited in

(12)

• Packing different-sized circles into a rectangular container
• Packing unequal rectangles and squares in a fixed size circular container using formulation space search
• Optimizing the packing of cylinders into a rectangular container: A nonlinear approach
• A support tool for planning classrooms considering social distancing between students
• On calculating the packing efficiency for embedding hexagonal and dodecagonal sensors in a circular container
• A cutting plane method and a parallel algorithm for packing rectangles in a circular container
• scientific article; zbMATH DE number 6698326 (Why is no real title available?)
• Approximate packing: integer programming models, valid inequalities and nesting
• Packing circular-like objects in a rectangular container
• Mixed-integer DC programming based algorithms for the circular packing problem
• A filtered beam search based heuristic algorithm for packing unit circles into a circular container
• Packing spheres with quasi-containment conditions

This page was built for publication: Integer programming formulations for approximate packing circles in a rectangular container

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1718120)