将一系列矩形放置在给定区域

Question

我想将一组矩形放入给定宽度的区域，并最大程度地减少总高度。我已经在Minizinc中制定了一个解决方案，但是运行时间很长。

最终结果是在几秒钟之后出现的，但是直到10分钟过去了，跑步才停止。这是使运行时间更快/提高性能的一种方法吗？我应该使用累积约束吗？

Answer 1

除 @dekker1的答案外，还有一些评论。

首先一些问题：您使用了哪个求解器？第一个答案是否直接找到了最佳解决方案？

您可能会与其他一些Flatzinc求解器获得更快的求解时间。我测试了您最初包含在该问题（后来删除）和一些不同的Flatzinc求解器中的模型。另外，我打印了目标值（makepan），以比较中间解决方案。

• gecode：立即找到一个69的pan的解决方案，但随后花很长时间找到最佳值（即17）。 15分钟后，没有进行改进，我停止了跑步。对于Gecode，您可能会通过不同的搜索策略获得更好的结果，请在此处查看更多信息： https://www.minizinc.org/doc-2.3.1/en/lib-annotations.html#search-search-annotations 。

• chuffed：几乎直接找到了17个制造物，但是在所有8分钟内花费了17个以证明17是最佳值。免费搜索测试的速度不是更快（9min23s）。

• or-tools：找到0.6s的Makepan（并证明它是最佳的）。

startX: [0, 0, 0, 3, 3, 13, 0, 14, 6, 9, 4, 6, 0, 10, 7, 15]
startY: [0, 3, 7, 0, 6, 5, 12, 0, 2, 6, 12, 0, 15, 12, 12, 12]
makespan: 17
----------
==========

使用免费搜索（-f flag）时，有时可以更快地求解器，但是在这种情况下，求解器较慢：4.2s。至少只有1个线程。当添加更多线程（此处12）时，在0.396中找到了带有免费搜索标志的最佳解决方案。

有很多不同的flatzinc求解器可以测试。有关其中的一些信息，请参见最新的Minizinc挑战页面： https：> https://www.minizinc.org/challenge20211 /results2021.html 。

关于累积，似乎有些求解器的限制速度可能更快，但是有些求解器较慢。最好的方法是对或在某些不同的问题实例上进行限制。

总而言之，偶尔可能需要尝试使用不同的约束和/或求解器和/或搜索策略。

Answer 2

这似乎是直接的矩形包装问题。适合此特定问题的算法，包括正方形堆积，具有/无旋转的直线填料等变化。

特别是在微型素中，这是在第二个Minizinc Coursera课程中讨论的主题：。这应该为您提供所有必要的知识，以为问题创建一个良好的模型。