- 集合分割問題の近似解法に、列生成法があります。これは、まず集合分割問題の中の変数xiを実数に変えた線形緩和問題が多項式時間で解けることを利用します。さらにcomplementary slackness conditionという最適解についての、dual potentialから定義されるreduced costに関する条件を利用します。
- まず全候補の中の一部のみから変数xの列を作り、その列について線形緩和問題を解き、その最適解のdual potentialから列に入れていない変数に関するreduced costを計算し、その値が負のものから、一部を新たに列に加えていきます。この操作を線形緩和問題の解が収束するまで続けます。そして収束した時の列について、集合分割問題を解きます。
|
