Exploiting packing components in general-purpose integer programming solvers

DOI10.1007/978-3-319-18899-7_10MaRDI QIDQ4634979zbMATH OpenOpenAlexFDO

Authors Jakub Mareček

Publication date 13 April 2018

Published in Optimized Packings with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.2526

zbMATH Keywords

integer programmingpackingstructure exploitationmulti-dimensional packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Integer programming (90C10) Mixed integer programming (90C11)

Abstract: The problem of packing boxes into a large box is often a part of a larger problem. For example in furniture supply chain applications, one needs to decide what trucks to use to transport furniture between production sites and distribution centers and stores, such that the furniture fits inside. Such problems are often formulated and sometimes solved using general-purpose integer programming solvers. This chapter studies the problem of identifying a compact formulation of the multi-dimensional packing component in a general instance of integer linear programming, reformulating it using the discretisation of Allen--Burke--Marecek, and and solving the extended reformulation. Results on instances of up to 10000000 boxes are reported.

Recommendations

• A space-indexed formulation of packing boxes into a larger box
• Packing small boxes into a big box.
• Packing a trunk
• scientific article; zbMATH DE number 3945878
• scientific article; zbMATH DE number 994195

Cites work

• scientific article; zbMATH DE number 702559 (Why is no real title available?)
• A MIP approach for some practical packing problems: balancing constraints and tetris-like items
• A space-indexed formulation of packing boxes into a larger box
• A time indexed formulation of non-preemptive single machine scheduling problems
• Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• An analytical model for the container loading problem
• Cutting Stock Problems
• Glass cutting in a small firm
• Hardness of approximation for orthogonal rectangle packing and covering problems
• Large-scale multi-period precedence constrained knapsack problem: a mining application
• MIP-based heuristic for non-standard 3D-packing problems
• Modeling and optimization in space engineering.
• Multistage Cutting Stock Problems of Two and More Dimensions
• On the complexity of unique solutions
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• Optimization models for the three-dimensional container loading problem with practical constraints
• Packing small boxes into a big box.
• Probabilistic Analysis of Geometric Location Problems
• Recursive Computational Procedure for Two-dimensional Stock Cutting
• SCIP: solving constraint integer programs
• Solving LP relaxations of large-scale precedence constrained problems
• Solving Non-standard Packing Problems by Global Optimization and Heuristics
• The Three-Dimensional Bin Packing Problem
• The three-dimensional knapsack problem with balancing constraints
• Three-dimensional container loading models with cargo stability and load bearing constraints
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem

Cited in

(1)

• A space-indexed formulation of packing boxes into a larger box

This page was built for publication: Exploiting packing components in general-purpose integer programming solvers

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