Linear Programming-based algorithms for orthogonal packing

我们的目标是开发高效的精确和启发式的方法，正交包装在两个和更多的维度使用线性规划（LP）。基本的正交装箱问题（Orthogonal Packing Problem，缩写为OPWP）是一个决策问题，它询问一组正交的物品是否可以放置在一个给定的正交容器中，并且所有的边都平行，没有旋转。这个问题涉及到正交带包装，装箱，背包问题以及调度问题。今天众所周知的方法大多拥有纯粹的组合结构（搜索策略和边界）。然而，几年来人们已经知道，一维松弛提供了强的边界，这是可计算的线性规划。我们的工作组已经集成了这样的界限的区间图算法（以前已知的精确方法），这导致其改进。这表明在这个方向上需要进一步的研究。最简单的方法是在现有方法中集成新的边界，而不改变搜索策略。然而，一个有趣的问题是搜索策略的适应性。这似乎是一个相当复杂的任务，因为问题的组合性质（例如，非重叠条件、每个维度中位置的非中断性）。

The goal is to develop efficient exact and heuristic methods for orthogonal packing in two and more dimensions using Linear Programming (LP). The basic Orthogonal Packing Problem (OPP) is a decision problem asking if a set of orthogonal items can be placed in a given orthogonal container with all sides parallel, without rotation. This problem relates to the orthogonal strip-packing, bin-packing, and knapsack problems as well as to scheduling problems. Today’s well-known methods mostly possess purely combinatorial structure (search strategies and bounds). However, it has been known for several years that the one-dimensional relaxation of OPP provides strong bounds which are computable by Linear Programming. Our working group has integrated such bounds in the interval graph algorithm (a previously known exact method), which lead to its improvement. This suggests further research in this direction. The simplest effort would be just to integrate the new bounds in existing approaches without changing the search strategy. However, an interesting question is the adaptation of the search strategy. This seems to be a rather involved task because of the combinatorial properties of the problem (e.g., non-overlapping conditions, non-interruptedness of the location in each dimension).