整数规划

整数规划算法最小化或最大化一个函数受等式、不等式和整数约束。整数约束限制优化问题中的部分或全部变量只能取整数值。这使得涉及离散量(如股票份额或电池中的电池单元)或是或否决策的问题能够精确建模。当只有一些变量有整数约束时，这个问题被称为混合整数程序(MIP)。示例整数规划问题包括投资组合优化在金融领域,发电机组优化调度(单位承诺)优化设计以及运输和供应链应用中的调度和路由。

整数规划是寻找一个向量\(x\)使函数最小化的数学问题:

\ [\ min_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} \左\ {f ^ {\ mathsf {T}} x \ \} \]

受以下限制:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(不等式约束)}\\A_{eq}x = b_{eq} & \quad & \text{(等式约束)}\\lb \leq x \leq ub & \quad & \text{(绑定约束)}\\ x_i \in \mathbb{Z} & \quad & \text{(整数约束)}\end{eqnarray}\]

混合整数线性规划MATLAB

整数规划算法可以在软件中实现，例如MATLAB^®．求解milp通常需要使用多种技术的组合来缩小解空间，找到整数可行解，并丢弃解空间中不包含更好的整数可行解的部分。整数编程的常见技术包括:

• 减少飞机:在问题中添加额外的约束以减少搜索空间。
• 启发式:寻找整数可行解。
• 分支和界:系统地寻找最优解。算法求解线性规划整数变量可能值的限制范围的松弛。

的MILP解算器在优化工具箱™实现这些技术。

混合整数非线性规划MATLAB

一些minlp可以通过将这些整数规划技术应用于非线性函数或线性化非线性函数并求解一系列milp来求解。当非线性函数只能在积分点处求值时，就需要采用其他方法。中实现了两种适用于这类整数程序的算法全局优化工具箱．

• 遗传算法:模拟一个自然选择过程，重复修改个体解的种群，这些解被限制为整数值。
• 代理优化:自动建立可松弛问题的代理模型，然后通过MILP技术对MINLP的适应来解决。

有关整数规划的更多信息，请参见优化工具箱而且全局优化工具箱．