在信息化时代，手机、计算机等智能产品的普及高度依赖先进芯片技术。芯片集成将普通设备转化为智能产品，这源于公众对技术创新的持续需求。进入后摩尔定律时代[1]后，芯片设计在有限物理尺寸内同时面临优化性能、功耗与成本的挑战。面向芯片设计的优化不仅对电子技术的进步至关重要，还与国家经济和半导体行业的国际竞争力息息相关。

布局优化在芯片设计自动化中占据核心地位，其质量直接影响后续设计任务。传统的电路设计高度依赖经验和手动操作，通常将元器件高度统一以简化问题[2]。然而，随着自动化的进步，越来越多的布局优化任务通过计算机算法得以实现，既提升设计效率，又减少人为失误。现代电路设计已转向混合元器件高度（MCH）配置，由于存在布线能力、时序、功耗与可制造性等严格约束[3]，布局优化难度显著增加。作为装箱问题（BPP）的一种变体，布局涉及根据设计技术的要求将元器件对齐到合法位置，同时分布在有限的芯片区域内。随着新兴技术的演进，布局约束不断变化，优化方法必须持续适应以符合新的设计规则。例如，元器件尺寸的减小虽然带来集成度的提升，但同时也增加了功耗，所以迫切需要创新方法来提高芯片空间利用率。要在芯片设计中保持竞争力，从业者必须根据技术进步和行业变化调整策略。

基础的布局优化问题可描述为：给定一个高度为h、宽度为w的芯片布局区域，其中电源导轨水平布线，每两条导轨之间的间距为h_{\mathrm{0}}。布局优化的目的是在该区域内合法地放置n个元器件，同时最小化布线总长度。每个元器件i（其中\mathrm{1}\le i\le n）的高度为h_i、宽度为w_i，其左下角坐标定义为(x_i,y_i)。此外，元器件i在纵轴上的高度通过k_i来描述。元器件的上下边界包含与电源导轨对应的引脚。图1展示了包含三种高度元器件的合法和非法布局示例。

基于上述描述，可以构建一个基础布局模型[4‒5]：

约束条件为

目标函数（1-1）最小化布线总长度，布线总长度由任意两个元器件之间水平和垂直坐标的平方差定义。元器件布局的基础合法性约束包括：约束（1-2）和（1-3）共同要求所有元器件放置在指定区域内；约束（1-4）明确规定元器件在水平方向上不得重叠；约束（1-5）规定每个元器件的纵坐标必须与相应的电源导轨对齐。由于决策变量x_i和y_i的定义域在约束（1-2）和（1-3）中隐含定义，此处不再赘述。

在这一基础问题的框架上，本研究进一步探讨现代技术对布局优化的影响。这些技术带来了新的挑战和机遇，将在第3节中详细讨论。

本研究提出了一种混合整数线性规划（MILP）模型和Benders分解（BD）算法，以应对芯片设计中的实际布局挑战。通过平衡布线长度和芯片区域的利用率，所提出的方法系统地集成了芯片区域的划分、元器件的坐标、元器件引脚与芯片导轨的对齐以及非法元器件的合并优化。针对该非确定性多项式（NP）难问题，开发了一种精确算法来解决。我们还设计了不同规模的数值实验，通过应用权威竞赛数据作为基准，评估了数学模型和算法的准确性及有效性。此外，我们讨论了芯片区域的纵横比、不同高度元器件的比例、元器件总数和bin总数对芯片设计企业运营管理的影响。我们的发现为指导现代技术下的二维布局提供了宝贵的见解，表明MILP模型和精确算法的结合可以帮助芯片设计企业节省布局成本。

本文的其余部分组织如下：第2节进行文献综述；第3节详述布局优化问题；第4节建立MILP模型；第5节开发精确算法；第6节阐述数值实验；第7节总结研究。

本研究聚焦MCH电路布局优化问题，并设计精确算法求解。因此，本节从两个角度回顾了以往的相关文献：布局优化问题和布局优化相关问题的算法设计。

作为芯片设计过程中的一个重要阶段，布局优化根据上游信息在合法区域内放置可用元器件。为降低企业成本，在布局优化过程中需要考虑元器件高度、阈值电压类型和设计规则。Wu和Chu [6]研究包含单、双行高元器件的MCH电路，通过构建最大加权匹配问题生成候选元器件对。他们的方法在鲁棒性与质量方面表现良好，但忽略现代技术且方案现已不合法。

