改良代理制約法による乲列化計算

摘要

代理双村ギャップをもつ大規模な多制約rn分離形離散最適化問題（多次元非線形ナップサックrn問題）を厳密かつ効率良く解く改良代理制約法（ISCrn法）［5］が提案された．また，多次元非線形ナップサッrnク問題の問題困難度を推定するための方法［7］が提案rnされた．この推定法を用いて大規模で計算困難な最適rn化問題を計算可能な複数の問題に分割することが可能rnであり，ISC法の並列処理アルゴリズムと組み合わせrnることで，より高速に最適解を得ることが期待される．rnしかしながら，並列計算のために混合整数計画問題rnを有効に分割することが簡単でないというRalphs［6］rnの指摘の中にあるように，実際に並列計算を行うにはrn問題の困難度推定・問題分割処理を適切に行わなけれrnばならず，通信速度や同期通信のオーバヘッドも十分rn考慮しなければならない．本論文では，非同期ネットrnワークによる並列計算のシミュレーションを行い，ISCrn法を利用した並列計算が高いパフォーマンスを示すとrnいう実験結果が得られたことを報告する．