非线性整数规划 非线性整数规划（Nonlinear Integer Programming）是指目标函数或约束条件中至少有一个为非线性，且决策变量需取整数值的优化问题。其一般形式可表示为： \[ \min f(x) \quad \text{s.t.} \quad x \in S \cap \mathbb{Z}^n \] 其中 \( f: \mathbb{R}^n \to \mathbb{R} \) 为非线性函数，\( S \subseteq \mathbb{R}^n \) 为由等式或不等式约束定义的可行域（可能包含非线性函数），\( \mathbb{Z}^n \) 表示整数约束。 1. 问题特征与挑战 离散性与非线性叠加 ：整数约束导致可行域为离散点集，非线性进一步使问题失去凸性，传统连续优化方法（如梯度法）直接失效。 计算复杂性 ：属于NP难问题，即使判断可行解是否存在也极具挑战。例如，非线性背包问题、整数二次规划均属此类。 局部极小陷阱 ：非线性函数可能存在多个局部极小点，整数约束加剧了陷入次优解的风险。 2. 经典应用场景 工程设计 ：如桁架结构优化中杆件截面取离散值，目标为最小化重量（非线性应力约束）。 供应链网络 ：设施选址与路径优化中固定成本为非线性函数，决策变量为整数（是否建仓、车辆数量）。 化学过程合成 ：反应器单元选择（0-1变量）与连续操作参数（如温度）共同影响非线性成本函数。 3. 核心求解方法分类 (1) 精确算法 分支定界法 ： 通过松弛整数约束生成连续子问题，利用目标函数下界剪枝。 关键改进 ： 非线性规划松弛 ：每个节点求解非线性规划（如序列二次规划）获得边界。 凸松弛技术 ：用凸函数外包络替代非凸项（如McCormick松弛处理双线性项）。 分支定价法 ： 结合列生成处理大规模变量，主问题为整数规划，子问题生成列（可能为非线性优化）。 广义Benders分解 ： 将问题分解为主问题（整数变量）和子问题（连续变量），通过割平面传递非线性约束信息。 (2) 启发式与元启发式 遗传算法 ： 编码整数变量为染色体，通过选择、交叉、突变探索解空间，适应度函数处理非线性目标。 模拟退火 ： 以概率接受劣解跳出局部最优，降温策略控制搜索范围。 粒子群优化 ： 粒子位置对应整数解，速度更新引入离散化操作（如取整函数）。 (3) 凸化与线性化技术 二次整数规划 ： 对角化或特征值变换将目标函数转为凸二次型，再用分支定界求解。 分段线性逼近 ： 用分段线性函数拟合非线性函数（如对数函数），转化为混合整数线性规划。 4. 处理非凸性的特殊策略 有效不等式 ： 添加割平面（如Gomory割、凸包割）排除分数解，强化松弛问题的边界。 同伦方法 ： 构造参数化函数族，从易解问题连续变形至原问题，跟踪整数解路径。 多面体分析 ： 研究整数点的凸包结构，推导极值不等式（如对特定非线性问题的多面体刻画）。 5. 软件与求解器 ANTIGONE ： 全面处理非凸整数规划的全局优化器，结合分支定界与凸松弛。 BARON ： 基于分支约减的优化器，适用于多项式整数规划。 SCIP ： 支持约束整数规划，可集成用户自定义非线性约束处理器。 6. 当前研究前沿 机器学习辅助 ： 用神经网络预测分支变量选择，或学习问题特征以自适应调整算法参数。 多项式优化 ： 利用半定规划松弛层次（Lasserre层次）逼近全局解。 分布式计算 ： 分解大规模问题为子问题，并行求解并协调整数可行性。