NDLI: Bidimensional packing by bilinear programming

Content Provider	Springer Nature Link
Author	Caprara, Alberto Monaci, Michele
Copyright Year	2007
Abstract	We consider geometric problems in which rectangles have to be packed into (identical) squares. These problems turn out to be very hard in practice, and ILP formulations in which variables specify the coordinates in the packing perform very poorly. While most methods developed so far are based on simple geometric considerations, a recent landmark result of Fekete and Schepers suggests to put these geometric aspects aside and use the most advanced tools for the one-dimensional case. In this paper we make additional progress in this direction, especially on the basic question “Does a given set of rectangles fit into a square?”, which turns out to be the bottleneck of all the approaches known. Given a set of rectangles and the associated convex hull of rectangle subsets that fit into a square, we derive a wide class of valid inequalities for this convex hull from a complete description of the two knapsack polytopes associated with the widths and the heights of the rectangles, respectively. In addition, we illustrate how to solve the associated separation problem as a bilinear program, for which we develop a solution method that turns out to be fast in practice, and show that the integer solutions that satisfy all these constraints generally correspond to vertices of the original convex hull for the benchmark instances in the literature. The same tools are used to derive lower bounds for the two-dimensional bin packing problem, corresponding to the determination of an optimal pair of so-called dual feasible functions. These lower bounds in many cases equal those obtained by the customary set covering formulation (for which column generation is very hard), but are computable within a time that is smaller by some orders of magnitude. This allows us to close a few of the benchmark instances in the literature.
Ending Page	108
Page Count	34
Starting Page	75
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1
Volume Number	118
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-08-30
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Packing and covering in $2$ dimensions Mathematical Methods in Physics Dual feasible functions Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Mathematical and Computational Physics Numerical Analysis Bidimensional packing Computational experiments Bilinear programming Combinatorics
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Strong valid inequalities for orthogonal disjunctions and bilinear covering sets

Covering symmetric supermodular functions by graphs

A weighted even factor algorithm

Lifted inequalities for $$0\mathord {-}1$$ mixed-integer bilinear covering sets

A semidefinite programming hierarchy for packing problems in discrete geometry

Decomposition methods in stochastic programming

Dynamic bundle methods

MIP reformulations of the probabilistic set covering problem

Variation of cost functions in integer programming

Bidimensional packing by bilinear programming

Similar Documents

Strong valid inequalities for orthogonal disjunctions and bilinear covering sets

Covering symmetric supermodular functions by graphs

A weighted even factor algorithm

Lifted inequalities for $$0\mathord {-}1$$ mixed-integer bilinear covering sets

A semidefinite programming hierarchy for packing problems in discrete geometry

Decomposition methods in stochastic programming

Dynamic bundle methods

MIP reformulations of the probabilistic set covering problem

Variation of cost functions in integer programming

Bidimensional packing by bilinear programming