运筹学 $3 整数线性规划_c++ 整数线性规划ilp代码

作者：喵喵爱编程 | 2024-07-16 11:45:20

踩

c++ 整数线性规划ilp代码

§2 整数线性规划

整数规划ILP：含有整数约束条件 $x_i \in Z^*$

1）分支定界法：隐枚举的一种，枚举过程中发生剪枝

2）应用于整数规划：

通过非整数规划确定一个初始分支
假设当前分支中某变量 $x_k = a$ （非整数）

则产生的两个子分支分别是非整数规划问题添加约束 $x_k\le \lfloor a\rfloor,x_k\ge \lceil a\rceil$
分支的决策上界是非整数规划下最优值
分支的决策下界是已知的某个可行整数解的最优值，初始为-M

思想：利用割平面切割可行域使得其某个整数顶点是最优解
实现：
- 令 $x_i$ 是求解非线性规划问题最优解的一个分数基变量，由单纯形表最终表
  
  $x_i + \sum\limits_k a_{ik}x_k = b_i(x_k\in X_N)$
- 分解 $b_i,a_{ik}$ 为带分数 $b_i = N_i+f_i;a_{ik} = N_{ik}+f_{ik},f\in[0,1)$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/833926