Computational Studies in Discrete Optimization

离散优化的计算研究

• 批准号: RGPIN-2014-04349
• 负责人: Cook, William
• 金额: $ 3.28万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=587750
• 关键词: Computational; Studies; Discrete; Optimization

Discrete optimization is used to solve practical problems that involve choosing the best alternative from a field of possibilities; it has broad applications in nearly every segment of the economy. Many industries, ranging from telecommunications to VLSI, are fully dependent on discrete optimization to guide them through complex design procedures. Perhaps the most important class of discrete optimization problems are the mixed-integer-programming (MIP) models. These models have the form of minimizing or maximizing a linear function subject to linear inequality constraints, where some or all of the variables are required to take on integer values. If no variables are required to be integer, then the model is a linear-programming (LP) problem. The integral variables make MIP models much more difficult to solve than the corresponding LP models, but it is this integrality component that allows MIP models to capture decisions that are discrete in nature. The great success of discrete optimization is due in large part to the power of George Dantzig's famous simplex algorithm, designed to solve LP models; this algorithm was named one of the Top Ten Algorithms of the Century in the year 2000. In discrete optimization, the simplex algorithm is combined with a technique known as the cutting-plane method for improving the LP approximations of discrete problems. The use of cutting planes was pioneered by Dantzig, Fulkerson, and Johnson in 1954 in their work on the traveling salesman problem (TSP); many variations have been proposed over the years and cutting planes are now an essential ingredient in commercial MIP solvers and in the most successful attacks on many classes of discrete optimization problems. We propose a line of research aimed at extending the reach of discrete optimization and mixed-integer programming. The work has two main thrusts. First, we will seek to develop tools that will allow for the solution of much larger classes of LP models with the simplex method, utilizing parallel computing platforms. Secondly, we will study MIP and TSP models to develop better techniques for applying the cutting-plane method to large-scale models, again focusing on the use of parallel computing platforms. The expected outcomes are greatly improved tools and software for the solution of LP and MIP models arising in industrial applications, as well as an improved version of the widely-used Concorde code for the solution of the traveling salesman problem. An important component of the proposed project is the training of graduate students in advanced techniques in the practical solution of large-scale discrete optimization models. Students involved in the project will be well-suited for the many positions that are currently available in this area in both industry and academia.

离散优化用于解决实际问题，涉及从可能性领域中选择最佳替代方案；它在几乎每个经济领域都有广泛的应用。从电信到VLSI，许多行业都完全取决于离散优化，以指导它们通过复杂的设计程序。 也许最重要的离散优化问题类别是混合构图（MIP）模型。这些模型的形式是最大程度地减少或最大化线性函数，但要受到线性不等式约束，其中某些或全部变量需要进行整数值。如果不需要变量是整数，则模型是线性编程（LP）问题。积分变量使MIP模型比相应的LP模型更难求解，但是正是这种完整性组件允许MIP模型捕获本质上离散的决策。 离散优化的巨大成功在很大程度上归功于乔治·丹齐格（George Dantzig）著名的单纯形算法的力量，该算法旨在解决LP模型。该算法在2000年被评为本世纪前十算法之一。在离散优化时，单纯形算法与一种称为改善离散问题LP近似值的切切平面方法相结合。 1954年，丹齐格（Dantzig），富尔克森（Fulkerson）和约翰逊（Johnson）在旅行推销员问题（TSP）的工作中率先使用了切割飞机的使用；多年来，已经提出了许多变化，并且切割平面现在是商业MIP求解器以及对许多离散优化问题的最成功攻击中的重要成分。 我们提出了一系列研究，旨在扩大离散优化和混合企业编程的覆盖范围。这项工作有两个主要推力。首先，我们将寻求开发工具，以利用并行计算平台来解决使用单纯形方法的更大类LP模型的解决方案。其次，我们将研究MIP和TSP模型，以开发更好的技术，以将切割平面方法应用于大型模型，再次着重于平行计算平台的使用。预期的结果大大改进了用于解决工业应用程序中LP和MIP模型解决方案的工具和软件，以及用于解决旅行推销员问题的广泛使用协和代码的改进版本。 该项目的一个重要组成部分是在大规模离散优化模型的实际解决方案中对研究生进行高级技术的培训。参与该项目的学生将非常适合行业和学术界目前可用的许多职位。