英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料
正交方向二维矩形包装问题的约束规划方法
MARTIN BERGER, MICHAEL SCHROuml;DER, AND KARL-HEINZ KUuml;FER
摘要：我们提出了一种基于约束的正交方向二维矩形填充问题的求解方法。这个问题是将一组可以旋转90度的矩形排列成最小尺寸的矩形，并且两个矩形不会重叠。在2.5D系统封装式集成电子系统的布局中，电子设备的放置是一个重要的问题。Moffitt等人用分枝定界法求解无定向的填料，并使用约束传播。我们将它们的传播技术推广到允许定向。我们的方法是比较一个混合整数程序，我们提供的结果优于它。
关键词：矩形包装，正交方向，非重叠约束，约束传播。
1.简介
矩形填充问题出现在现实世界的许多应用中，并对运筹学、约束规划、人工智能等领域的研究人员提出了挑战。我们用正交方向(RPWO)来解决二维矩形填充问题，即将可旋转90度的矩形放置到矩形容器中，使两个矩形不重叠。最小化容器尺寸是一个NP-hard组合优化问题。
在2.5D System-in-Package (SiP)布局设计[9]中就出现了这样的问题。2.5D SiP是一种将异构电子元件垂直堆叠或折叠在模块上的现代集成方式。SiP集成符合现代对微型化电子系统的要求，市场需求预计将不断增长，但仍缺乏标准化的设计自动化工具。图1举例说明了两种2.5D SiP技术。
图 1 SiPs的两个插图:集成在柔性弯曲的基板上(左)和集成在刚性模块上(右)，这些模块通过导电焊锡球进行电连接
布局过程被细分为三个优化问题[10]的序列。在划分步骤中，组件被分配给垂直堆叠的模块。在放置步骤中，组件被放置在每个模块的一侧。每个模块上的放置问题涉及一个RPWO。路由步骤包括垂直互连的布置和各模块内的路由。图2说明了SiP设计中的布局步骤。
图 2 SiPs的布局过程:组件与模块的划分;组件放置在模块侧面;通过垂直互连和模块进行路由
我们建议使用我们的新型原型电子设计自动化(EDA)工具3D SiP专家来布置SiP。此工具使用在脱机阶段计算的SiP布局数据库。然后在在线阶段，工程师可以使用此工具快速导航到他感兴趣的SiP布局。设计人员可以限制和选择多个标准的值，如SiP的大小、线路、热和电性能。这种新的方法加快了布局过程，避免了耗时的重新设计周期。
对于SiP布局中的布局问题，我们需要一个充分的算法方法。许多方法从元启发式，线性，混合整数，非线性和约束规划已发展为矩形包装[11,2,7,6,1]。然而，定位常常被忽视，大多数方法不能集成SiP设计中出现的重要约束。因此，我们扩展了Moffitt等人的元约束满足问题方法(CSP)。它们的分支和界解决了最小的面积填充，并使用约束传播。
我们推广了定向的传播算法，并证明了元CSP方法与混合整数规划的关系。我们将扩展后的meta-CSP与MIP进行比较，并提供了优于后者的数值结果。综上所述，我们的方法解决了RPWO问题，可以扩展到SiP组件的布线问题，作为SiP设计自动化工具的算法。
本文的概要如下:在第二节中，我们介绍了我们的表示法和问题的提法，然后在第三节中讨论了元CSP模型，在第四节中讨论了我们对正交方向的推广。在第5节中，我们提出了一个MIP公式，并讨论了它与我们的方法的相似之处。然后，我们在第6节中为我们的实现提供数值结果，讨论它们，并在第7节中总结未来工作的大纲。
2.问题公式化
我们用R：={,hellip;,}表示矩形，I：={1,hellip;,n}表示下标；，isin;N表示矩形宽度和高度，,isin;Rge;0为矩形的左下角的坐标，isin;{0,1}表示矩形的方向；W, Hisin;Rge;0表示容器的宽度和高度的上限值Wmax，Hmax。我们将RPWO定义为具有线性目标的最小半周长填充问题：
(RPWO) min 服从于
(1-2)确保矩形包容在容器内，(3)定义方向矩形的大小，(4)确保没有两个重叠，将它们分别放在左边()、右边()、下面()或上面(),(5)为矩形坐标的非负约束。
- Meta-CSP模型
在[8]最小面积矩形填料与固定方向的探讨。不需要搜索、，而是为每个非重叠约束引入元变量。的值域为，表示与的几何关系。搜索树在上分枝，并通过约束传播进行修剪。传播使用增量维护的图形来描述部分解决方案。图3显示了完整的解决方案和相应的矩形布局。
图 3 一个完整的Meta-CSP解决方案和相应包装的例子
R的子集S的部分填充由两组不等式来描述，其中表示水平关系，表示垂直几何关系。和被编码在两个加权有向图和中，表示和的左前导和下前导。两个图的顶点表示矩形，边表示矩形的水平或垂直优先级。从j到i的边的权值由矩形的大小-s给出。为了规范地说明图的算法，用矩形的负大小对边进行加权。同样为了更好的说明，我们为每个矩形顶点i引入了一个输出边为n 1的源顶点和一个输入边为0的汇聚顶点每个矩形顶点i的边权值为0。图4显示了图3中的示例的和。
图 4 图3中示例的优先图
那么，当且仅当()没有负循环时，()是一致的。通过检查()[4]的全对最短路径矩阵()的主对角上的负项，可以在多项式时间内检测出负循环。在搜索过程中维护和，并使用O()中的Floyd-Warshall算法进行更新。在图5中，我们为图3中的示例提供了全对最短路径矩阵。
图 5 图3中示例的全对最短路径矩阵
当一个元变量在搜索过程中被一个水平级进级实例化时，距离图就会被扩展为顶点i和j之间的一条边，Floyd-Warshall就会被应用来更新。当使用垂直级进级实例化时，和都类似地更新。
无环有向图和可用于确定矩形坐标和以及容器的宽度W和高度H的下界。从顶点i到顶点0的负最短路径长度给出了下界。在全对最短路径矩阵和的帮助下陈述这些条件，我们得到以下的下界，
因此，我们的目标也有一个下界，即。
一旦实例化了所有，等式就成立了。
除了使用、、、来获取容器的矩形坐标和尺寸外，这些数据结构还允许我们尽早有效地检测不一致性，并应用一些特定的传播技术。我们将在下面讨论一些技术，并参考[8]进行详细描述。利用, , , ，在搜索过程中O(1)应用以下传播技术:
前向检查(FC)删除了相对于部分赋值的不一致值。若要检查值是否一致，则一定不能小于s。FC的传播规则如下:
删除包含的变量(RS),和将传递地表示。当且仅当从到的最短路径小于-s时，的一个值是满足的。RS的传播规律如下:
在图6中，我们演示了FC如何检测负周期，在图7中，我们演示了RS如何检测包含的变量。
图 6 负循环检测与前向检查 图 7 检测包含的变量
另外一种剪枝技术是位移的检测(DC)。包含成对的、水平的或垂直的、对齐的矩形，其对齐超过容器的部分解决方案会导致死胡同。在水平和垂直位移图上应用贪心启发式算法，以及早发现这种集合。
此外，为了避免对称解，在搜索之前和搜索期间，在[8]的分支和边界上应用了对称性破缺。一个动态最受约束的变量，首先启发式地将大矩形对的排序。首先选择面积增长最小的关系。如果情况相同，选择松弛度-s最少的关系式。
- 具有方向的Meta-CSP模型
为了将方向引入到Meta-CSP模型中，我们推广了剪枝技术FC、RS和DC。当没有分配时，我们要么使用的最小边长，要么使用的最大边长来传播。图8说明了泛化的概念。当分配了时，我们使用类似于Meta-CSP模型的和。
图 8 最大和最小方形边长所组成的矩形被用于我们推广传播技术
我们将应用于FC, 应用于RS，广义传播规则如下:
对于DC，我们还将的应用于未实例化的。
为了加强传播，我们整合去向后提出了新的修剪技术。我们分配的，它只适用于具有特定的容器。超过Wmax的规则如下，下界和Hmax的类似规则如下:
在类似的方式下，我们给的赋值使其只能在在之前有一个确定的。左边的优先级()规则如下,其他几何关系的类比规则如下:
(16)
(17)
同样，对实例化=1应用了类似的规则。
在此基础上，提出了一种基于lex-leader约束的对称破缺技术，该技术通过移除一个水平方向和一个垂直方向的几何关系，对等大小的矩形施加lex-leader约束。lex-leader约束和三个大小相等的矩形的示例如图9所示。
图 9 3个大小相等的矩形的lex-leader约束的说明。在、和区域内，一个水平和一个垂直的分离物被移除。
除了元变量之外，我们还必须搜索的方向。通过我们的归纳，我们可以独立实例化和排序。我们在分配了元变量之后立即实例化和。我们定义这个排序为(, , )。与优先排序相比，这种排序只略微削弱了传播，优先排序在这里称为标准顺序(o, C)。
为了增强穷举搜索方法，我们用上的一个上界来初始化它。我们从一个由贪心最佳拟合装箱启发法构造的可行解中得到了这个上界。
我们的启发式算法将所有矩形都装入一个具有固定宽度和高度的给定容器中。容器的半周长最初设置为，然后迭代递增，直到找到所有矩形的可行填充。在每个迭代中，对于给定的容器周长的一半，尝试不同的宽度和高度对。
贪心启发式算法一次装入一个矩形。随后的每个矩形都在插入位置进行填充，其中的一个角及其相邻的边与其他矩形或容器边相接触。我们的插入位置概括在[3]中定义的二维装箱问题的法线位置。
我们的算法不是静态地对矩形排序，而是动态地选择下一对最佳的矩形和插入位置。类似于[5]中的触摸周长算法，我们更喜欢插入矩形，其中插入的矩形与已经填充的矩形共享尽可能多的边。
- 混合整数规划
现在我们将RWPO表示为一个混合整数程序。因此，我们必须解决分离性非重叠约束(4)，通过big-M松弛变量和辅助变量:
约束(19)表示非重叠约束(4)的线性分界点，约束(20)保证存在最多一个水平和最多一个垂直的几何关系，约束条件(21)保证在任何矩形对之间存在至少一个几何关系。
得到的MIP模型和meta-CSP模型在不同方面有相似之处。我们在下面讨论一些相似之处。
定义1.关键路径问题是在有向无环图中找出从任意源s到任意汇聚点t的最长路径。
引理2.meta- CSP模型中W和H下界的确定等价于以下形式的关键路径问题的求解:
等价于
等价于
证明。根据是有向无环图的性质，最长路径问题可以作为具有非正边权值的最短路径问题来解决。具有源点s、汇聚点t和非负权边的有向无环图的关键路径问题可表示为最短路径线性规划[12]的对偶:为最短路径最优性条件，成立的条件为： 其中的变量分别对应为：和
我们现在证明，在MIP模型中求解具有固定方向的部分解s的线性松弛与在meta- CSP模型中求解部分解的有向无环图的最长路径问题对目标的影响是相同的。因此，这两个模型为目标函数提供了相同的下界。
定理3.假设s是具有固定方向的RWPO的部分解,即一般情况下。则MIP模型中s的线性松弛的目标函数值等于由meta-CSP模型中s的图和的关键路径问题得到的目标函数值，即，
证明。已知部分解s，我们得到MIP中s的剩余线性松弛:
(22) 服从于
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
(31)
(32)
(33)
(34)
(35)
(36)
(37)
(38)
(39)
包含约束(23-26)和非负性约束(38-39)
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239242]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
