Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints
- Authors
- Choi, Jiwoong; Choi, In-Chan
- Issue Date
- 2-12월-2014
- Publisher
- TAYLOR & FRANCIS LTD
- Keywords
- redundancy; linear program; surrogate constraints; knapsack constraints; feasibility problems; 65K05; 90C08
- Citation
- INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, v.91, no.12, pp.2470 - 2482
- Indexed
- SCIE
SCOPUS
- Journal Title
- INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
- Volume
- 91
- Number
- 12
- Start Page
- 2470
- End Page
- 2482
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/96538
- DOI
- 10.1080/00207160.2014.885020
- ISSN
- 0020-7160
- 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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - College of Engineering > School of Industrial and Management Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.