Constraint Programming is recognized as an efficient technique for solving hard combinatorial optimization problems. However, it is best used in conjunction with other optimization paradigms such as local search, yielding hybrid algorithms with constraints. Such combinations lack a language supporting an elegant description and retaining the original declarativity of Constraint Logic Programming. We propose a language, SALSA, dedicated to specifying (local, global or hybrid) search algorithms. We illustrate its use on a few examples from combinatorial optimization for which we specify complex optimization procedures with a few simple lines of code of high abstraction level. We report preliminary experiments showing that such a language can be implemented on top of CP systems, yielding a powerful environment for combinatorial optimization.

References in zbMATH (referenced in 23 articles , 1 standard article )

Showing results 1 to 20 of 23.
Sorted by year (citations)

1 2 next

  1. Schrijvers, Tom; Tack, Guido; Wuille, Pieter; Samulowitz, Horst; Stuckey, Peter J.: Search combinators (2013)
  2. Milano, Michela; Wallace, Mark: Integrating operations research in constraint programming (2010)
  3. Caseau, Yves: Combining constraint propagation and meta-heuristics for searching a maximum weight Hamiltonian chain (2006)
  4. Loudni, Samir; Boizumault, Patrice; David, Philippe: On-line resources allocation for ATM networks with rerouting (2006)
  5. Milano, Michela; Wallace, Mark: Integrating operations research in constraint programming (2006)
  6. Van Hentenryck, Pascal; Michel, Laurent: Nondeterministic control for hybrid search (2006)
  7. Danna, Emilie; Rothberg, Edward; Le Pape, Claude: Exploring relaxation induced neighborhoods to improve MIP solutions (2005)
  8. Katriel, Irit; Michel, Laurent; Van Hentenryck, Pascal: Maintaining longest paths incrementally (2005)
  9. Michel, Laurent; Van Hentenryck, Pascal: A modeling layer for constraint-programming libraries (2005)
  10. Van Hentenryck, Pascal; Michel, Laurent: Control abstractions for local search (2005)
  11. Van Hentenryck, Pascal; Michel, Laurent; Liu, Liyuan: Contraint-based combinators for local search (2005)
  12. Van Roy, Peter; Brand, Per; Duchier, Denys; Haridi, Seif; Schulte, Christian; Henz, Martin: Logic programming in the context of multiparadigm programming: The Oz experience (2003)
  13. Caseau, Yves; Josset, François-Xavier; Laburthe, François: CLAIRE: Combining sets, search and rules to better express algorithms (2002)
  14. Dasgupta, P.; Chakrabarti, P.P.; Dey, A.; Ghose, S.; Bibel, W.: Solving constraint optimization problems from CLP-style specifications using heuristic search techniques (2002)
  15. Laburthe, François; Caseau, Yves: SALSA: a language for search algorithms (2002)
  16. Rousseau, Louis-Martin; Gendreau, Michel; Pesant, Gilles: Using constraint-based operators to solve the vehicle routing problem with time windows (2002)
  17. Schulte, Christian: Programming constraint services. High-level programming of standard and new constraint services (2002)
  18. Van Hentenryck, Pascal: Constraint and integer programming in OPL (2002)
  19. Wallace, Mark; Schimpf, Joachim: Finding the right hybrid algorithm -- A combinatorial meta-problem (2002)
  20. Boizumault, Patrice; David, Philippe; Djellab, Housni: Resource allocation in a mobile telephone network: A constructive repair algorithm (2001)

1 2 next