第14章・第14回 組み合わせ最適化法
- 概要
-
組み合わせ最適化問題とは、条件を満たす変数の組み合わせの中で最適なものを求める問題である。組み合わせ最適化問題は実世界にあふれている。その多くは解くための計算量が莫大になり、素朴な探索では解くことができないが、様々な工夫が施され、年々規模の大きな問題を解くことができるようになっている。代表的な組み合わせ最適化問題と解法について解説する。
【キーワード】
組み合わせ最適化問題，分枝限定法，欲張り法，動的計画法
- 放送授業パタン，台本（字幕代りにどうぞ）
-
- Excelソルバーによる整数最適化法
- ナップサック問題
- R (lpSolveパッケージ)による整数最適化法
- ナップサック問題
- GLPKによる整数最適化法
- ナップサック問題
- プログラム
/* Knapsack Problem */
var x1, binary;
var x2, binary;
var x3, binary;
maximize z: 6*x1 + 3*x2 + 4*x3;
s.t. CAPACITY: 4*x1 + 3*x2 + 6*x3 <= 9;
end;
- 出力
Problem: KP
Rows: 2
Columns: 3 (3 integer, 3 binary)
Non-zeros: 6
Status: INTEGER OPTIMAL
Objective: z = 9 (MAXimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 z 9
2 CAPACITY 7 9
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x1 * 1 0 1
2 x2 * 1 0 1
3 x3 * 0 0 1
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+000 on row 0
max.rel.err = 0.00e+000 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+000 on row 0
max.rel.err = 0.00e+000 on row 0
High quality
End of output
- 最小木問題
- プログラム
/* Minimum Spanning Tree Problem */
var x12, binary;
var x13, binary;
var x14, binary;
var x15, binary;
var x23, binary;
var x24, binary;
var x25, binary;
var x34, binary;
var x35, binary;
var x45, binary;
minimize z: x12 + 4*x13 + 5*x14 + 3*x15 + 2*x23 + 6*x24 + 7*x45;
s.t. SPANNING: x12 + x13 + x14 + x15 + x23 + x24 + x45 = 4;
s.t. Loop_3_1: x12 + x13 + x14 + x23 + x24 + x34 <= 3;
s.t. Loop_3_2: x12 + x13 + x15 + x23 + x25 + x35 <= 3;
s.t. Loop_3_3: x12 + x14 + x15 + x24 + x25 + x45 <= 3;
s.t. Loop_3_4: x13 + x14 + x15 + x34 + x35 + x45 <= 3;
s.t. Loop_3_5: x23 + x24 + x25 + x34 + x35 + x45 <= 3;
s.t. Loop_2_1: x12 + x13 + x23 <= 2;
s.t. Loop_2_2: x12 + x14 + x24 <= 2;
s.t. Loop_2_3: x13 + x14 + x34 <= 2;
s.t. Loop_2_4: x23 + x24 + x34 <= 2;
s.t. Loop_2_5: x12 + x15 + x25 <= 2;
s.t. Loop_2_6: x13 + x15 + x35 <= 2;
s.t. Loop_2_7: x23 + x25 + x35 <= 2;
s.t. Loop_2_8: x14 + x15 + x45 <= 2;
s.t. Loop_2_9: x24 + x25 + x45 <= 2;
s.t. Loop_2_10: x34 + x35 + x45 <= 2;
end;
- 出力
Problem: minSpanningTree
Rows: 17
Columns: 10 (10 integer, 10 binary)
Non-zeros: 74
Status: INTEGER OPTIMAL
Objective: z = 11 (MINimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 z 11
2 SPANNING 4 4 =
3 Loop_3_1 3 3
4 Loop_3_2 3 3
5 Loop_3_3 3 3
6 Loop_3_4 2 3
7 Loop_3_5 1 3
8 Loop_2_1 2 2
9 Loop_2_2 2 2
10 Loop_2_3 1 2
11 Loop_2_4 1 2
12 Loop_2_5 2 2
13 Loop_2_6 1 2
14 Loop_2_7 1 2
15 Loop_2_8 2 2
16 Loop_2_9 0 2
17 Loop_2_10 0 2
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x12 * 1 0 1
2 x13 * 0 0 1
3 x14 * 1 0 1
4 x15 * 1 0 1
5 x23 * 1 0 1
6 x24 * 0 0 1
7 x25 * 0 0 1
8 x34 * 0 0 1
9 x35 * 0 0 1
10 x45 * 0 0 1
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+000 on row 0
max.rel.err = 0.00e+000 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+000 on row 0
max.rel.err = 0.00e+000 on row 0
High quality
End of output