随着芯片设计的不断发展，电压漏极（VDD/VSS）对齐技术吸引了研究人员越来越多的关注。Chow等[7]表明，具有多行高度的元器件在行之间不是独立的，他们首次考虑了MCH电路的合法布局。他们提出的算法在区域元器件移动和缓冲器插入方面特别有效，通过最小化元器件总位移来提高初始布局的质量。Spindler等[8]提出的Abacus方法可以有效处理单行高度元器件的布局，但不适用于MCH电路。Wang等[4]通过利用Abacus的特性，设计了一种优化方案和一个特别适合芯片设计的目标函数，解决了对电路类型的限制。与分别优化多行和单行高度元器件布局的方法不同，Lin等[9]同时优化了各种高度的元器件。他们提出了一种包含链式移动方案和由密度驱动布局决定的嵌套动态规划的布局方法，解决了有序多行布局问题。他们的布局比逐个合法化元器件的上述工作实现了更好的合法化解决方案。

随着现代电路设计复杂性的增加，Zhu等[5]考虑了特殊元器件以实现电路各方面性能的平衡。这些特殊元器件对布局设计提出了重大挑战，特别是在增加合法化过程的难度方面。他们通过首先确保元器件满足对齐技术的要求，然后逐个调整非法放置的特殊元器件，优化了现有的布局方案。在器件尺寸逐渐缩小的进程中，最小注入面积（MIA）约束成为MCH电路新挑战。Chen等[10]首创将违反MIA的元器件聚类为具有相同阈值电压（Vth）的元器件的方法，然后对组合的元器件进行排序以获得理想的元器件顺序。他们的方法在不需要额外面积开销的情况下有效解决了MIA违规问题。

MCH电路中的布局优化是一个高度复杂的问题，我们在表1中总结了一些代表性的工作[4‒7,9‒10]。在该表中，我们概述了上述研究解决的问题的具体特征。多数研究聚焦常规单/多行高元器件，对特殊元器件关注有限。近年研究日益重视元器件Vth类型差异，一些研究在现有布局方案的基础上开发方法以实现合法化，这些研究大多以最小化元器件总位移为优化目标。元器件的不重叠约束是布局优化的基本条件，但在考虑复杂的现代设计技术时，实现100%的不重叠可能具有挑战性。现有研究多通过将布局规则（如边缘布局）与启发式算法相结合来获得布局解决方案，然而由于这些规则无法覆盖所有可能的情况，所得布局无法完全保证元器件的不重叠放置。同时满足不重叠和VDD/VSS对齐约束的布局优化研究被认为是有效的，布局合法化已成为近期研究的重要趋势。由于元器件类型的多样性和内部引脚配置，实现VDD/VSS对齐并非易事。现有研究常将其他类型元器件分解为标准元器件（即单行高度元器件）组合处理，然后组合这些标准元器件以解决对齐问题。然而，这种分解和合并的方法不适用于特殊元器件，因为它们的引脚位于元器件内部，无法轻易映射到标准元器件。MIA约束作为MCH电路布局优化中的新兴研究，相关研究较少，其解决方法也不成熟。

为了帮助芯片设计企业在布局中应对各种类型的元器件，本研究根据元器件的高度和布线方式考虑了四种类型的元器件。元器件的Vth类型会影响将元器件分配到bin的决策以及违反MIA约束的合并元器件。因此，我们在工作中也考虑了这一因素。与之前专注布线长度优化的研究不同，本研究考虑了布局成本，以提高芯片区域的利用率。这三种先进技术仍值得进一步探索。我们将不重叠约束纳入模型，通过约束强制实现100%的不重叠。通过引入VDD/VSS对齐约束，我们实现了各种元器件引脚与电源导轨的直接对齐。我们提出了一种聚合策略，将具有相同Vth的元器件水平合并为更大的元器件，从而避免违反MIA约束。在现有研究的基础上，我们通过数学建模系统地呈现了这些先进的设计规则，旨在提供稳定且合法的布局解决方案。

随着芯片设计规模的扩大，布局优化方法不断更新。最初，布局优化问题主要通过基于分区的方法[11]和启发式算法[12]解决。随着这两种技术的应用，布局优化问题的规模呈指数增长。为了获得大规模布局的解决方案，Agnihotri等[13]研究了元器件在较小子区域中的排列方式，并开发了最小切割方法。然而，由于子区域划分的随机性，子区域的解决方案与整体布局的相关性较低，导致解决方案质量不尽如人意。

芯片尺寸的缩小和设计规模的扩大促使布局算法进一步发展。分析方法在过去十年的学术竞赛中广泛应用，如设计自动化会议[14]、国际物理设计研讨会[15]和国际计算机辅助设计会议[16]。分析方法主要包括二次布局和非线性优化[17]。二次布局构建了一个便于求解的凸优化模型，但由于模型与实际布局差异较大，解决方案质量不符合芯片设计标准。非线性优化的思想是通过添加基于密度的惩罚成本来近似布线长度，从而生成一个非线性目标函数，然后通过非线性优化方法解决布局问题[18]。

