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

Jiwoong Choi, In Chan Choi

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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 languageEnglish
Pages (from-to)2470-2482
Number of pages13
JournalInternational Journal of Computer Mathematics
Issue number12
Publication statusPublished - 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.


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

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints'. Together they form a unique fingerprint.

Cite this