Solving mixed 0-1 knapsack problems using Fenchel cutting planes

Abstract

Cutting-plane methods have shown their unique advantage in solving IP problems. In this research, a new algorithm (MIXCUT) is developed to generate the cutting planes for mixed 0-1 knapsack problems. The class of the cutting planes is called Fenchel cuts. They are generated by solving a separation problem instead of using explicit knowledge of the polyhedral structure of the IP problem. Dynamic programming and variable separation are two main techniques used to generate Fenchel cuts. Once a Fenchel cut is generated, a mixed 0-1 knapsack problem can be solved by using MIXCUT algorithm iteratively. A major advantage of the algorithm is that a mixed 0-1 knapsack problem can be solved without any knowledge of the polyhedral facial structure of the problem. Our test results demonstrated the expected good performance of the algorithm.