然而，现有的布局优化算法仍无法完全满足解决方案质量和计算速度的双重要求，需要进一步开发优化算法，以应对不断增加的布局规模和日益复杂的设计规则。目前，图形处理元器件加速布局设计[19]和强化学习方法[20]引起了研究人员的广泛关注。然而，这两种方法仍处于探索阶段，在面对复杂且不断变化的设计技术时，其性能和稳定性有待进一步提高。因此，我们将注意力转向与芯片布局设计相似的其他问题，试图通过利用这些经典问题的求解方法来探索本研究的解决方案。

基于二维BPP的芯片布局优化更加强调微元（如元器件）的精确定位和连接，以满足电路的功能和性能要求，其约束条件更为复杂和精确。布局优化问题是BPP的一种变体，因此求解BPP的高效技术也可以应用于布局优化问题。自20世纪60年代以来，BPP发展迅速。基于实际背景，出现了许多BPP的变体，如机械加工行业的切割库存问题[21]、造纸生产行业的切割过程优化[22]以及供应链中的集装箱装载问题[23]。鉴于布局优化对解决方案质量的高要求，应用于BPP的精确算法可以作为参考。启发式算法[24]和近似算法[25]可以为精确算法提供初始解决方案。虽然模拟退火被认为是BPP最合适的启发式算法，但BD算法在BPP研究中的应用频率也显著增加[26]。

与BPP相比，切割和装箱问题也旨在优化给定空间或材料中物体的排列，然而区别在于，切割和装箱问题关注如何将较大物体转化为较小物体，以最大化切割的价值，而BPP则强调如何有效安排各种尺寸的物体。这两个问题都以有效利用空间为共同目标，因此都适用于芯片布局设计。表2对这三个相关问题进行了全面分析。因此，我们总结了切割和装箱问题的求解方法，以适应本研究的求解方法。Serairi 和Haouari [27]研究了具有固定方向的二维BPP，该问题在切割和装箱中广泛应用。他们开发了用于建立下界的理论框架，并进行了实证评估，强调了关系在提高装箱效率和解决方案质量中的重要性。Queiroz等[28]通过约束规划算法确保候选解决方案遵守二维装箱约束。他们还探索了界限和有效切割，同时结合了禁忌搜索和模拟退火的启发式方法以迭代生成解决方案。Delorme等[26]总结了近20年来切割和装箱问题的研究，指出最流行的求解方法是MILP和分支定界，并注意到近年来BD已成为求解切割和装箱问题的越来越受欢迎的选择。

综上所述，关于布局优化问题的文献总体趋势是考虑MCH电路和一些基本条件，这种组合适用于大多数芯片设计工作，使其成为研究人员的热门选择。本研究在此基础上，进一步考虑了Vth类型和一些现代电路设计技术对布局的影响。据我们所知，我们是第一个将布局优化问题表述为MILP模型的研究。此外，鉴于BD在BPP与切割和装箱问题中的应用近年来不断增加，本研究提出了一种基于BD的精确算法来解决所提出的问题，寻求速度和解决方案质量之间的平衡。

在提出数学模型之前，本节详细介绍了芯片布局的两个要素：第3.1节描述了布局优化问题；第3.2节陈述了若干布局设计准则。

芯片布局实际上是一个位置分配问题，确定元器件在芯片区域内的坐标。为了获取元器件的精确坐标，我们假设将矩形芯片区域置于二维笛卡尔坐标系中。如图2所示，坐标系的原点o对应芯片区域的左下角坐标，x轴和y轴分别沿芯片区域的宽度和高度方向延伸。VDD为芯片提供漏极电压，VSS为地线。VDD和VSS导轨之间的间距称为行高，是固定的。元器件的最小宽度称为位点。位点和行高分别是x轴和y轴的单位长度。换句话说，芯片区域是由VDD和VSS导轨交错在布局行之间的电路组成。

此外，每个元器件包含两种不同的引脚类型：VDD和VSS [6]。当元器件上的VDD/VSS引脚与芯片区域中的VDD/VSS导轨放置在相应位置时，元器件可以在电路中发挥作用。元器件的形状统一为矩形，其宽度和高度分别是x轴和y轴上单位长度的倍数。

根据引脚连接和高度的不同，可以区分四种类型的元器件：A、B、C和D。A、B和C型元器件的引脚位于其上下边界，高度分别等于单行、双行和三行高度。D型元器件的高度也是双行高度，但其引脚位于矩形内部[5]，形成更专业的布线配置。

除了这些差异，元器件还可以根据其高、中、低Vth分为三组。Vth仅与元器件注入的介质有关，与其高度或布线方式没有固定关联。例如，在图2中，具有单行高度的元器件A1属于低Vth，而具有相同高度的元器件A2具有标准Vth。具有多种Vth类型的元器件可以实现电路在速度和泄漏功率之间的平衡，而具有相同Vth的元器件聚集可以进一步提高电路的效率[29]。

