通过构造良好结构的分段线性插值，显著提升高维数据拟合的优化求解效率。
Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions
- 基于差凸表示法，构造具有良好结构的分段线性插值以增强模型
- 六种紧化策略结合使用可使求解时间大幅缩短，尤其在高维场景下
- 适合需要高效求解分段线性逼近问题的优化研究者和工程应用
本文针对任意维度下数据集的连续分段线性（CPWL）逼近问题，提出改进混合整数线性规划（MILP）公式的紧化方法。该方法利用CPWL函数的差凸（DC）表示。研究引入了‘良好结构的CPWL插值’概念，并证明任一数据集的CPWL插值均存在一个良好结构版本。这一结论对紧化MILP至关重要。文中提出了六种紧化策略：固定部分变量值、添加新约束、确定小的big-M参数值以及采用更紧的变量边界。这些方法充分利用了DC表示特性和良好结构插值的内在特性。实验表明，特定组合的紧化策略能显著提升求解速度，尤其在考虑良好结构解时效果更佳。
原文摘要 · Abstract (English)
This paper addresses the problem of tightening the mixed-integer linear programming (MILP) formulation for continuous piecewise linear (CPWL) approximations of data sets in arbitrary dimensions. The MILP formulation leverages the difference-of-convex (DC) representation of CPWL functions. We introduce the concept of well-behaved CPWL interpolations and demonstrate that any CPWL interpolation of a data set has a well-behaved version. This result is critical to tighten the MILP problem. We present six different strategies to tighten the problem, which include fixing the values of some variables, introducing additional constraints, identifying small big-M parameter values and applying tighter variable bounds. These methods leverage key aspects of the DC representation and the inherent structure of well-behaved CPWL interpolations. Experimental results demonstrate that specific combinations of these tightening strategies lead to significant improvement in solution times, especially for tightening strategies that consider well-behaved CPWL solutions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。