集合覆盖割平面法

0-1 集合覆盖问题的割平面算法。包含化简规则(行支配删除、单元素行固定变量)与覆盖不等式生成。

预置示例

5个元素须被选中的集合覆盖,最小化总费用

问题参数
问题形式
min3F₁ + 2F₂ + 4F₃ + 2F₄ + 3F₅
s.t.F₁ + F₂ ≥ 1(覆盖 e1)
F₂ + F₃ ≥ 1(覆盖 e2)
F₁ + F₃ + F₅ ≥ 1(覆盖 e3)
F₄ + F₅ ≥ 1(覆盖 e4)
F₂ + F₄ ≥ 1(覆盖 e5)
F₁, F₂, F₃, F₄, F₅ ∈ { 0, 1 }
元素 \ 集合F₁F₂F₃F₄F₅
e1✓✓···
e2·✓✓··
e3✓·✓·✓
e4···✓✓
e5·✓·✓·
费用 c32423
最优覆盖
最优费用
5.00
选用集合数
2
选用:F₂,F₅
覆盖矩阵
元素↓ 集合→F₁F₂F₃F₄F₅
e111000
e201100
e310101
e400011
e501010
费用32423
步骤 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