Computational Studies in Discrete Optimization

离散优化的计算研究

基本信息

  • 批准号:
    RGPIN-2014-04349
  • 负责人:
  • 金额:
    $ 3.28万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2015
  • 资助国家:
    加拿大
  • 起止时间:
    2015-01-01 至 2016-12-31
  • 项目状态:
    已结题

项目摘要

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.
离散优化用于解决涉及从一系列可能性中选择最佳替代方案的实际问题;它在经济的几乎每一个领域都有广泛的应用。许多行业,从电信到超大规模集成电路,都完全依赖离散优化来指导他们完成复杂的设计程序。 也许最重要的一类离散优化问题是混合整数规划(MIP)模型。这些模型具有最小化或最大化受线性不等约束的线性函数的形式,其中某些或全部变量被要求取整数值。如果不要求变量为整数,则该模型是线性规划(LP)问题。积分变量使得MIP模型比相应的LP模型更难求解,但正是这种完整性组件使MIP模型能够捕捉本质上离散的决策。 离散优化的巨大成功在很大程度上归功于George Dantzig著名的单纯形算法的强大功能,该算法被评为2000年十大世纪算法之一。在离散优化中,单纯形算法与一种称为割平面法的技术相结合,以改进离散问题的Lp逼近。割面的使用最早是由Dantzig,Fulkerson和Johnson于1954年在研究旅行商问题(TSP)时提出的;多年来,人们提出了许多变体,割面现在是商业MIP解算器的基本组成部分,也是对许多类离散优化问题最成功的攻击。 我们提出了一系列旨在扩大离散优化和混合整数规划的研究范围。这项工作有两个主要推动力。首先,我们将寻求开发工具,利用并行计算平台,用单纯形法解决更大类别的线性规划模型。其次,我们将研究MIP和TSP模型,以开发更好的技术,将割平面法应用于大型模型,再次侧重于并行计算平台的使用。预期的结果是极大地改进了用于解决工业应用中出现的LP和MIP模型的工具和软件,以及用于解决旅行推销员问题的广泛使用的协和代码的改进版本。 拟议项目的一个重要组成部分是对研究生进行大规模离散优化模型实际求解方面的高级技术培训。参与该项目的学生将非常适合目前这一领域的许多工业界和学术界的职位。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Cook, William其他文献

Inside environmental auditing: effectiveness, objectivity, and transparency
Machine Learning for Conservative-to-Primitive in Relativistic Hydrodynamics
相对论流体动力学中从保守到原始的机器学习
  • DOI:
    10.3390/sym13112157
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Dieselhorst, Tobias;Cook, William;Bernuzzi, Sebastiano;Radice, David
  • 通讯作者:
    Radice, David
The actor-partner interdependence model for categorical dyadic data: A user-friendly guide to GEE
  • DOI:
    10.1111/pere.12028
  • 发表时间:
    2014-06-01
  • 期刊:
  • 影响因子:
    1.6
  • 作者:
    Loeys, Tom;Cook, William;Buysse, Ann
  • 通讯作者:
    Buysse, Ann
A hybrid branch-and-bound approach for exact rational mixed-integer programming
  • DOI:
    10.1007/s12532-013-0055-6
  • 发表时间:
    2013-09-01
  • 期刊:
  • 影响因子:
    6.3
  • 作者:
    Cook, William;Koch, Thorsten;Wolter, Kati
  • 通讯作者:
    Wolter, Kati
Deposition, characterization and performance evaluation of ceramic coatings on metallic substrates for supercritical water-cooled reactors
  • DOI:
    10.1016/j.surfcoat.2010.12.017
  • 发表时间:
    2011-02-25
  • 期刊:
  • 影响因子:
    5.4
  • 作者:
    Hui, Rob;Cook, William;Zhang, Lefu
  • 通讯作者:
    Zhang, Lefu

Cook, William的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Cook, William', 18)}}的其他基金

Evaluation of the effect of ion exchange resin on feeder integrity
离子交换树脂对进料器完整性影响的评估
  • 批准号:
    528048-2018
  • 财政年份:
    2020
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Collaborative Research and Development Grants
Evaluation of the effect of ion exchange resin on feeder integrity
离子交换树脂对进料器完整性影响的评估
  • 批准号:
    528048-2018
  • 财政年份:
    2019
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Collaborative Research and Development Grants
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2018
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Evaluation of the effect of ion exchange resin on feeder integrity
离子交换树脂对进料器完整性影响的评估
  • 批准号:
    528048-2018
  • 财政年份:
    2018
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Collaborative Research and Development Grants
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2017
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Performance Testing and Evaluation of Diffusion Coatings for Application in Supercritical Water-Cooled Reactors and Power Plants
超临界水冷堆和发电厂扩散涂层的性能测试和评估
  • 批准号:
    507272-2016
  • 财政年份:
    2016
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Engage Grants Program
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2016
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Mitigating hydrogen production in the end-shield cooling system of CANDU reactors
减少 CANDU 反应堆端罩冷却系统中的氢气产生
  • 批准号:
    467688-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Collaborative Research and Development Grants
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    461928-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Mitigating hydrogen production in the end-shield cooling system of CANDU reactors
减少 CANDU 反应堆端罩冷却系统中的氢气产生
  • 批准号:
    467688-2014
  • 财政年份:
    2014
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Collaborative Research and Development Grants

相似海外基金

Advanced Studies and Developments on Discrete Preimage Problems
离散原像问题的最新研究与进展
  • 批准号:
    22H00532
  • 财政年份:
    2022
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Grant-in-Aid for Scientific Research (A)
Studies on game theory by Lefschetz fixed point theorem and discrete fixed point theorems
Lefschetz不动点定理和离散不动点定理研究博弈论
  • 批准号:
    20K03751
  • 财政年份:
    2020
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2018
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Studies on discrete quasi-integrable systems
离散拟可积系统研究
  • 批准号:
    18H01127
  • 财政年份:
    2018
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2017
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    RGPIN-2014-04349
  • 财政年份:
    2016
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Individual
Studies of discrete curved geometries
离散弯曲几何形状的研究
  • 批准号:
    480710-2015
  • 财政年份:
    2015
  • 资助金额:
    $ 3.28万
  • 项目类别:
    University Undergraduate Student Research Awards
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    461928-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Studies on discrete integrable systems via tropical algebraic curves
基于热带代数曲线的离散可积系统研究
  • 批准号:
    26400107
  • 财政年份:
    2014
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Computational Studies in Discrete Optimization
离散优化的计算研究
  • 批准号:
    461928-2014
  • 财政年份:
    2014
  • 资助金额:
    $ 3.28万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了