A cutting-plane generation method for a variable-capacity (0,1)-knapsack problem with general integer variables

A cutting-plane generation method for a variable-capacity (0,1)-knapsack problem with general integer variables

0.00 Avg rating0 Votes
Article ID: iaor20051946
Country: South Korea
Volume: 10
Issue: 1
Start Page Number: 97
End Page Number: 106
Publication Date: May 2004
Journal: International Journal of Management Science
Authors:
Keywords: knapsack problem
Abstract:

In this paper, we propose an effective cut generation method based on the Chvatal–Gomory procedure for a variable-capacity (0.1)-Knapsack problem with two general integer variables. We first derive a class of valid inequalities for the problem using Chvatal–Gomory procedure, then analyze the associated separation problem. Based on the results, we show that there exists a pseudo-polynomial time algorithm to solve the separation problem. By analyzing the theoretical strength of the inequalities which can be generated by the proposed cut generation method, we show that generated inequalities define facets under mild conditions. We also extend the result to the case in which a nontrivial upper bound is imposed on a general integer variable.

Reviews

Required fields are marked *. Your email address will not be published.