Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints

Abstract

Redundancy identification techniques play an important role in improving the solvability of a linear program. In this paper, we address the redundancy in multi-dimensional knapsack constraints by proposing a new redundancy identification method. The proposed method is based on the constraint intercepts of Paulraj, Chellappan, and Natesan [A heuristic approach for identification of redundant constraints in linear programming models, Int. J. Comput. Math. 83 (2006), pp. 675–683] and surrogate constraints. In it, feasibility problems are constructed in order to determine the redundancy of the constraints, and are solved by a heuristic algorithm, which is developed to check the redundancy fast. The results of computational experiments show that the proposed method may be used in a preprocessing stage in order to reduce the number of knapsack constraints.

Keywords:

• linear program
• redundancy
• knapsack constraints
• surrogate constraints
• feasibility problems

2010 AMS Subject Classifications:

• 90C08
• 65K05

This work was supported in part by the National Research Foundation of Korea Grant funded by the Korean Government (KRF-2008-313-D01200).