Computer Science

Finding the best combination within budget

- Combinatorial optimization using binary decision diagram -

Abstract

Knapsack problem (KP) is one of the fundamental combinatorial optimization problems, and covers a wide range of practical problems such as text summarization, bin packing, and network design. The general solution of KP cannot simply handle additional constraints like “we do not want to include some combination of items in the solution”, which is often required in actual use. To tackle this inconvenience, we have developed a general methodology for solving constraint-added variants of KP. The key to our method is Zero-suppressed Binary Decision Diagram (ZDD). ZDD can represent a set of feasible solutions as a compact graph, and it can efficiently guide the solver to find the best solution of the constraint-added variants of KP. Our methodology will impact many real applications.

Photos

Poster


Please click the thumbnail image to open the full-size PDF file.

Presenters

Masaaki Nishino
Masaaki Nishino
Innovative Communication Laboratory
Tsutomu Hirao
Tsutomu Hirao
Innovative Communication Laboratory
Yasuhisa Yoshida
Yasuhisa Yoshida
Innovative Communication Laboratory