第3章　线性化方法

在实际问题的建模中，我们往往会遇到一些非线性的情形，例如二次表达式、取绝对值运算、取最小值/最大值（min/max）运算、分段线性函数等。这些非线性情形有时出现在约束条件中，有时出现在目标函数中，从而使模型成为非线性模型，给后续的模型求解带来了一定的挑战。不过，对于一些特定类型的非线性运算，可以使用特殊方法将其等价或转换为线性运算，从而使模型更便于求解。这些特殊方法就是本章要介绍的线性化方法。

线性化方法是数学规划建模中重要的技巧，该方法在降低模型的复杂度、为模型重构提供有利条件、加速模型求解等方面有重要的作用。对于一些包含特定形式的非线性目标函数或者非线性约束条件的数学规划模型，对其执行线性化的处理是非常有必要的。原因主要有以下几点：（1）线性规划的求解算法已经非常成熟，包括单纯形法、内点法等。目前，已经有多款数学规划求解器可以高效地求解线性规划问题。（2）整数线性规划问题的求解存在多种提速策略，包括列生成（Column Generation）算法、分支定价（Branch and Price）算法、Benders分解（Benders Decomposition）算法、Dantzig-Wolfe分解（Dantzig-Wolfe Decomposition）算法等。线性化后的模型有望使用上述加速算法进行高效求解。其他原因不再一一列举。

一般来讲，线性化方法的大体思想是：通过设置合适的目标函数、引入辅助决策变量或者辅助约束等方式，使得原有决策变量或者辅助决策变量的取值恰好等于预期的值。大家也可以在阅读本章内容的同时，细细体会这一点。

本章主要介绍整数规划建模中常用的线性化方法，包括乘积式（0-1变量乘0-1变量、0-1变量乘连续变量、0-1变量乘整数变量、整数变量乘整数变量等）、取整运算（向上取整和向下取整）、绝对值运算、min/max运算、分式函数、分段线性函数、平方根运算等的线性化。