混合整数非线性规划

混合整数非线性规划（mixed-integer nonlinear programming，MINLP）在同一个优化模型中使用整数决策和非线性目标或约束。例如，设备是否启用只能选零或一，启用后的产量却可以连续变化，偏离目标产量的损失又可能随偏差平方增长。

设有一条可选生产线，产量 $q$ 以吨计，启用变量 $z\in \{0,1\}$，产能为六吨。目标产量四吨，偏差平方的损失系数为一百元每平方吨，启用费为三百元。以下费用以百元计，模型为 $$\begin{array}{cc}min& (q-4{)}^2+3z,\\ 0& \le q\le 6z,\\ z& \in \{0,1\}.\end{array}$$ 约束 $q\le 6z$ 使停机时产量只能为零；它不要求开机后一定生产六吨，也不要求严格正产量。

固定整数后求连续最优

本例只有两个整数选择。若 $z=0$，只能 $q=0$，费用十六。若 $z=1$，连续子问题是在 $[0,6]$ 上最小化 $(q-4{)}^2+3$；平方项非负，在 $q=4$ 恰为零，费用为三。因此全局最优为开机生产四吨，费用三百元。这是完整的两分支全局比较，不是仅凭一个导数为零就宣告最优。

一般形式可写为 $$\begin{array}{cc}min& f(x,z),\\ g_i(x,z)& \le 0(i=1,\dots ,m),\\ h_j(x,z)& =0(j=1,\dots ,r),\\ x& \in {ℝ}^n,z\in {\mathbb{Z}}^p.\end{array}$$ 变量界可以另列，允许的整数也可只限零一。这里的“混合”指连续与离散变量同时参与，非线性可以出现在目标中，也可以出现在约束中。

连续松弛给出的下界

把本例的 $z$ 放宽到 $[0,1]$，对固定 $q$，应取最小可行的 $z=q/6$，因为其系数三为正。于是只需最小化 $$\begin{array}{cc}(q-4{)}^2+q/2& =(q-15/4{)}^2+31/16.\end{array}$$ 松弛解为 $q=15/4,z=5/8$，费用 $31/16=1.9375$。这个数低于整数模型的三，因为放宽后允许支付部分启用费；它是数学下界，不能解释成现实中启用了八分之五条生产线。

实线最低点给出真实开机分支；虚线允许分数启用，得到更低的松弛值。停机分支只有左上方那一个可行点。

最小化模型中，任意真正可行方案给上界，松弛的全局最优值给下界。因此本例有 $31/16\le z^{\ast }\le 3$；逐个求解两个整数分支后，两者的全局比较把最优值确定为三。若计算只找到非凸松弛中的一个局部极小值，它可能高于另一个区域的可行值，便不能直接作为全局下界。

凸性所处的位置

当目标与不等式左端为凸函数、等式为仿射，且连续变量域凸时，放松整数要求后的问题是凸优化；通常称这种结构为凸MINLP。原问题的整数可行集仍一般不凸。例如本例中，两个可行点 $(0,0)$ 与 $(4,1)$ 的中点不是整数可行点。

固定所有整数变量以后，凸结构保证连续子问题的局部极小值也是全局极小值。若出现非凸函数，这项保证就不再自动成立；分支算法需要能证明有效的全局下界，而不能把任意局部求解结果直接拿来剪枝。有限个整数选择也只保证组合数量有限，不会替代每个连续子问题本身的求解与可行性检查。

变式。 仅把启用费改成二十百元，关机费用仍为十六，开机分支的最低费用为二十，故最优变为停机。原先的开机结论依赖固定费与偏差损失的比较，而非“接近目标”这一句描述。

在复杂模型中，二元变量可表达工艺选择，非线性约束可表达压力、功率或几何关系。数值尺度仍须与单位一致；把偏差从吨改成千克而不同时修改平方项系数，会改变模型而不只是改变显示格式。