High-speed decision method of combination of risk-reducing plans using Branch and Bound
Keisuke Kawaratani, Kouta Itakura, Masaki Samejima, Masanori Akiyoshi · 2010
This paper addresses a problem to decide the combination of risk-reducing plans quickly. The combinatorial problem is formulated as one of the 0–1 integer programming and Branch and Bound is applied. On Branch and Bound, Simplex method for deciding a branching variable and the lower bound, which takes much time. Therefore, we propose the high-speed decision reducing calculations of a combination using Branch and Bound. The proposed method decides the combination quickly based on approximate solutions by greedy algorithm instead of solutions by Simplex method. In order to derive the optimal combination with certainty, when nodes are bounded with the approximate solutions, the validity of the bounding is confirmed by Simplex method. As a result of evaluation experiments, the proposed method can reduce the computational time by 65% in comparison with the existing method.