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

REFERENCES

• E.D. Andersen and K.D. Andersen, Presolving in linear programming, Math. Program. 71 (1995), pp. 221–245.
   Web of Science ®Google Scholar
• S. Balev, N. Yanev, A. Fréville, and R. Andonov, A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem, European J. Oper. Res. 186 (2008), pp. 63–76. doi: 10.1016/j.ejor.2006.02.058
   Web of Science ®Google Scholar
• C. Beltran-Royo, The radar method: An effective line search for piecewise linear concave functions, Ann. Oper. Res. 166 (2009), pp. 299–312. doi: 10.1007/s10479-008-0415-1
   Web of Science ®Google Scholar
• A.L. Brearley, G. Mitra, and H.P. Williams, Analysis of mathematical programming problems prior to applying the simplex algorithm, Math. Program. 8 (1975), pp. 54–83. doi: 10.1007/BF01580428
   Web of Science ®Google Scholar
• D.J. Burke and M.J. O'Malley, Maximizing firm wind connection to security constrained transmission networks, IEEE Trans. Power Syst. 25 (2010), pp. 749–759. doi: 10.1109/TPWRS.2009.2033931
   Web of Science ®Google Scholar
• P.C. Chu and J.E. Beasley, A genetic algorithm for the multidimensional knapsack problem, J. Heuristics 4 (1998), pp. 63–86. doi: 10.1023/A:1009642405419
   Web of Science ®Google Scholar
• L.F. Escudero, A. Garín, and G. Pérez, On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, Top 4 (1996), pp. 87–98. doi: 10.1007/BF02568605
   Google Scholar
• A. Fréville, The multidimensional 0-1 knapsack problem: An overview, European J. Oper. Res. 155 (2004), pp. 1–21. doi: 10.1016/S0377-2217(03)00274-1
   Web of Science ®Google Scholar
• A. Fréville and G. Plateau, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Discrete Appl. Math. 49 (1994), pp. 189–212. doi: 10.1016/0166-218X(94)90209-7
   Web of Science ®Google Scholar
• A. Fréville and G. Plateau, Hard 0-1 multiknapsack test problems for size reduction methods, Investig. Oper. 1 (1990), pp. 251–270.
   Google Scholar
• A. Fréville and G. Plateau, Heuristics and reduction methods for multiple constraints 0–1 linear programming problems, European J. Oper. Res. 24 (1986), pp. 206–215. doi: 10.1016/0377-2217(86)90042-1
   Web of Science ®Google Scholar
• A. Fréville and G. Plateau, The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool, J. Heuristics 2 (1996), pp. 147–167. doi: 10.1007/BF00247210
   Google Scholar
• F. Glover, A multiphase-dual algorithm for the zero-one integer programming problem, Oper. Res. 13 (1965), pp. 879–919. doi: 10.1287/opre.13.6.879
   Web of Science ®Google Scholar
• F. Glover, Heuristics for integer programming using surrogate constraints, Decis. Sci. 8 (1977), pp. 156–166. doi: 10.1111/j.1540-5915.1977.tb01074.x
   Google Scholar
• J. Gondzio, Presolve analysis of linear programs prior to applying an interior point method, INFORMS J. Comput. 9 (1997), pp. 73–91. doi: 10.1287/ijoc.9.1.73
   Google Scholar
• Gurobi 5.5.0, Gurobi Optimization, USA. Available at http://www.gurobi.com.
   Google Scholar
• S. Hanafi and A. Freville, An efficient tabu search approach for the 0-1 multidimensional knapsack problem, European J. Oper. Res. 106 (1998), pp. 659–675. doi: 10.1016/S0377-2217(97)00296-8
   Web of Science ®Google Scholar
• M.H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Redundancy in Mathematical Programming: A State-of-the-Art Survey, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, 1983.
   Google Scholar
• K.K. Veni and S.R. Balachandar, A new heuristic approach for large size zero-one multi knapsack problem using intercept matrix, World Acad. Sci. Eng. Technol. 43 (2010), pp. 538–542.
   Google Scholar
• H.W. Kuhn and R.E. Quandt, An experimental study of the simplex method, Proc. Sympos. Appl. Math. 15 (1963), pp. 107–124. doi: 10.1090/psapm/015/0161746
   Google Scholar
• T.H. Mattheiss, An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Oper. Res. 21 (1973), pp. 247–260. doi: 10.1287/opre.21.1.247
   Web of Science ®Google Scholar
• C. Mészáros and U.H. Suhl, Advanced preprocessing techniques for linear and quadratic programming, OR Spectrum 25 (2003), pp. 575–595. doi: 10.1007/s00291-003-0130-x
   Web of Science ®Google Scholar
• G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience, New York, 1999.
   Google Scholar
• S. Paulraj, C. Chellappan, and T.R. Natesan, A heuristic approach for identification of redundant constraints in linear programming models, Int. J. Comput. Math. 83 (2006), pp. 675–683. doi: 10.1080/00207160601014148
   Web of Science ®Google Scholar
• S. Paulraj and P. Sumathi, A comparative study of redundant constraints identification methods in linear programming problems, Math. Probl. Eng. 2010 (2010), Article ID 723402, 16 pp.
   Web of Science ®Google Scholar
• J. Puchinger, G.R. Raidl, and U. Pferschy, The multidimensional knapsack problem: Structure and algorithms, INFORMS J. Comput. 22 (2010), pp. 250–265. doi: 10.1287/ijoc.1090.0344
   Web of Science ®Google Scholar
• N.V. Stojkovíc and P.S. Stanimirovíc, Two direct methods in linear programming, European J. Oper. Res. 131 (2001), pp. 417–439. doi: 10.1016/S0377-2217(00)00083-7
   Web of Science ®Google Scholar
• J. Telgen, Identifying redundant constraints and implicit equalities in systems of linear constraints, Manage. Sci. 29 (1983), pp. 1209–1222. doi: 10.1287/mnsc.29.10.1209
   Web of Science ®Google Scholar
• L.A. Tomlin and J.S. Welch, Finding duplicate rows in a linear programming model, Oper. Res. Lett. 5 (1986), pp. 7–11. doi: 10.1016/0167-6377(86)90093-3
   Web of Science ®Google Scholar
• M. Vasquez and Y. Vimont, Improved results on the 0-1 multidimensional knapsack problem, European J. Oper. Res. 165 (2005), pp. 70–81. doi: 10.1016/j.ejor.2004.01.024
   Web of Science ®Google Scholar
• C. Wilbaut, S. Salhi, and S. Hanafi, An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem, European J. Oper. Res. 199 (2009), pp. 339–348. doi: 10.1016/j.ejor.2008.11.036
   Web of Science ®Google Scholar