最小矛盾の概念を用いた混合0-1整数計画問題の近似解法

概要

論文の詳細を見る
我々は、組合せ最適化に対して最小矛盾の概念を用いた近似解法の研究を行っており、すでにジョブショップスケジューリング問題および全0-1整数計画問題に対して適用した結果を報告をしている。本稿では、我々の方式を混合0-1整数計画問題に適用した結果について報告する。混合0-1整数計画問題は以下のように定式化される。[chemical formura]ここで、Aはm×n行列、Gはm×1行列、cは1×n行列、hは1×1行列、bはm×1行列である。混合0-1整数計画問題は、生産計画問題、配置問題、スケジューリング問題など多くの応用があり、重要な問題である。混合0-1整数計画問題に対する厳密な解法としては分枝限定法、切除平面法などがあるが、一般に混合0-1整数計画問題はNP-completeであり、問題の規模が大きくなると厳密に解くことは極めて難しくなる。このため、個別の問題ごとに各種の近似手法が開発されている。本論文では混合0-1整数計画問題一般に適用可能な汎用的な近似解法を提案する。
1992-09-28