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.
Original language | English |
---|---|
Pages (from-to) | 2470-2482 |
Number of pages | 13 |
Journal | International Journal of Computer Mathematics |
Volume | 91 |
Issue number | 12 |
DOIs | |
Publication status | Published - 2014 Dec 2 |
Bibliographical note
Funding Information:This work was supported in part by the National Research Foundation of Korea Grant funded by the Korean Government (KRF-2008-313-D01200).
Publisher Copyright:
© 2014, © 2014 Taylor & Francis.
Keywords
- feasibility problems
- knapsack constraints
- linear program
- redundancy
- surrogate constraints
ASJC Scopus subject areas
- Computer Science Applications
- Computational Theory and Mathematics
- Applied Mathematics