CG4AI: A Column Generation Framework for Training AI Models Under Constraints

CG4AI：一种在约束条件下训练 AI 模型的列生成框架

Abstract: Standard machine-learning training minimizes a loss function over a dataset, but does not guarantee that the resulting model will satisfy predefined rules or constraints on its outputs. In many real-world applications, ranging from autonomous systems to network routing, such guarantees are essential.

摘要： 标准的机器学习训练旨在最小化数据集上的损失函数，但无法保证所得模型能够满足预定义的输出规则或约束。在从自动驾驶系统到网络路由的许多实际应用中，此类保证至关重要。

We propose CG4AI, a framework that builds a convex combination of AI models while enforcing linear constraints on the combined output. A master linear program (LP) determines the optimal mixture weights, while a pricing subproblem generates new models guided by LP dual variables, focusing attention on the most violated constraints. A cutting-plane procedure extends feasibility guarantees beyond the training set.

我们提出了 CG4AI，这是一个通过构建 AI 模型的凸组合，同时对组合输出强制执行线性约束的框架。主线性规划（LP）确定最优混合权重，而定价子问题则在 LP 对偶变量的引导下生成新模型，将注意力集中在违反最严重的约束上。切割平面程序将可行性保证扩展到了训练集之外。

We apply CG4AI to two problems: (i) digit classification on MNIST, where we demonstrate four distinct uses of constraints, learning from constraints alone, improving adversarial robustness, correcting misclassified examples, and enforcing output relabeling; and (ii) the multi-commodity flow problem, where link capacity constraints are enforced on neural-network routing predictors. Experiments on MNIST and standard SNDLIB benchmark networks show that CG4AI reliably produces feasible predictors while achieving better accuracy than single-model baselines.

我们将 CG4AI 应用于两个问题：(i) MNIST 上的数字分类，我们展示了约束的四种不同用途：仅从约束中学习、提高对抗鲁棒性、纠正错误分类的样本以及强制执行输出重标记；(ii) 多商品流问题，其中链路容量约束被强制应用于神经网络路由预测器。在 MNIST 和标准 SNDLIB 基准网络上的实验表明，CG4AI 能够可靠地生成可行预测器，同时比单模型基准方案实现更高的准确率。