情報処理学会 第86回全国大会 会期:2024年3月15日~17日

6K-07
0-1整数線形計画問題の実行可能解を列挙するZDDの生成法とその評価
○吉  浩,川原 純,湊 真一(京大)
線形計画問題は、複数の線形不等式をすべて充足しながらコスト関数を最適化する問題である。0-1整数線形計画問題は、変数値が0, 1の組合せに制約された線形計画問題である。湊らはZDD (Zero-suppressed Binary Decision Diagram) で与えられた実行可能解の集合に対して、コスト制約解を表すZDDを高速に抽出する方法を2022年に提案している。0-1整数線形計画問題の実行可能解は、不等式の制約式をコスト制約とみなして湊らの方法を繰り返し適用することで、最終的なZDDを生成することができる。ただし、この生成プロセスではZDDの変数展開順序と制約不等式の適用順序が ZDD 生成の時間に大きく影響する。本研究では、この生成プロセスにおける効率的な順序付け方法の提案とその評価を行う。