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.
Yan, Xiao-Qing (1995). Solving mixed 0-1 knapsack problems using Fenchel cutting planes. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1995 -THESIS -Y36.