由于元器件之间的差异，在布局决策中需要考虑诸如相同Vth类型元器件的聚集、元器件密度和芯片区域利用率等因素，这不可避免地使布局更具挑战性。为了实现元器件数量、类型和坐标之间的合理匹配，本研究采用了一种方法，即在芯片区域上反复执行水平和垂直切割，将完整的芯片区域划分为多个较小的矩形块，称为bin。在布局的初步阶段，确定了放置相同元器件类型的区域，而未指定bin和元器件类型的匹配或每个bin的元器件数量。这种划分有助于更精确的元器件布局，遵守关键的设计约束（如布线），同时通过将复杂的布局区域划分为较小的bin来减少全局搜索所需的计算资源。

为了便于理解切割操作，我们在图3中展示了一个切割示例及其顺序。经过六次交替的水平和垂直切割，芯片区域被划分为七个bin。芯片的功能分区可用于计算bin的面积和数量。每个bin内部的空间决定了其可容纳元器件的上限。将芯片区域划分为bin的目的是确保每个bin中存储的元器件具有相同的Vth。在确定每个bin对应的Vth类型后，将给定数量的元器件与bin匹配，以实现相同Vth元器件的聚集。这种划分机制可以避免元器件在局部电路中过度集中，并实现元器件在芯片区域内的均匀分布。

在布局之前，元器件是相互独立的，其坐标未固定。切割布局的目的是提高空间利用率并减少电路的布线总长度，从而降低电路中的延迟并提高稳定性[30]。在澄清了芯片区域的结构特征、元器件类型和bin划分后，本研究在一些布局设计准则下进行优化。

由于布局成本直接影响企业的经济绩效，并与产品质量和客户满意度相关，我们进行了一个旨在降低成本的优化过程。布线长度是衡量布局成本最常用的指标[31]，布线结果也可用于评估布局的质量。我们从两个方面衡量布线长度：布局的紧凑性和布线总长度，将目标从降低成本转变为缩短布线长度。元器件的更密集排列意味着更高的空间利用率和更短的布局布线长度。半周布线长度（HPWL）方法是一种非常准确和快速的布线长度估计方法[32]。在本研究中，我们使用两个指标来评估布局的紧凑性和布线效率。第一个指标是紧凑性度量，使用HPWL方法评估。具体来说，通过计算元器件沿x轴和y轴的最大距离之和来测量紧凑性。第二个指标是布线总长度，表示为每个元器件到原点o的曼哈顿距离的总和。我们将元器件i的坐标设为(x_i,y_i)，原点o的坐标为(0,0)，元器件集合为C，那么布线总长度可以表示为{\sum }_{i\in C}(x_i+y_i)。

图4演示了HPWL方法，其中芯片区域被划分为三个bin。以bin 1为例，x轴上的最大距离存在于元器件A5和C1之间，而y轴上的最大距离在A5和A1之间。因此，bin 1的HPWL值为10.5。类似地，我们可以计算bin 2和bin 3的HPWL值，最终得到整个布局的总HPWL值为34。

基于上述方法，布线总长度的计算可以表示为{\sum }_{z\in Z}{\sum }_{l\in L}\left[\underset{\begin{array}{c}i,i^{\text{'}},i^{\text{'}\text{'}},i^{\text{'}\text{'}\text{'}}\in C\\ i\ne i^{\text{'}},i^{\text{'}\text{'}}\ne i^{\text{'}\text{'}\text{'}}\end{array}}{\mathrm{m}\mathrm{a}\mathrm{x}}(x_i{\mu }_{i,z,l}+y_{i^{\text{'}}}{\mu }_{i^{\text{'}},z,l}-x_{i^{\text{'}\text{'}}}{\mu }_{i^{\text{'}\text{'}},z,l}-y_{i^{\text{'}\text{'}\text{'}}}{\mu }_{i^{\text{'}\text{'}\text{'}},z,l})\right]，其中Z表示bin集合；L表示元器件Vth类型集合；z和l分别是上述两个集合的索引；{\mu }_{i,z,l}是一个二进制变量，如果元器件i的类型l在binz中，则为1，否则为0。然而，这个表达式的计算复杂度为O(|Z|+|L|+\mathrm{4}|C|)。考虑到芯片布局的可扩展性，我们决定修改上述布线长度计算公式以提高求解速度。

