173
Views
3
CrossRef citations to date
0
Altmetric
Section A

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

&
Pages 2470-2482 | Received 11 Jun 2012, Accepted 14 Jan 2014, Published online: 27 Mar 2014
 

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.

2010 AMS Subject Classifications:

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.