The Centre de Recherches Mathematiques in Montreal (CRM) is organizing a Theme Semester on Combinatorial Optimization that will include a NATO Advanced Study Institute and five workshops. Broadly speaking, combinatorial optimization is the study of optimization problems in which there are a finite (but usually very large) number of potential solutions, also called feasible solutions. These are not enumerated but rather defined implicitly by constraints, i.e., linear or nonlinear relations. For instance, the famous traveling salesman problem (TSP) consists of selecting the least expensive tour of a given set of locations, and the minimum spanning tree problem (MST) of selecting the least expensive network connecting given sites. Combinatorial optimization has been applied to many fields of huge practical import, such as transport scheduling, telecommunications planning and circuit design (where problems similar to the TSP, among others, must be solved routinely). Since most combinatorial optimization problems are very difficult to solve, researchers have, on the one hand, improved the time-consuming algorithms that compute optimal solutions of difficult problems such as the TSP, and on the other, designed efficient algorithms that compute near-optimal solutions (also called heuristic solutions). Two of the workshops will address the design of such algorithms (from different angles). The three others will address the computation of polyhedra related to optimization, the use of optimization in data mining, and the design of computer and communication networks such as the Internet.
