子供$i$が種類$j$の菓子を$x_{i, j}$個もらうとすると、与えられた問題は以下の条件で$\sum x_{i, j}$を最大化する問題と考えられる:
- $\sum_{j=1}^Nx_{i,j} \le C_i \qquad\forall i \in [M]$
- $\sum_{i=1}^Mx_{i, j} \le A_j \qquad \forall j \in [N]$
- $0 \le x_{i, j} \le B_i \qquad \forall i \in [M], \forall j \in [N]$
- $x_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$
ただし、$[M] = \{1, 2, ..., M\}, [N] = \{1, 2, ..., N\}$。実は4の整数制約は外してもよい。つまり、このILPの最適解はLP緩和の最適解にもなっている。以下はConfortiのInteger Programmingのp. 133を基にした説明。
定義: $m \times n$行列$A$の行を2つの集合$S$と$R$に分割する: $S \dot{\cup} R = [m]$。$S$の行ベクトルの総和 - $R$の行ベクトルの総和が$0, \pm 1$のみからなるベクトルであるとき、$S, R$を$A$の公平な行二彩色 (equitable row-bicoloring) と呼ぶ。
定理: 行列$A$が$0, \pm 1$のみからなり、各列の非ゼロ成分は高々2個であるとする。$A$が公平な行二彩色可能であれば、全ユニモジュラである。
上の制約の1, 2の係数行列について考えると、定理の条件を満たす（1の行と2の行に分割すれば公平になっている）ので全ユニモジュラである。
定理: $A$を$m \times n$整数行列とする。$A$が全ユニモジュラならば、任意の$l, u \in \mathbb Z^n, d \in \mathbb Z^m$について凸多面体$Q := \{x: Ax \le d, l \le x \le u\}$は整数多面体である、
この定理より上の制約1～3によって与えられる凸多面体は整数多面体なので、任意の目的関数について、（有界なら）最適解の少なくとも一つは整数解である。
従って、ILPに関しても強双対性が成り立つので、上のILPの最大値はLP双対の最小値に等しい。双対問題は以下の条件で$\sum_{i=1}^MC_ip_i + \sum_{j=1}^NA_jq_j+\sum_{i=1}^MB_i\sum_{j=1}^Nr_{i, j}$を最小化する問題である:
- $p_i + q_j + r_{i, j} \ge 1 \qquad \forall i \in [M], \forall j \in [N]$
- $p_i \ge 0, q_j \ge 0, r_{i, j} \ge 0 \qquad \forall i \in [M], \forall j \in [N]$
- $p_i, q_j, r_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$
双対問題を、$M \times N$のグリッドのいくつかの行と列を選択して覆うようなイメージで解釈した:
- 行と列の集合$S \subseteq [M], T \subseteq [N]$を任意に選ぶ。（$p_i=1$であるような$i$と$q_j=1$であるような$j$を選ぶ）
- $i \in S$についてコスト$C_i$を払う。
- $j \in T$についてコスト$A_j$を払う。
- $S$に含まれる行と$T$に含まれる列に覆われないすべてのマス$(i, j)$についてコスト$B_i$を払う。
最後の「覆われない」の部分の扱いが面倒に見えるので、さらに言い換える:
- 最初にコスト$N\sum_{i=1}^MB_i$を払っておく。
- $S \subseteq [M], T \subseteq [N]$を任意に選ぶ。$k=|T|$とする。
- $i \in S$についてコスト$C_i-(N-k)B_i$を払う。
- $j \in T$についてコスト$A_j-\sum_{i=1}^M B_i$を払う。
さて、$[N]$から$k$点選ぶと決めたときの最小コストについて考える。$S \in [M], T \in [N]$について$(N-k)\sum_{i=1}^MB_i + \sum_{i \in S}(C_i-(N-k)B_i)+\sum_{j \in T}A_j$が総コストである。$T$は$A_j$の小さいほうから$k$個取ればよく、$S$のほうは$C_i-(N-k)B_i < 0$であるものだけ取ればよい。$C_i-(N-k)B_i$は$k$が減少すると一点で正から負に切り替わる。具体的には$k \le \lfloor (NB_i-C_i)/B_i \rfloor$で0以下になる。したがって、この閾値を超えた$i$について$C_i$と$B_i$の総和を保持することにすれば$k$ごとに${O}(1)$で計算できる。$(A_i)$のソートが必要だから全体の計算量は${O}(N \log N + M)$。
LPの整数性について追記した。
