September 18-22, 2006
Centre de recherches mathématiques
Organizer: Vašek Chvátal (Concordia)
Problems of combinatorial optimization (such as SAT, the problem of recognizing satisfiable boolean formulas in the conjunctive normal form) have been the subject of intensive study by two communities of researchers : those in mathematical programming (often classified under “operations research”) and those in constraint satisfaction programming (often classified under “artificial intelligence”). Recent years have seen increasing interaction between these two initially separate communities. One of the aims of the workshop is to foster this confluence.
Traditional methods of combinatorial optimization come in two distinct flavours. Heuristic search algorithms (with variants such as simulated annealing, tabu search, genetic algorithms and neural networks) aim at finding quickly a satisfactory even if not necessarily optimal solution ; where these methods leave off, the exact algorithms (typically some variation on the theme of branch-and-bound) proceed, often through much time-consuming work, to find a provably optimal solution. The more recent hybrid methods borrow ideas from both sources. Development of novel hybrid algorithms will be one of the themes of the workshop.
Branching rules are the other theme of the workshop. These rules are an important component of branch-and-bound-based exact algorithms and their choice may have an overwhelming impact on the efficiency of such algorithms. Branching rules are not well understood at present and they may never be well understood. One intriguing template for their design is strong branching, first introduced in Concorde, a computer code for the symmetric travelling salesman problem ; another one echoes the theme of hybrid algorithms by letting local search heuristics (such as GSAT or Walksat) pick out promising variables for branching.