整数线性规划分支定界法交互演示器

以二维整数线性规划为例，逐步展示“LP 松弛 → 上界 → 分支 → 剪枝 → 更新 incumbent”的全过程。支持自定义目标函数与线性约束。

算法控制及实时状态

当前步骤

0 / 0

当前最优整数解

—

活节点数量

当前关注节点

准备就绪。点击“下一步”开始观察根节点的 LP 松弛。

可视化工作区

左：LP 松弛几何区域；右：分支定界搜索树

LP 松弛与当前节点区域N0

根松弛区域当前节点区域分支约束整数点/Incumbent

分支定界树点击节点可查看对应松弛区域

待处理已分支整数剪枝剪枝当前步骤

节点列表

按搜索树生成顺序排列

模型设置

目标函数系数 c₁, c₂：max c₁x + c₂y

节点选择与分支规则

约束：每行写 “a b <= rhs”，自动附加 x ≥ 0, y ≥ 0, x,y 为整数

当前演示器聚焦二维 ILP。为了便于画图与枚举 LP 顶点，约束统一按 ≤ 输入。

算法流程

高亮对应当前步骤

1. 将整数约束 x,y∈Z 暂时去掉，建立根节点 LP 松弛。

2. 从活节点表中选择一个节点。

3. 求该节点 LP 松弛，得到上界 UB 与松弛解 x*。

4. 若 LP 不可行，则不可行剪枝。

5. 若 UB ≤ 当前 incumbent，则界剪枝。

6. 若 x* 已为整数，则更新 incumbent 并整数剪枝。

7. 否则选一个分量做分支：v ≤ ⌊v*⌋ 与 v ≥ ⌈v*⌉。

8. 重复直到没有活节点，incumbent 即为最优整数解。

当前节点说明