Alternating control tree search for knapsack/covering problems

• Achterberg, T.: Conflict analysis in mixed integer programming. Discrete Optim. 4(1), 4–20 (2007)

  Article  MATH  MathSciNet  Google Scholar 

• Arntzen, H., Hvattum, L.M., Løkketangen, A.: Adaptive memory search for multidemand multidimensional knapsack problems. Comput. Oper. Res. 33, 2508–2525 (2006)

  Article  MATH  MathSciNet  Google Scholar 

• Beaujon, G.J., Marin, S.P., McDonald, G.C.: Balancing and optimizing a portfolio of r&d projects. Nav. Res. Logist. 48, 18–40 (2001)

  Article  MATH  MathSciNet  Google Scholar 

• Cappanera, P.: Discrete facility location and routing of obnoxious facilities. PhD thesis, University of Milano (1999)

• Cappanera, P., Trubian, M.: A local-search-based heuristic for the demand-constrained multidimensional knapsack problem. INFORMS J. Comput. 17, 82–98 (2005)

  Article  MathSciNet  Google Scholar 

• Chu, P.C., Beasley, J.E.: A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4, 63–86 (1998)

  Article  MATH  Google Scholar 

• Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–90 (2005)

  Article  MATH  MathSciNet  Google Scholar 

• Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1), 23–47 (2003)

  Article  MATH  MathSciNet  Google Scholar 

• Gavish, B., Pirkul, H.: Allocation of databases and processors in a distributed computing system. In: Akoka, J. (ed.) Management of Distributed Data Processing, pp. 215–231. North-Holland, Amsterdam (1982)

  Google Scholar 

• Gilmore, P.C., Gomory, R.E.: The theory and computation of knapsack functions. Oper. Res. 14, 1045–1075 (1966)

  Article  MathSciNet  Google Scholar 

• Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977)

  Article  Google Scholar 

• Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Boston (1997)

  MATH  Google Scholar 

• Gomes, C., Sellmann, M.: Streamlined constraint reasoning. In: Proceedings, CPAIOR 2004 (2004)

• Gomes, C., van Hoeve, W., Leahu, L.: The power of semidefinite programming relaxations for MAX-SAT. In: Proceedings, CPAIOR 2006, pp. 104–118 (2006)

• Hanafi, S., Wilbaut, C.: Improved convergent heuristic for 0–1 mixed integer programming. Research Report, University of Valenciennes (2006)

• Holmberg, K., Yuan, D.: A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48(3), 461–481 (2000)

  Article  MATH  MathSciNet  Google Scholar 

• Hvattum, L.M., Løkketangen, A.: Experiments using scatter search for the multidemand multidimensional knapsack problem. In: Doerner, K.F., et al. (eds.) Metaheuristics: Progress in Complex Systems Optimization. Operations Research/Computer Science Interfaces, vol. 39, pp. 3–24. Springer, Berlin (2007)

  Google Scholar 

• Laguna, M., Martí, R.: Scatter Search: Methodology and Implementations in C. Kluwer Academic, Dordrecht (2003)

  Google Scholar 

• Lorie, J., Savage, L.: Three problems in capital rationing. J. Bus. 28, 229–239 (1955)

  Google Scholar 

• Manne, A., Markowitz, H.: On the solution of discrete programming problems. Econometrica 25, 85–110 (1957)

  MathSciNet  Google Scholar 

• Plastria, F.: Static competitive facility location: an overview of optimization approaches. Eur. J. Oper. Res. 129, 461–470 (2001)

  Article  MATH  MathSciNet  Google Scholar 

• Puchinger, J., Raidl, G.R.: Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In: Mira, J., Álvarez, J.R. (eds.) Proceedings of the First International Work-Conference on the Interplay Between Natural and Artificial Computation, Part II. Lecture Notes in Computer Science, vol. 3562, pp. 41–53. Springer, Berlin (2005)

  Google Scholar 

• Romero-Morales, D., Carrizosa, E., Conde, E.: Semi-obnoxious location models: a global optimization approach. Eur. J. Oper. Res. 102, 295–301 (1997)

  Article  MATH  Google Scholar 

• Savelsbergh, M.W.P.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994)

  MATH  MathSciNet  Google Scholar 

• Sellmann, M., Kliewer, G., Koberstein, A.: Lagrangian cardinality cuts and variable fixing for capacitated network. In: Proceedings of the Tenth Annual European Symposium on Algorithms, pp. 845–858 (2002)

• Shih, W.: A branch and bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30, 369–378 (1979)

  MATH  Google Scholar 

• Soyster, A.L., Lev, B., Slivka, W.: Zero-one programming with many variables and few constraints. Eur. J. Oper. Res. 2, 195–201 (1978)

  Article  MATH  Google Scholar 

• Vasquez, M., Hao, J.-K.: A hybrid approach for the 0–1 multidimensional knapsack problem. In: Proceedings of the International Joint Conference on Artificial Intelligence 2001, pp. 328–333 (2001)

• Vasquez, M., Vimont, Y.: Improved results on the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 165, 70–81 (2005)

  Article  MATH  MathSciNet  Google Scholar 

Download references