×

Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints. (English) Zbl 1309.90052

Summary: 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 S. Paulraj et al. [Int. J. Comput. Math. 83, No. 8–9, 675–683 (2006; Zbl 1128.90040)] 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.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
65K05 Numerical mathematical programming methods

Citations:

Zbl 1128.90040

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen E.D., Math. Program 71 pp 221– (1995)
[2] DOI: 10.1016/j.ejor.2006.02.058 · Zbl 1138.90015 · doi:10.1016/j.ejor.2006.02.058
[3] DOI: 10.1007/s10479-008-0415-1 · Zbl 1163.90526 · doi:10.1007/s10479-008-0415-1
[4] DOI: 10.1007/BF01580428 · Zbl 0317.90037 · doi:10.1007/BF01580428
[5] DOI: 10.1109/TPWRS.2009.2033931 · doi:10.1109/TPWRS.2009.2033931
[6] DOI: 10.1023/A:1009642405419 · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[7] DOI: 10.1007/BF02568605 · Zbl 0855.90091 · doi:10.1007/BF02568605
[8] DOI: 10.1016/S0377-2217(03)00274-1 · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[9] DOI: 10.1016/0166-218X(94)90209-7 · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[10] Fréville A., Investig. Oper 1 pp 251– (1990)
[11] DOI: 10.1016/0377-2217(86)90042-1 · Zbl 0579.90066 · doi:10.1016/0377-2217(86)90042-1
[12] DOI: 10.1007/BF00247210 · Zbl 0870.90084 · doi:10.1007/BF00247210
[13] DOI: 10.1287/opre.13.6.879 · Zbl 0163.41301 · doi:10.1287/opre.13.6.879
[14] DOI: 10.1111/j.1540-5915.1977.tb01074.x · doi:10.1111/j.1540-5915.1977.tb01074.x
[15] DOI: 10.1287/ijoc.9.1.73 · Zbl 0890.90143 · doi:10.1287/ijoc.9.1.73
[16] Gurobi 5.5.0, Gurobi Optimization
[17] DOI: 10.1016/S0377-2217(97)00296-8 · Zbl 0991.90089 · doi:10.1016/S0377-2217(97)00296-8
[18] DOI: 10.1007/978-3-642-45535-3 · doi:10.1007/978-3-642-45535-3
[19] Veni K.K., World Acad. Sci. Eng. Technol 43 pp 538– (2010)
[20] DOI: 10.1090/psapm/015/0161746 · doi:10.1090/psapm/015/0161746
[21] DOI: 10.1287/opre.21.1.247 · Zbl 0265.90024 · doi:10.1287/opre.21.1.247
[22] DOI: 10.1007/s00291-003-0130-x · Zbl 1042.90031 · doi:10.1007/s00291-003-0130-x
[23] G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization, Wiley-Interscience, New York, 1999. · Zbl 0944.90001
[24] DOI: 10.1080/00207160601014148 · Zbl 1128.90040 · doi:10.1080/00207160601014148
[25] Paulraj S., Math. Probl. Eng (2010)
[26] DOI: 10.1287/ijoc.1090.0344 · Zbl 1243.90190 · doi:10.1287/ijoc.1090.0344
[27] DOI: 10.1016/S0377-2217(00)00083-7 · Zbl 0991.90087 · doi:10.1016/S0377-2217(00)00083-7
[28] DOI: 10.1287/mnsc.29.10.1209 · Zbl 0527.90066 · doi:10.1287/mnsc.29.10.1209
[29] DOI: 10.1016/0167-6377(86)90093-3 · Zbl 0621.65058 · doi:10.1016/0167-6377(86)90093-3
[30] DOI: 10.1016/j.ejor.2004.01.024 · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[31] DOI: 10.1016/j.ejor.2008.11.036 · Zbl 1176.90669 · doi:10.1016/j.ejor.2008.11.036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.