半正定値計画の組み合わせ最適化問題への応用

点击翻译按钮获取中文摘要

本年度に計画した研究目標は以下の通りであった.1.一般的な半正定値計画問題に対して開発した主双対内点法のプログラム計算効率を高める.2.0-1整数計画問題の数値解法の主要部分を構成する予定の半正定値計による緩和について,より効果のある緩和について模索する.3.半正定値計画による緩和と既存の手法である切除平面法または分枝限定組み合わせについて研究する.研究目標1に関しては,組合せ最適化問題から生ずる過疎で大規模な半定値計画問題を高速に解けるように,プログラムの改訂を行い,そのさまざまな組合せ最適化問題から生ずる半正定値計画問題に適用しその有効性を検証した.また,この段階で目標2に関しての計算実験もあわせて行った.プログラムをインターネットを通して公開した.目標1に関しては最初に計画した以上の成果をあげた.しかしながら,目標1の達成に時間がかかり,目標3に関する研究はあまり進まなかった.この主たる理由は目標2および3に関する研究の中途で,より大規模な半正定値計画問題を解くためのソフトウエアが必要であることが判明し,主双対内点法のより大幅な改定が必要になったためである.