Finding the best combination within budget

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.

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