The Accuracy of Search Heuristics: An Empirical Study on Knapsack Problems

1. Balas, E., Carrera, M.: A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research 44, 875–890 (1996)

   MATH  MathSciNet  Google Scholar 

2. Beacham, A., Chen, X., Sillito, J., van Beek, P.: Constraint Programming Lessons Learned from Crossword Puzzles. In: Canadian Conference on AI, pp. 78–87 (2001)

   Google Scholar 

3. Cooper, M.C.: An Optimal k-Consistency Algorithm. AI 41, 89–95 (1989)

   MATH  Google Scholar 

4. Crowder, H., Johnson, E., Padberg, M.: Solving large scale zero-one linear programming problem. Operations Research 31, 803–834 (1983)

   Article  MATH  Google Scholar 

5. Dantzig, G.: Discrete variable extremum problems. Operations Research 5, 226–277 (1957)

   MathSciNet  Google Scholar 

6. Fahle, T., Sellman, M.: Cost-Based Filtering for the Constrained Knapsack Problem. AOR 115, 73–93 (2002)

   Article  MATH  Google Scholar 

7. Focacci, F., Lodi, A., Milano, M.: Cutting Planes in Constraint Programming. In: CP-AI-OR, pp. 45–51 (2000)

   Google Scholar 

8. Freuder, E.: Backtrack-Free and Backtrack-Bounded Search. In: Search in Artificial Intelligence, pp. 343–369 (1988)

   Google Scholar 

9. Garey, M.R., Johnson, D.S.: Computers and Intractability (1979)

   Google Scholar 

10. Gomes, C., van Hoeve, W., Leahu, L.: The Power of Semidefinite Programming Relaxations for MAXSAT. In: Beck, J.C., Smith, B.M. (eds.) CPAIOR 2006. LNCS, vol. 3990, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

11. Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. American Mathematical Society 64, 275–278 (1958)

    Article  MATH  MathSciNet  Google Scholar 

12. Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. IJCAI, 607–613 (1997)

    Google Scholar 

13. Hooker, J.N.: A search-infer-and-relax framework for integrating solution methods. In: CPAIOR, pp. 243–257 (2005)

    Google Scholar 

14. Martello, S., Pisinger, D., Toth, P.: Dynamic programming and tight bounds for the 0-1 knapsack problem. Management Science 45, 414–424 (1999)

    Google Scholar 

15. Pisinger, D.: Where are the hard knapsack problems? Computers and Operations Research 32(9), 2271–2284 (2005)

    Article  MATH  MathSciNet  Google Scholar 

16. Sandholm, T., Suri, S., Gilpin, A., Levine, D.: CABOP: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science 51(3), 374–390 (2005)

    Article  Google Scholar 

17. Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach (2002)

    Google Scholar 

18. Trick, M.: A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints. In: CP-AI-OR, pp. 113–124 (2001)

    Google Scholar 

19. Walsh, T.: Depth-bounded discrepancy search. In: IJCAI, pp. 1388–1393 (1997)

    Google Scholar 

20. Williams, R., Gomes, C., Selman, B.: On the Connections between Heavy-tails, Backdoors, and Restarts in Combinatorial search. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, Springer, Heidelberg (2004)

    Google Scholar 

Download references