预置示例
5个元素须被选中的集合覆盖，最小化总费用
问题参数
问题形式
min3F₁ + 2F₂ + 4F₃ + 2F₄ + 3F₅
s.t.F₁ + F₂ ≥ 1（覆盖 e1）
s.t.F₂ + F₃ ≥ 1（覆盖 e2）
s.t.F₁ + F₃ + F₅ ≥ 1（覆盖 e3）
s.t.F₄ + F₅ ≥ 1（覆盖 e4）
s.t.F₂ + F₄ ≥ 1（覆盖 e5）
s.t.F₁, F₂, F₃, F₄, F₅ ∈ { 0, 1 }
| 元素 \ 集合 | F₁ | F₂ | F₃ | F₄ | F₅ |
|---|---|---|---|---|---|
| e1 | ✓ | ✓ | · | · | · |
| e2 | · | ✓ | ✓ | · | · |
| e3 | ✓ | · | ✓ | · | ✓ |
| e4 | · | · | · | ✓ | ✓ |
| e5 | · | ✓ | · | ✓ | · |
| 费用 c | 3 | 2 | 4 | 2 | 3 |
最优覆盖
最优费用
5.00
选用集合数
2
选用：F₂，F₅
覆盖矩阵
| 元素↓ 集合→ | F₁ | F₂ | F₃ | F₄ | F₅ |
|---|---|---|---|---|---|
| e1 | 1 | 1 | 0 | 0 | 0 |
| e2 | 0 | 1 | 1 | 0 | 0 |
| e3 | 1 | 0 | 1 | 0 | 1 |
| e4 | 0 | 0 | 0 | 1 | 1 |
| e5 | 0 | 1 | 0 | 1 | 0 |
| 费用 | 3 | 2 | 4 | 2 | 3 |
步骤 1 / 6
集合覆盖割平面算法（§11.5）。集合数: 5，元素数: 5
16
速度:
步骤日志
1.集合覆盖割平面算法（§11.5）。集合数: 5，元素数: 5
2.初始贪婪覆盖 J = {F₁,F₂,F₄}: 目标值 = 7
3.第 1 轮 LP 松弛：目标值 = 7，所有变量为整数
4.LP 松弛解已为整数，覆盖问题最优解！目标值 = 7
5.小规模精确校验更新最优覆盖，目标值 = 5。
6.算法完成。最优覆盖：{F₂, F₅}，总费用 = 5