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

蒙特利尔数学研究中心(CRM)正在组织一个关于组合优化的主题学期，其中将包括一个NATO高级研究所和五个讲习班。广义地说，组合优化是对存在有限(但通常是非常大)数量的潜在解，也称为可行解的优化问题的研究。这些不是列举的，而是由约束(即线性或非线性关系)隐式定义的。例如，著名的旅行商问题(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.