01 分数规划

在 x_i∈{0,1} 上最大化 Σa_i x_i / Σb_i x_i;参数化权值 a_i-λb_i,把比值判定化为 0/1 优化。

标签 数学 / 分数规划 / 01 分数规划 / 二分答案 / 最优化

定义

这是 分数规划 在 𝑥𝑖∈{0,1} 时的特例。设 𝑆⊆{0,1}𝑛,𝑏𝑖>0,且 𝑔(𝑥)>0。对

𝑓(𝑥)=∑𝑖=1𝑛𝑎𝑖𝑥𝑖,𝑔(𝑥)=∑𝑖=1𝑛𝑏𝑖𝑥𝑖,

求

𝜆∗=max𝑥∈𝑆𝑓(𝑥)𝑔(𝑥).

参数化判定

对 𝜆,令

𝐹(𝜆)=max𝑥∈𝑆∑𝑖=1𝑛(𝑎𝑖−𝜆𝑏𝑖)𝑥𝑖.

分数规划的判定给出

𝐹(𝜆)≥0当且仅当𝜆≤𝜆∗.

因此二分 𝜆 时,每次只需解一个以 𝑎𝑖−𝜆𝑏𝑖 为权值的 0/1 优化问题。

无其他约束

若 𝑆={𝑥∈{0,1}𝑛:𝑔(𝑥)>0},则 𝑥𝑖 可逐项选取。记 𝑑𝑖=𝑎𝑖−𝜆𝑏𝑖。若存在 𝑑𝑖>0,取所有这样的项;否则取 𝑑𝑖 最大的一项。于是

𝐹(𝜆)={∑𝑖:𝑑𝑖>0𝑑𝑖存在正项max𝑖𝑑𝑖否则

后一支至少选一项,保证 𝑔(𝑥)>0。

带组合约束

若 𝑆 还带有其他约束,𝐹(𝜆) 就是权值为 𝑑𝑖 的 0/1 优化问题。约束不同,判定算法也不同;例如 𝑆 为生成树时,判定是带参数边权的最小生成树,见 Earthquake。

常见误解

  • 无约束时只取正项;若所有 𝑑𝑖≤0,空集不满足 𝑔(𝑥)>0,必须至少选一项。
  • 忽略 𝑏𝑖>0:分母可能为零,𝑔(𝑥)>0 的可行域需要单独处理。
  • 认为一次排序可以复用:权值 𝑑𝑖 随 𝜆 改变,每次判定都要按当前 𝜆 重新比较。
  • 把 𝐹(𝜆)≥0 当成最终答案:它只说明存在比值不低于 𝜆 的 01 向量。
  • 把 01 分数规划直接当成 01 背包:背包只是约束 𝑆 的一种;判定时物品价值变为 𝑑𝑖。
源码位置