整数规划算法最小化或最大化受等式、不等式和整数约束的函数。整数约束限制优化问题中的部分或全部变量只取整数值。这使得对涉及离散数量(如股票份额)或是非决策的问题进行精确建模成为可能。当只有一些变量有整数约束时,这个问题被称为混合整数程序(MIP)。示例整数规划问题包括投资组合优化在金融领域,能源生产中发电机组的优化调度(机组组合),设计优化工程、运输和供应链应用中的调度和路线。
整数规划是寻找使函数最小化的向量\(x\)的数学问题:
\[\min\u x f(x)\]
受以下限制:
\[begin{eqnarray}g(x) \leq 0 & \quad & \text{(不等式约束)}\\h(x) = 0 & \quad & \text{(等式约束)}\\ x_i \in \mathbb{Z} & \quad & text{(整数约束)}\end{eqnarray}\]
这是整数规划的最一般形式,称为混合整数非线性规划(MINLP)。
许多问题只能用线性目标和约束来描述。在这种情况下,整数规划称为混合整数线性规划(MILP),其编写方式如下:
\[\min{x}\left\{f^{\mathsf{T}}x\right\}\]
受以下限制:
\[\begin{eqnarray}Ax\leq b&\quad&\text{(不等式约束)}\\A{eq}x=b{eq}&\quad&\text{(等式约束)}\\lb\leq x\leq ub&\quad&\text{(绑定约束)}\\x\u i\in\mathbb{Z}&\quad&\text{(整数约束)}\end{eqnarray}]