2021年9月2日木曜日

ARC 126 E - Snack

子供iiが種類jjの菓子をxi,jx_{i, j}個もらうとすると、与えられた問題は以下の条件で∑xi,j\sum x_{i, j}を最大化する問題と考えられる:

  1. ∑j=1Nxi,j≤Ci∀i∈[M]\sum_{j=1}^Nx_{i,j} \le C_i \qquad\forall i \in [M]
  2. ∑i=1Mxi,j≤Aj∀j∈[N]\sum_{i=1}^Mx_{i, j} \le A_j \qquad \forall j \in [N]
  3. 0≤xi,j≤Bi∀i∈[M],∀j∈[N]0 \le x_{i, j} \le B_i \qquad \forall i \in [M], \forall j \in [N]
  4. xi,j∈Z∀i∈[M],∀j∈[N]x_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]

ただし、[M]={1,2,...,M},[N]={1,2,...,N}[M] = \{1, 2, ..., M\}, [N] = \{1, 2, ..., N\}。実は4の整数制約は外してもよい。つまり、このILPの最適解はLP緩和の最適解にもなっている。以下はConfortiのInteger Programmingのp. 133を基にした説明。

定義: m×nm \times n行列AAの行を2つの集合SSとRRに分割する: S∪˙R=[m]S \dot{\cup} R = [m]。SSの行ベクトルの総和 - RRの行ベクトルの総和が0,±10, \pm 1のみからなるベクトルであるとき、S,RS, RをAAの公平な行二彩色 (equitable row-bicoloring) と呼ぶ。

定理: 行列AAが0,±10, \pm 1のみからなり、各列の非ゼロ成分は高々2個であるとする。AAが公平な行二彩色可能であれば、全ユニモジュラである。

上の制約の1, 2の係数行列について考えると、1の行と2の行に分割すれば公平になっている定理の条件を満たし、全ユニモジュラである。

定理: AAをm×nm \times n整数行列とする。AAが全ユニモジュラならば、任意のl,u∈Zn,d∈Zml, u \in \mathbb Z^n, d \in \mathbb Z^mについて凸多面体Q:={x:Ax≤d,l≤x≤u}Q := \{x: Ax \le d, l \le x \le u\}は整数多面体である、

この定理より上の制約1～3によって与えられる凸多面体は整数多面体なので、任意の目的関数について（有界なら）最適解の少なくとも一つは整数解である。

従って、ILPに関する双対、つまり元の問題のLP緩和のLP双対に整数制約を課したものを考えると、これについても強双対性が成り立つ。双対問題は以下の条件で∑i=1MCipi+∑j=1NAjqj+∑i=1MBi∑j=1Nri,j\sum_{i=1}^MC_ip_i + \sum_{j=1}^NA_jq_j+\sum_{i=1}^MB_i\sum_{j=1}^Nr_{i, j}を最小化する問題である:

  • pi+qj+ri,j≥1∀i∈[M],∀j∈[N]p_i + q_j + r_{i, j} \ge 1 \qquad \forall i \in [M], \forall j \in [N]
  • pi≥0,qj≥0,ri,j≥0∀i∈[M],∀j∈[N]p_i \ge 0, q_j \ge 0, r_{i, j} \ge 0 \qquad \forall i \in [M], \forall j \in [N]
  • pi,qj,ri,j∈Z∀i∈[M],∀j∈[N]p_i, q_j, r_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]

双対問題を、M×NM \times Nのグリッドのいくつかの行と列を選択して覆うようなイメージで解釈した:

  • 行と列の集合S⊆[M],T⊆[N]S \subseteq [M], T \subseteq [N]を任意に選ぶ。言い換えると、pi=1p_i=1とするii、qj=1q_j=1とするjjを選ぶ。
  • i∈Si \in SについてコストCiC_iを払う。
  • j∈Tj \in TについてコストAjA_jを払う。
  • SSに含まれる行とTTに含まれる列に覆われないすべてのマス(i,j)(i, j)についてコストBiB_iを払う。

最後の「覆われない」の部分の扱いが面倒に見えるので、さらに言い換える:

  • 最初にコストN∑i=1MBiN\sum_{i=1}^MB_iを払っておく。
  • S⊆[M],T⊆[N]S \subseteq [M], T \subseteq [N]を任意に選ぶ。k=∣T∣k=|T|とする。
  • i∈Si \in SについてコストCi−(N−k)BiC_i-(N-k)B_iを払う。
  • j∈Tj \in TについてコストAj−∑i=1MBiA_j-\sum_{i=1}^M B_iを払う。

さて、[N][N]からkk点選ぶと決めたときの最小コストについて考える。S∈[M],T∈[N]S \in [M], T \in [N]について(N−k)∑i=1MBi+∑i∈S(Ci−(N−k)Bi)+∑j∈TAj(N-k)\sum_{i=1}^MB_i + \sum_{i \in S}(C_i-(N-k)B_i)+\sum_{j \in T}A_jが総コストである。TTはAjA_jの小さいほうからkk個取ればよく、SSのほうはCi−(N−k)Bi<0C_i-(N-k)B_i < 0であるものだけ取ればよい。Ci−(N−k)BiC_i-(N-k)B_iはkkが減少すると一点で正から負に切り替わる。具体的にはk≤⌊(NBi−Ci)/Bi⌋k \le \lfloor (NB_i-C_i)/B_i \rfloorで0以下になる。したがって、この閾値を超えたiiについてCiC_iとBiB_iの総和を保持することにすればkkごとにO(1){O}(1)で計算できる。(Ai)(A_i)のソートが必要だから全体の計算量はO(Nlog⁡N+M){O}(N \log N + M)。

LPの整数性について追記した。

投稿者