整数线性规划

分类: 基础理论

整数线性规划

定义

在线性约束下最优化线性目标函数，且决策变量被限制为整数（通常为 0/1 二值）的数学规划问题。

数学形式

min⁡x  cTx,s.t.  Ax≤b,  x∈{0,1}n\min_{x} \; c^T x, \quad \text{s.t.} \; Ax \leq b, \; x \in \{0, 1\}^n

其中 cc 为目标系数向量，A,bA, b 定义线性约束，xx 为 0/1 决策变量。

核心要点

NP-hard 问题：一般情况下求解复杂度指数级，但规模较小时可用分支定界（Branch & Bound）精确求解

松弛求解：先求解连续松弛（LP），再用取整策略或 Cutting Plane 方法逼近整数解

在 NAS 中的应用：将候选块选择编码为 0/1 变量，延迟预算编码为线性约束，实现在硬件约束下的最优架构选择

代表工作

Fast-FoundationStereo: 用 ILP 在延迟预算约束下选择最优代价过滤块组合

相关概念

神经架构搜索

延迟感知优化