Approximate Packing: Integer Programming Models, Valid Inequalities and Nesting

Igor Litvinchev (), Luis Infante () and Lucero Ozuna ()
Additional contact information
Igor Litvinchev: Russian Academy of Sciences
Luis Infante: Nuevo Leon Sate University
Lucero Ozuna: Nuevo Leon Sate University

Chapter Chapter 9 in Optimized Packings with Applications, 2015, pp 187-205 from Springer

Abstract: Abstract Using a regular grid to approximate a container, packing objects is reduced to assigning objects to the nodes of the grid subject to non-overlapping constraints. The packing problem is then stated as a large scale linear 0-1 optimization problem. Different formulations for non-overlapping constraints are presented and compared. Valid inequalities are proposed to strengthening formulations. This approach is applied for packing circular and L-shaped objects. Circular object is considered in a general sense as a set of points that are all the same distance (not necessary Euclidean) from a given point. Different shapes, such as ellipses, rhombuses, rectangles, octagons, etc., are treated similarly by simply changing the definition of the norm used to define the distance. Nesting objects inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach.

Keywords: Packing problems; Integer programming; Large-scale optimization (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (3)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-18899-7_9

Ordering information: This item can be ordered from
http://www.springer.com/9783319188997

DOI: 10.1007/978-3-319-18899-7_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().