我们将芯片区域视为一个整体，直接计算整个电路的HPWL。HPWL方法适用于小规模布局的电路；当布局规模较大时，HPWL比实际布线长度短。为了避免产生这种误差，我们将HPWL乘以一个校正因子。考虑到布线长度与元器件数量成正比，但与bin数量和Vth类型数量成反比，我们在测试后将校正因子设为\sqrt[]{|C|/(\mathrm{1.5}|Z|+|L|)}。修改后的HPWL公式为\sqrt[]{|C|/(\mathrm{1.5}|Z|+|L|)}\underset{\begin{array}{c}i,i^{\text{'}},i^{\text{'}\text{'}},i^{\text{'}\text{'}\text{'}}\in C\\ i\ne i^{\text{'}},i^{\text{'}\text{'}}\ne i^{\text{'}\text{'}\text{'}}\end{array}}{\mathrm{m}\mathrm{a}\mathrm{x}}(x_i+y_{i^{\text{'}}}-x_{i^{\text{'}\text{'}}}-y_{i^{\text{'}\text{'}\text{'}}})，其计算复杂度为O(|C|)，显著提高了求解效率。在图4所示的示例中，修改后的HPWL'约为32.9，与原始HPWL的差距在4%以内。有关HPWL校正因子有效性的实验详见附录A中的第S1节。

在确定元器件的坐标时，需要考虑基本布局条件和现代电路设计技术的双重要求。基本布局条件决定了元器件的分配方案，现代电路设计技术确保了元器件的排列是合法的。在初始布局阶段，元器件被放置在芯片区域内，然后进行细致的匹配过程，将其坐标与相应的bin对齐。以合理的方式将元器件与bin匹配并确保bin中的每个元器件具有相同的Vth是一项挑战。同样重要的是确保每个元器件仅属于一个bin。值得注意的是，bin的容量是有限的，bin内的元器件数量不能超过容量。基本布局条件决定了各种元器件与bin之间的位置和数量关系，而现代电路设计技术对优化提出了更高的要求。

元器件在bin内不是随机放置的，它们的坐标必须遵守设计技术。本研究考虑了三个约束：元器件不重叠、VDD/VSS对齐和解决MIA违规。不重叠约束是合法化的基本条件[33]，要求两个元器件的坐标在x轴或y轴上至少有一个不同。这一约束在实际应用中很有意义，因为重叠的元器件会增加布局的层数，复杂化优化工作。

VDD/VSS对齐约束对元器件的纵坐标提出了更具体的要求。图5展示了四种类型元器件在VDD/VSS对齐约束下的合法和非法条件。合法性的标准是元器件的引脚必须与相同类型的导轨匹配。由于A型和C型元器件具有相同的布线方式，它们可以通过垂直翻转放置在行之间，被统称为奇数行高元器件。B型元器件有两个相同类型的引脚，垂直翻转对它们没有意义[34]。D型元器件的布线方式类似于A型和C型元器件，因为它们的引脚在内部，其坐标位于两条相邻导轨的中间。总之，我们将元器件分为三种类型：单行高度（A和C）、双行高度（B）和特殊（D）。我们进一步根据布线方式确定元器件纵坐标与行高之间的关系。

随着元器件尺寸的不断缩小，芯片设计的复杂性和精细度增加。然而，更小的元器件并不总是更可取的。MIA约束规定了元器件的最小允许面积，违反此约束的元器件需要进一步处理。由于元器件的面积是给定的，解决MIA违规有两种方法：一种是插入相同Vth的填充物以从根本上增加元器件的面积；另一种是聚集过小的元器件并将它们组合以遵守MIA约束。前一种方法增加了设计布局成本并导致空间浪费，而后一种方法经济且已被证明是有效的[10]。根据邻近原则，我们将违反MIA约束的非法元器件组合成一个新实体，确保组合后的面积超过MIA约束规定的下限。本研究基于聚合的思想扩展了元器件的宽度，并在水平方向上解决了MIA违规问题。

该模型包含各种复杂的设计技术，确定元器件的坐标，并通过使用整个电路的布线长度评估布局质量。我们在附录A中的第S2节中展示了以下符号及其与布局优化的关系。

为了优化布局，我们开发了一个MILP模型，考虑了元器件不重叠、VDD/VSS对齐和MIA约束。在构建模型之前，需要解释一些基本假设。

（1）交错的VDD/VSS导轨：芯片区域中VDD和VSS导轨的交错旨在最小化地弹并提高信号完整性。这种技术还有助于更好的热分布，减少密集设计中的热问题。

（2）元器件的高度规格：待布局的元器件高度最高为三行高度，其中特殊元器件的高度为两倍行高，但其布线方式与双行高度元器件不同。

（3）元器件尺寸对布局的影响：每个元器件的物理尺寸直接影响其在布局中占用的面积，因为较大的元器件需要更多空间以避免干扰和信号延迟。每个bin的宽度和高度必须大于任何单个元器件的宽度和高度，以确保布局的稳定性和各种元器件的性能。

（4）芯片区域分割为bin：将芯片区域分割为bin，每个bin都有面积和元器件容量的上限，这对于有效的资源分配和高效的布局管理至关重要。

（5）长度单位的设置：在本研究中，元器件的尺寸在纳米级，而布局区域的尺寸在微米级。因此，本研究全程采用微米作为长度单位。

