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 "artifical intelligence"). Recent years have seen increasing interaction between these two initially separate communities. The workshop will endeavour to help fostering 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, neural networks) aim at quickly finding 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.
The other theme are branching rules. These 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 conceivably they can never be well understood (see Ming Ouyang, How good are branching rules in DPLL?, Discrete Appl. Math. 89 (1998), no. 1-3, 281--286 and DIMACS TR: 96-38, September 1996). One intriguing template for their design is strong branching, first introduced in Concorde, a computer code for the symmetric traveling salesman problem; another one echos the theme of hybrid algorithms by letting local search heuristics (such as GSAT or Walksat ) pick out promising variables for branching. In the restricted context of mixed integer linear programming, an exciting recent proposal by Miroslav Karamanov and Gérard Cornuéjols relates good branching strategies to good disjunctive cuts; it is one of those ideas that seem perfectly natural and make one wonder why they had not been thought of long ago.
Reading room:
Open problems and research directions:
Montreal:
Problem instances:
All talks and discussion sessions will take place in room 6214 (6th floor), Pavillon André-Aisenstadt
.