摘要

混合整数线性规划（MILP）具有广泛的应用。在实际中，改进 MILP 求解器的性能通常需要大量高质量数据，这些数据往往难以收集。研究人员转向生成技术来生成额外的 MILP 实例，但现有的方法没有考虑到约束系数矩阵（CCM）中的特定块结构，这些结构与问题表述密切相关。因此，它们容易生成计算上简单或不可行的实例。为了解决这一挑战，本文提出了一个新的 MILP 生成框架，称为块结构分解（MILP-StuDio），通过保留块结构来生成高质量实例。

具体来说，MILP-StuDio 通过识别 CCM 中的块并将其分解为块单元开始，这些块单元作为 MILP 实例的构建块。然后通过设计三种操作来通过删除、替换和追加块单元来构造新实例，能够生成灵活大小的实例。MILP-StuDio 的一个吸引人的特点是其强大的能力，能够保持生成实例的可行性和计算难度。在常用基准上的实验表明，使用 MILP-StuDio 生成的实例，基于学习的求解器能够显著减少超过 10% 的求解时间。

方法

MILP的块结构

MILP 问题的约束系数矩阵（CCM）是一个稀疏矩阵，它包含了问题的所有约束和变量。CCM 的块结构是指 CCM 中的子矩阵，这些子矩阵具有相同的非零元素模式。MILP 问题的块结构反映了问题的结构，例如哪些变量和约束是相关的。

上图是4个问题（combinatorial auctions (CA), item placement (IP), multiple knapsacks (MIK), and workload balancing (WA)）的CCM矩阵通过排列后得到的附有规律的图，行是约束，列是变量，白色像素代表其系数不为0。

现有生成实例方法的问题

本文主要比较另外两个基线方法：Bowly和G2MILP，通过可视化的方法展现出它们的生成实例的问题。

  • Bowly 是一种基于统计的 MILP 实例生成方法，旨在通过控制特定的统计特征来生成与原始实例具有相似统计属性的新实例。具体来说，Bowly 方法通过调整系数密度和系数均值等统计特征，生成与原始实例在统计上相似的 MILP 实例。
  • G2MILP 是一种基于学习的 MILP 实例生成框架，利用深度学习模型来捕获全局实例特征，并通过迭代修改原始实例中的约束来生成新实例。G2MILP 的核心思想是通过掩码变分自编码器（VAE）来逐步替换和修改原始实例的约束节点，从而生成新的实例。

从可视化结果可以看出来，这两种方法会都会破坏原有实例的块结构，使得生成出来的实例与原实例不相似，从而影响了下游的学习任务的效果。

块分解

MILP-StuDio 的核心是块结构分解，通过重新排列 CCM 的行和列来识别块结构。

本文首先通过 GCG （Generic Column Generation）求解器中的结构检测器来重新排列 CCM，进行初步分块。然后再使用以下算法进一步分解特定块。这个算法能够处理比 GCG 更复杂的块结构，例如在 WA 中具有 M-Cons、B-Cons 和 BD-Cons 的实例。

该算法是包含了超参数的分割算法，用于区分出D、F、B等变量和约束，基于以下观察设计的：

  • 对于CCM中的行 A∈Rm×nA\in\mathbb{R}^{m\times n}：

    • xmaxx_{\text{max}} 是非零系数的最大 xx 坐标
    • xminx_{\text{min}} 是非零系数的最小 xx 坐标
    • hxh_x 是该行非零系数的数量

    对于CCM中的列：

    • ymaxy_{\text{max}} 是非零系数的最大 yy 坐标
    • yminy_{\text{min}} 是非零系数的最小 yy 坐标
    • hyh_y 是该列非零系数的数量

    观察结果：

    • M-Con 行特征
      非零系数具有大范围的xx-索引：
      ∙\bullet 较大的xmax−xminx_{\text{max}} - x_{\text{min}}
      ∙\bullet 较高的xx坐标标准差（standard deviation）

    • B-Con 行特征
      非零系数具有较窄的xx-索引范围：
      ∙\bullet 较小的xmax−xminx_{\text{max}} - x_{\text{min}}
      ∙\bullet 较低的xx坐标标准差

    • Bd-Var 列特征
      非零系数具有：
      ∙\bullet 广泛的yy-索引（较大的ymax−yminy_{\text{max}} - y_{\text{min}}）
      ∙\bullet 高密度（列中非零比例 hy/mh_y/m 较大）

    • DB-Cons 定义
      包含 Bd-Vars 的约束条件

结构库构建

通过上述分解得到的基本块，构建相应的二分子图，并利用这些子图来构建结构库。这个结构库作为块单元的存储库，允许高效地存储、检索和利用块信息。

块操作

三种块操作来生成新实例：减少、混合和扩展。

  • 减少操作涉及从原始实例中随机采样一个块单元并删除它；
  • 混合操作涉及从原始实例中随机采样一个块单元，并从结构库 L 中随机采样另一个块单元，然后用后者替换前者；
  • 扩展操作涉及从结构库 L 中随机采样一个块单元并将其附加到原始实例中。

实验

实验设置

我们在四个 MILP 问题基准上进行实验：组合拍卖（CA）、有容量的设施选址（FA）、物品放置（IP）和工作负载分配（WA）。我们使用三个指标来评估原始和生成实例之间的相似性：图统计、计算难度和可行比率。我们考虑了两种基线：基于统计的 MILP 生成方法 Bowly 和基于学习的方法 G2MILP.

实验结果

相似性

MILP-StuDio 在图结构分布相似性得分方面显著高于基线方法。随着修改比率的增加，MILP-StuDio 的相似性得分下降幅度较小，而 G2MILP 的相似性得分下降幅度较大。

计算硬度和可行性

MILP-StuDio 生成的实例在计算硬度和可行性方面与原始实例非常接近，而基线方法生成的实例在计算硬度方面显著退化，且 G2MILP 在 FA 和 WA 数据集上的大部分实例不可行。

改进学习求解器

MILP-StuDio 生成的实例显著提高了学习求解器的性能，包括基于预测和搜索的 PS 方法和基于学习的分支方法。例如，在 CA 和 FA 数据集上，PS 方法在 MILP-StuDio 生成的实例上达到与原始实例相同的解，且求解时间更短；在 IP 和 WA 数据集上，MILP-StuDio 生成的实例使得 PS 方法达到更小的绝对原始间隙。

生成效率

MILP-StuDio 在生成效率方面显著优于 G2MILP，尤其是在处理大规模实例时。

结论

我们提出了一个新的 MILP 生成框架 MILP-StuDio，通过块结构分解来生成高质量的 MILP 实例。MILP-StuDio 能够有效地保持生成实例的计算硬度和可行性，具有强大的可扩展生成能力和高效率。实验表明，MILP-StuDio 在提高学习求解器性能方面非常有效。