我们定义了以下三种类型的符号来构建MILP模型：集合用大写字母表示，索引为相应的小写字母；为了突出决策的内容，变量用希腊字母表示；上标用于进一步解释这些符号。

使用上述符号定义的混合整数非线性规划（MINLP）模型如下：

目标（1）从两个方面最小化布局成本。如前所述，布局的紧凑性是评估成本的第一个指标。修改后的HPWL'不是根据最短直线距离计算的，而是根据最长的曼哈顿距离，这与我们从二维坐标角度的建模一致。第二个指标用于评估布局的布线总长度，计算为所有元器件到原点的曼哈顿距离的总和。在实际布线中，并非所有元器件都直接连接到原点，因此这个计算结果是布线总长度的上界。然而，由于在布局阶段无法获得具体的布线细节，且该指标有效地捕捉了布线总长度的变化，因此被认为是一种合理的评估方法。总之，我们的模型通过提高芯片区域的利用率和最小化布线总长度来最小化布局成本。为了确保结果的稳健性，我们在正文中没有为目标函数中的两个指标进行具体的权重分配。然而，考虑到芯片设计公司在实际生产中可能对布局的紧凑性和布线总长度有不同的优先级，我们在附录A中的第S3节中进行了额外的实验来分析这些方面。

约束条件为

约束（2）~（11）是关于基本布局条件的。约束（2）和约束（3）确保元器件放置在芯片区域内。约束（4）确保每个binz中所有Vth类型的元器件总数不超过由元器件总数、元器件尺寸和切割系数共同确定的密度阈值，以防止布局设计过于拥挤或过于稀疏。约束（5）计算binz中l类型的元器件的实际数量，这是关于两个变量{\theta }_{z,l}和{\mu }_{i,z,l}的连接约束。约束（6）确保元器件i只能匹配一个类型l和binz。约束（7）要求binz内的元器件类型l一致。约束（8）规定了bin中可以放置的元器件类型，而约束（9）进一步将bin与元器件关联。约束（10）和约束（11）确保类型l的元器件i的坐标应对应于binz。

约束（12）~（27）对应现代电路设计技术。

