Conference Proposal: CRM Theme Semester on Combinatorial Optimization (June 2006 - December 2006)

蒙特利尔数学研究中心（CRM）正在组织一个关于组合优化的主题学期，其中包括一个北约高级研究所和五个讲习班。广义地说，组合优化是研究存在有限（但通常非常大）数量的潜在解（也称为可行解）的优化问题。这些不是枚举的，而是由约束隐含地定义的，即，线性或非线性关系。例如，著名的旅行商问题（TSP）包括选择给定位置集合的最便宜的旅行，以及选择连接给定站点的最便宜的网络的最小生成树问题（MST）。组合优化已经被应用到许多具有巨大实际意义的领域，例如运输调度、电信规划和电路设计（其中，与TSP类似的问题必须常规解决）。由于大多数组合优化问题都很难求解，研究者们一方面改进了计算TSP等难题的最优解的耗时算法，另一方面设计了计算近似最优解的高效算法（也称为启发式算法）。其中两个讲习班将讨论这种算法的设计（从不同的角度）。其他三个将解决与优化有关的多面体的计算，在数据挖掘中使用优化，以及计算机和通信网络（如互联网）的设计。

The Centre de Recherches Mathematiques in Montreal (CRM) is organizing aTheme Semester on Combinatorial Optimization that will include a NATOAdvanced 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 potentialsolutions, also called feasible solutions. These are not enumerated but rather defined implicitly by constraints, i.e., linear ornonlinear relations. For instance, the famous traveling salesman problem (TSP) consists of selecting the least expensive tour of a given set oflocations, and the minimum spanning tree problem (MST) of selecting theleast 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 verydifficult to solve, researchers have, on the one hand, improved thetime-consuming algorithms that compute optimal solutions of difficultproblems such as the TSP, and on the other, designed efficientalgorithms that compute near-optimal solutions (also called heuristicsolutions). 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.