The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance

References

• Amini M. M., Racer M. A rigorous computational comparison of alternative solution methods for the generalized assignment problem. Management Sci. (1994) 40(7):868–890Link, Google Scholar
• Balas E., Martin C. H. Pivot and complement—A heuristic for 0–1 programming. Management Sci. (1980) 26(1):86–96Link, Google Scholar
• Balas E., Zemel E. An algorithm for large zero-one knapsack problems. Oper. Res. (1980) 28(5):1130–1154Link, Google Scholar
• Cario M. C., Clifford J., Hill R., Yang J., Yang K., Reilly C., Schmeiser B., Uzsoy R.Alternative methods for generating synthetic generalized assignment problems (1995) Proc. 4th Indust. Engrg. Res. Conf.:1080–1089Google Scholar
• Drexl A. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Comput. (1988) 40:1–8Crossref, Google Scholar
• Fisher M., Jaikumar R., Van Wassenhove L. A multiplier adjustment method for the generalized assignment problem. Management Sci. (1986) 32(9):1095–1103Link, Google Scholar
• Fréville A., Plateau G. An exact search for the solution of the surrogate dual of the 0–1 bidimensional knapsack problem. European J. Oper. Res. (1993) 68(3):413–421Crossref, Google Scholar
• Fréville A., Plateau G. An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discrete Appl. Math. (1994) 49:189–212Crossref, Google Scholar
• Fréville A., Plateau G. The 0–1 bi-dimensional knapsack problem: Toward an efficient high-level primitive tool. J. Heuristics (1996) 2(2):147–167Crossref, Google Scholar
• Frieze A. M., Clarke M. R. B. Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses. European J. Oper. Res. (1984) 15:100–109Crossref, Google Scholar
• Guignard M., Rosenwein M. B. An improved dual based algorithm for the generalized assignment problem. Oper. Res. (1989) 37(4):658–663Link, Google Scholar
• Hanafi S., Fréville A. An efficient tabu search for the multiconstraint zero-one knapsack problem. European J. Oper. Res. (1998) 106:659–675Crossref, Google Scholar
• Hill R. R.Multivariate sampling with explicit correlation induction for simulation and optimization studies (1996) . Ph.D. Dissertation, Department of Industrial, Welding and Systems Engineering, The Ohio State University, Columbus, OHGoogle Scholar
• Hill R. R., Medeiros D. J., Watson E. F., Carson J. S., Manivannan M. S.An Analytical Comparison of Optimization Problem Generation Methodologies (1998) Proc. 1998 Winter Simulation Conf.(Institute of Electrical and Electronics Engineers, Washington, D.C.) 609–615Crossref, Google Scholar
• Hill R. R., Reilly C. H., Tew J. T., Manivannan S., Sadowski D. A., Seila A. F.Composition for multivariate random variables (1994) Proc. 1994 Winter Simulation Conf.(Institute of Electrical and Electronics Engineers, Orlando, FL) 332–342Crossref, Google Scholar
• Hooker J. N. Needed: An empirical science of algorithms. Oper. Res. (1994) 42(2):201–212Link, Google Scholar
• Iman R. L., Conover W. J. A distribution-free approach to inducing rank correlation among input variables. Comm. Statist.: Simulation Comput. (1982) 11(3):311–334Crossref, Google Scholar
• John T. C. Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty. Comput. Oper. Res. (1989) 16(5):471–479Crossref, Google Scholar
• Lokketangen A., Glover F. Solving zero-one mixed integer programming problems using tabu search. European J. Oper. Res. (1998) 106:624–658Crossref, Google Scholar
• Loulou R., Michaelides E. New greedy heuristics for the multidimensional 0–1 knapsack problem. Oper. Res. (1979) 27(6):1101–1114Link, Google Scholar
• Martello S., Toth P., Christofides N., Mingozzi A., Sandi C. The 0–1 knapsack problem. Combinatorial Optimization (1979) (John Wiley and Sons, New York) 237–279Google Scholar
• Martello S., Toth P., Brans J. P. An algorithm for the generalized assignment problem. Operational Research '81 (1981) (North-Holland, Amsterdam)589–603Google Scholar
• Martello S., Toth P. A new algorithm for the 0–1 knapsack problem. Management Sci. (1988) 34(5):633–644Link, Google Scholar
• Martello S., Toth P. Upper bounds and algorithms for hard 0–1 knapsack problems. Oper. Res. (1997) 45(5):768–778Link, Google Scholar
• Mazzola J. B., Neebe A. W. An algorithm for the bottleneck generalized assignment problem. Comput. Oper. Res. (1993) 20(4):355–362Crossref, Google Scholar
• Moore B., Peterson J., Reilly C., Balci O., Sadowski R., Nance R.Characterizing distributions of discrete bivariate random variables for simulation and evaluation of solution methods (1990) Proc. 1990 Winter Simulation Conf.(Institute of Electrical and Electronics Engineers, New Orleans, LA) 294–302Crossref, Google Scholar
• Moore B., Reilly C. H.Randomly generating synthetic optimization problems with explicitly induced correlation (1993) . OSU/ISE Working Paper, The Ohio State University Series Number 1993–002, Columbus, OHGoogle Scholar
• Pirkul H. A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Res. Logist. (1987) 34(2):161–172Crossref, Google Scholar
• Pollock G. A.Evaluation of solution methods for weighted set covering problems generated with correlated uniform random variables (1992) . Undergraduate Honors Thesis, Department of Industrial and Systems Engineering, The Ohio State University, Columbus, OHGoogle Scholar
• Potts C. N., Von Wassenhove L. N. Algorithms for scheduling a single machine to minimize the weighted number of late jobs. Management Sci. (1988) 34(7):843–858Link, Google Scholar
• Potts C. N., Von Wassenhove L. N. Single machine scheduling to minimize total late work. Oper. Res. (1992) 40(3):586–595Link, Google Scholar
• Reilly C. H., Nelson B. L., Kelton W. D., Clark G. M.Optimization test problems with uniformly distributed coefficients (1991) Proc. of the 1991 Winter Simulation Conf.(Institute of Electrical and Electronics Engineers, Phoenix, AZ) 866–874Crossref, Google Scholar
• Reilly C. H.Generating coefficients for optimization test problems with implicit correlation induction (1997a) 3Proc. 1997 IEEE Internat. Conf. Systems, Man, Cybernetics:2438–2443Crossref, Google Scholar
• Reilly C. H.Why are knapsack problems with correlated coefficients harder to solve? (1997b) INFORMS Spring 1997 MeetingMay 7San Diego, CAPresentationGoogle Scholar
• Reilly C. H., Medeiros D. J., Watson E. F., Carson J. S., Manivannan M. S.Properties of synthetic optimization problems (1998) Proc. 1998 Winter Simulation Conf.(Institute of Electrical and Electronics Engineers, Washington DC) 617–621Crossref, Google Scholar
• Saltzman M. J. Survey: Mixed integer programming. OR/MS Today (1994) 21(2):42–51Google Scholar
• Thiel J., Voss S. Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms. Comput. (1994) 32(4):226–242Google Scholar
• Toyoda Y. A simplified algorithm for obtaining approximate solutions to zero-one programming problems. Management Sci. (1975) 21(12):1417–1427Link, Google Scholar
• Trick M. A linear relaxation heuristic for the generalized assignment problem. Naval Res. Logist. (1992) 39(2):137–151Crossref, Google Scholar
• Yang J.A computational study on 0–1 knapsack problems generated under explicit correlation induction (1994) . MS Thesis, Department of Industrial and Systems Engineering, The Ohio State Universitym, Columbus, OHGoogle Scholar
• Zanakis S. H. Heuristic 0–1 linear programming: An experimental comparison of three methods. Management Sci. (1977) 24:91–104Link, Google Scholar