约束（12）~（16）确保元器件i和i^{\text{'}}在x或y坐标上至少有一个差异，从而保证这两个元器件在二维坐标系中不重叠。

约束（17）~（23）是关于将元器件上的引脚与VDD和VSS导轨匹配的。约束（17）规定了非特殊元器件的纵坐标，并根据其类型将它们分配到相应的导轨。允许的j值集合（表示导线索引）随元器件类型而变化。对于可以翻转放置的单行高度和三行高度元器件，允许的k_{i,j}范围更广，以适应这种灵活性。约束（18）表示对于一个元器件，必须有且只有一个Vth类型，并且其引脚只能与一条导线相关联。约束（19）声明单行、三行高度元器件i应与类型l匹配，并对应于导线j。约束（20）规定双行高度元器件i与类型l和导线j之间的关系。约束（21）定义特殊元器件的纵坐标，建立这些元器件内部引脚与布局区域内电源导轨的对应关系。约束（22）表示特殊元器件i的纵坐标应与类型l和导线j对应。约束（23）规定所有类型元器件在所有可能导线上的总和应等于待放置的元器件数量，确保没有元器件被遗漏。值得注意的是，由于每个元器件上的引脚位置是预先确定的，元器件的放置方向（原始或翻转）可以从其纵坐标和相应的导线分配中推断出来。

约束（24）~（27）是关于解决MIA违规的。约束（24）比较元器件i的宽度和w^{\mathrm{m}\mathrm{i}\mathrm{n}w}以确定MIA违规。由于第4.1小节中的假设（5），确保了约束（24）的有效性。约束（25）表示如果元器件i的宽度小于w^{\mathrm{m}\mathrm{i}\mathrm{n}w}，它将与其他元器件组合。约束（26）要求组合元器件的宽度超过w^{\mathrm{m}\mathrm{i}\mathrm{n}w}。约束（27）表示组合元器件在x轴上的坐标是连续的。

约束（28）~（33）定义了决策变量的定义域。

上述模型包含几个难以直接使用求解器求解的部分，如目标函数中最小化最大值的结构和约束（9）~（11）中的非线性部分。如果不解决这些问题，模型的计算工作量将增加，进而导致设计周期延长。

对于目标函数（1）中的第一部分，即\sqrt[]{|C|/(\mathrm{1.5}|Z|+|L|)}\underset{\begin{array}{c}i,i^{\text{'}},i″,i″\mathrm{\text{'}}\in C\\ i\ne i^{\text{'}},i″\ne i″\mathrm{\text{'}}\end{array}}{\mathrm{m}\mathrm{a}\mathrm{x}}(x_i+y_{i^{\text{'}}}-x_{i^{\text{'}\text{'}}}-y_{i^{\text{'}\text{'}\text{'}}})，我们定义一个额外的非负决策变量\delta。随后，公式（1）可以通过添加以下约束来构建：

使用\delta表示芯片区域内的最大曼哈顿距离，将最小化最大值的双重目标转化为单目标，允许模型通过CPLEX（IBM ILOG CPLEX Optimization Studio）求解。修订后的目标函数见第4.4.3小节。

约束（9）中的非线性是由决策变量的乘积引起的。令{\pi }_{z,l}表示 {\theta }_{z,l}{\omega }_{z,l}，约束（9）可以修改为方程（35）~（39）。线性化过程在附录A推导1中描述。

类似地，我们使用{\sigma }_{i,z,l}和{\phi }_{i,z,l}替换约束（10）和约束（11）中的双线性表达式，这两个约束可以分别替换为方程（40）~（44）和方程（45）~（49）。这两个线性化过程详细记录在附录A的推导2和推导3中。

这种通过放宽可行域边界的线性化方法使模型能够从非线性转换为线性，并获得全局最优解的下界。与引入大M进行线性化相比，这种方法使用的计算空间更少，求解速度更快。

基于这些新的决策变量和约束，模型M0可以重新表述为MILP模型M1。

约束条件为

式（2）~（8）以及式（12）~（49）。

第4.4节的核心内容总结在图6中，描述了线性化过程。线性化的目的是使模型能够直接由CPLEX求解，并便于应用精确算法。在初始模型M0中，有两个部分需要预处理：非凸目标函数和约束（9）~（11）中的非线性表达式。通过添加新的决策变量\delta，实现从Min-Max问题到最小化问题的转换。通过引入新的辅助变量来替换原始决策变量的乘积，并根据决策变量的定义域定义差异变量，我们可以推导出线性化约束。随后，推导出新的MILP模型M1，可以轻松求解。对于更实际的中等或大规模实例，CPLEX无法在指定设计周期内得到解决方案。因此，在下一节中设计了一种合适的算法来提高求解效率。

考虑到现代电路设计技术，布局优化问题面临重大挑战。在设计周期中，商业求解器（如CPLEX）在数据规模扩大时几乎无法计算结果，而在实际生产中，元器件数量极大，需要开发一种为该模型量身定制的算法。BD以求解大规模优化问题而闻名，广泛应用在供应链[35]、材料运输[36]等领域。我们将迭代优化的思想融入布局模型中，寻求解决方案质量和计算速度之间的平衡。

BD的主要思想是根据求解难度将决策变量分为两类，从而将复杂问题分解为主问题（MP）和子问题（SP）。通过迭代求解这两个小模型，我们可以比直接求解原始模型更容易地获得结果。

在本研究中，决定元器件、bin、Vth和导轨之间相对位置关系的决策变量包括{\theta }_{z,l}、{\mu }_{i,z,l}、{\omega }_{z,l}、{\alpha }_{i,i^{\text{'}}}、{\beta }_{i,i^{\text{'}}}、{\gamma }_{i,i^{\text{'}}}、{\tau }_i以及{\rho }_{i,l,j}。上述间接确定元器件坐标的变量统一放置在MP中。然而，与元器件坐标直接相关的核心变量x_i和y_i被分配到SP中以做出最终决策。MP中的二进制和整数变量被代入SP中，然后从SP中计算最优割，并添加到MP中，这极大地提高了求解效率。结合两级解耦的思想，我们迭代优化原始问题的上、下界以获得最优解。

SP根据MP获得的相对位置关系确定元器件的最终坐标。元器件的纵坐标受VDD/VSS对齐约束的影响，在决定元器件坐标的过程中可能存在一定的随机性，因此确保SP有解至关重要。首先，SP为原始问题提供了上界，表述如下：

约束条件为

式（2）、（3）、（28）、（29）、（34）、（41）、（44）、（46）、（49）；

SP中的所有变量都是连续的，模型是线性的。带帽的符号表示MP中的决策变量。为了确保迭代过程的顺利进行，我们首先设计了一个初始解生成规则。该规则要求按高度对所有元器件进行排序，然后从底部到顶部将元器件放置到布局区域中。使用这种方法，获得一个初始布局解，然后传递到SP中进行进一步优化。SP求解更精细的布局，并将元器件位置传递到MP中进行全局调整。这个过程在每次迭代中重复，每轮生成一个新的割。我们基于对偶理论推断最优割，并用它来收缩可行域，从而提高布局质量。

根据SP的约束，我们引入对偶变量P_i^n，其中n\mathrm{ϵ}\{\mathrm{1,2},\dots ,\mathrm{21}\}。这些对偶变量及其对应的约束通过加权和被纳入SP的原始目标函数中，生成一个增强的目标函数。这种表述通过将约束直接集成到目标中简化了问题。所得拉格朗日松弛表达式如下：

在求解SP后，我们获得一个可行解，并可以基于对偶理论推断最优割。我们遵循Adulyasak等[37]的思想，将所有场景合并为一个SP，并在每次迭代中仅添加一个最优割，以避免求解过多SP。大多数研究首先基于SP获得对偶子问题（DSP），然后通过最优割法将DSP与MP连接起来。由于本研究涉及大量决策变量，并且在对偶过程中max函数和求和的合并具有挑战性，因此我们选择拉格朗日松弛来确定最优割。根据拉格朗日松弛展开，我们引入一个新变量\zeta来表示预期成本。与元器件相对位置对应的MP可以重新表述如下：

约束条件为

式（4）~（9），（14）~（16），（18）~（20），（22）~（26）和（30）~（33）；

约束（68）表示对所有MP解都有效的最优割。

算法的核心在于确保在每次迭代中传递的变量在SP和MP中都是有效和可行的。具体来说，当MP确定元器件的相对位置时，约束相对宽松，而SP在可行域内进一步细化元器件的精确位置坐标。因此，MP用于提供元器件的相对位置，而SP确保这些位置满足布局约束，最终提供精确的布局坐标。

在每次迭代中，新产生的最优割是算法进展的关键。通过求解SP，我们获得一个可行解，并通过对偶理论推断割的优化性。这个最优割为后续迭代提供了关键指导，确保每一轮在可行域内提高解决方案质量，从而接近最优解。基于我们的算法，MP和SP可以高效协作，使每次迭代都能收缩可行域并逐步优化布局，最终求解元器件的最优坐标。

总之，BD迭代地将MP中的变量值传递到SP，然后SP将最优割返回到MP。这种迭代思想逐渐缩小了解空间，最终获得最终解。BD的伪代码在附录A的第S5节中展示，框架如下：

步骤1：初始化。设置上界\mathrm{U}\mathrm{B}=\mathrm{\infty }，下界\mathrm{L}\mathrm{B}=-\mathrm{\infty }，迭代次数I_n=\mathrm{0}，迭代上限I_{n\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{50}，可接受间隙g=\mathrm{0.01}(w+h)。计算初始指导、SP和MP的目标值，并将它们分别设为\mathrm{F}\left(o\right)、\mathrm{F}\left(sp\right)和\mathrm{F}\left(mp\right)。

步骤2：初始解设置。根据从高到低的排列顺序和沿芯片区域边缘放置元器件的思想，我们设计了一组初始可行解。由于\mathrm{F}\left(o\right)>\mathrm{L}\mathrm{B}，更新\mathrm{L}\mathrm{B}，\mathrm{F}\left(o\right)\leftarrow \mathrm{L}\mathrm{B}。

步骤3：求解SP。将初始指导的相对位置信息代入SP以获得元器件的初始可行坐标。如果，更新\mathrm{F}\left(sp\right)\leftarrow \mathrm{U}\mathrm{B}，I_n+\mathrm{1}\leftarrow I_n。

步骤4：推断本轮迭代的最优割。如果\mathrm{U}\mathrm{B}-\mathrm{L}\mathrm{B}\le g，停止迭代；否则，转到步骤5。

步骤5：求解MP。将通过拉格朗日松弛获得的最优割代入MP以获得相对位置信息。如果\mathrm{F}\left(mp\right)>\mathrm{L}\mathrm{B}，更新 \mathrm{L}\mathrm{B}，\mathrm{F}\left(mp\right)\leftarrow \mathrm{L}\mathrm{B}。如果I_n\ge \mathrm{1}，转到步骤2。

步骤6：迭代终止。存在以下任何一种情况：① \mathrm{U}\mathrm{B}-\mathrm{L}\mathrm{B}\le g，I_n=I_{n\mathrm{m}\mathrm{a}\mathrm{x}}，算法终止并输出最优解。

在本研究中，我们的算法保证收敛。具体来说，我们在迭代中获得新的最优割，算法最终将收敛到最优解。

原始的最佳解为(x^{*},y^{*})，其中x和y分别表示整数向量和非负的实向量。根据经典BD原理，SP有以下表达式：

约束条件为

其中，A是一个矩阵，代表整数变量线性约束的系统；B是一个矩阵，对应于涉及实向量\tilde{\mathit{y}}的对偶约束中的系数；\mathit{b}是一个常数向量；向量\mathit{c}代表SP目标函数中的系数。

由于在第4.3节中对目标和约束的处理，SP的解是单调的。存在一个足够大的N，使得对于所有n\ge N，SP的最优解满足{\mathit{c}}^{\mathrm{T}}{x}_n\le {\mathit{c}}^{\mathrm{T}}{x}_{n-\mathrm{1}}。这确保了算法的每次迭代都产生一个至少与前一个同样好的解。芯片区域限制了SP的可行解数量，从而限制了SP的解空间。因此，原始问题的最优解对应于优化SP的解。