Theory, computations and applications of structured Mixed-Integer Programs

结构化混合整数程序的理论、计算和应用

基本信息

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

项目摘要

Mixed-Integer Programming (MIP) is an extremely important tool in quantitative decision making within modern corporations. Its applications include air transportation, telecommunications, logistics and manufacturing. The long-term goal of my research is to improve solution methods for MIPs, by providing better theoretical understanding of its properties, improving algorithmic ideas and ultimately allowing one to solve real-world optimization problems at a larger scale. This proposal advances this goal by studying particular structures that appear in some applications. Two research streams will be addressed. The first stream deals with considering sparsity in MIPs, particularly in cutting planes. Sparsity is a measure of the number of nonzero components, and it is an important factor that allows several algorithms to become faster. It is a prominent feature in several benchmark MIPs that came from practical applications - in a large set of such benchmark MIPs, the average sparsity is close to 1%. Cutting planes are one of the most important components in the practical solution of MIPs and, among all cutting planes, split cuts are the ones with greater impact. In a recent work, we have investigated split cuts obtained from sparse splits and show, through computational experiments, that this subclass of split cuts is very important. Therefore, this first stream will address theoretical and computational questions that arise based on such a sparsity parameter, with the ultimate goal to improve the performance of MIP algorithms. The second stream is dedicated to studying the structure obtained in the context of MIP formulations for vehicle routing (VRP), particularly under uncertainty. The VRP is an important optimization problem that seeks to find the minimum cost way to route a fleet of vehicles to satisfy a set of customer demands in such a way that the capacity of each vehicle is respected. It finds applications in logistics and transportation. One limiting assumption in the VRP is that all customer demands are known in advance, which is not always the case. Thus, recently, renewed research interest has been devoted to studying variants of the problem where demands are uncertain (i.e. stochastic VRP). Thus, this second stream aims to significantly advance the state-of-the-art in solving the stochastic VRP. Of particular interest are data-driven approaches, i.e. approaches that optimize using only historical data as input. The proposal will investigate new algorithms for existing versions of the problem and new paradigms for modeling more realistic versions of it. Ultimately, the development of such approaches will significantly increase the applicability of VRP models in real-world applications. HQP trained as a result of this proposal will gain valuable skills in quantitative decision making, acquiring both theoretical and implementation knowledge, which is important in both academia and industry.
混合规划是现代企业定量决策的重要工具。其应用包括航空运输、电信、物流和制造业。我的研究的长期目标是改进MIP的解决方案,通过提供对其属性的更好的理论理解,改进算法思想,并最终允许在更大范围内解决现实世界的优化问题。该建议通过研究在某些应用中出现的特定结构来推进这一目标。两个研究流将得到解决。 第一个流涉及在MIP中考虑稀疏性,特别是在切割平面中。稀疏性是非零分量数量的度量,它是允许几种算法变得更快的重要因素。这是来自实际应用的几个基准MIP中的一个突出特征-在大量这样的基准MIP中,平均稀疏度接近1%。 切割平面是MIP实际解决方案中最重要的组成部分之一,在所有切割平面中,分裂切割是影响最大的切割平面。在最近的一项工作中,我们已经调查了分裂削减稀疏分裂和显示,通过计算实验,这子类的分裂削减是非常重要的。 因此,这第一个流将解决理论和计算问题,出现在这样的稀疏参数的基础上,最终目标是提高MIP算法的性能。 第二个流是专门研究的MIP配方的车辆路径(VRP),特别是在不确定性的背景下获得的结构。车辆路径问题是一个重要的优化问题,它寻求找到最小成本的方式来路由车队,以满足一组客户的需求,在这样的方式,每辆车的能力是尊重。它适用于物流和运输。VRP中的一个限制性假设是所有客户需求都是事先已知的,但情况并非总是如此。因此,最近,新的研究兴趣一直致力于研究需求不确定的问题(即随机车辆路径问题)的变种。 因此,这第二个流的目的是显着推进国家的最先进的解决随机车辆路径问题。特别令人感兴趣的是数据驱动的方法,即仅使用历史数据作为输入进行优化的方法。该提案将调查新的算法,为现有版本的问题和新的范例建模更现实的版本,它。最终,这种方法的发展将显着增加VRP模型在现实世界中的应用的适用性。 HQP培训的结果,这一建议将获得宝贵的技能,定量决策,获得理论和实施知识,这是在学术界和工业界都很重要。

项目成果

期刊论文数量(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 }}

Fukasawa, Ricardo其他文献

A disjunctive convex programming approach to the pollution-routing problem
A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem
  • DOI:
    10.1287/trsc.2015.0593
  • 发表时间:
    2016-02-01
  • 期刊:
  • 影响因子:
    4.6
  • 作者:
    Fukasawa, Ricardo;He, Qie;Song, Yongjia
  • 通讯作者:
    Song, Yongjia
The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands
  • DOI:
    10.1016/j.orl.2022.11.005
  • 发表时间:
    2022-11-25
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Fukasawa, Ricardo;Gunter, Joshua
  • 通讯作者:
    Gunter, Joshua
The time dependent traveling salesman problem: polyhedra and algorithm
  • DOI:
    10.1007/s12532-012-0047-y
  • 发表时间:
    2013-03-01
  • 期刊:
  • 影响因子:
    6.3
  • 作者:
    Abeledo, Hernan;Fukasawa, Ricardo;Uchoa, Eduardo
  • 通讯作者:
    Uchoa, Eduardo

Fukasawa, Ricardo的其他文献

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

{{ truncateString('Fukasawa, Ricardo', 18)}}的其他基金

Solution of optimization problems for group decision making
群体决策优化问题的求解
  • 批准号:
    566661-2021
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Alliance Grants
Theory, computations and applications of structured Mixed-Integer Programs
结构化混合整数程序的理论、计算和应用
  • 批准号:
    RGPIN-2020-04030
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Theory, computations and applications of structured Mixed-Integer Programs
结构化混合整数程序的理论、计算和应用
  • 批准号:
    RGPIN-2020-04030
  • 财政年份:
    2020
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Improved methods and applications of Mixed-Integer Programming
混合整数规划的改进方法及应用
  • 批准号:
    RGPIN-2014-05623
  • 财政年份:
    2019
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Improved methods and applications of Mixed-Integer Programming
混合整数规划的改进方法及应用
  • 批准号:
    RGPIN-2014-05623
  • 财政年份:
    2017
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Improved methods and applications of Mixed-Integer Programming
混合整数规划的改进方法及应用
  • 批准号:
    RGPIN-2014-05623
  • 财政年份:
    2016
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Improved methods and applications of Mixed-Integer Programming
混合整数规划的改进方法及应用
  • 批准号:
    RGPIN-2014-05623
  • 财政年份:
    2015
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Improved methods and applications of Mixed-Integer Programming
混合整数规划的改进方法及应用
  • 批准号:
    RGPIN-2014-05623
  • 财政年份:
    2014
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Methods for mixed integer programming
混合整数规划方法
  • 批准号:
    371937-2009
  • 财政年份:
    2013
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Methods for mixed integer programming
混合整数规划方法
  • 批准号:
    371937-2009
  • 财政年份:
    2012
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

Identifying how alcohol-evoked changes in neural firing affect systems level computations during decision-making
确定酒精引起的神经放电变化如何影响决策过程中的系统级计算
  • 批准号:
    10766877
  • 财政年份:
    2023
  • 资助金额:
    $ 3.79万
  • 项目类别:
Computations and applications of Seiberg-Witten Floer stable homotopy type
Seiberg-Witten Floer稳定同伦型的计算与应用
  • 批准号:
    23K03115
  • 财政年份:
    2023
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Collaborative Research: Hardware-Aware Matrix Computations for Deep Learning Applications
协作研究:深度学习应用的硬件感知矩阵计算
  • 批准号:
    2247014
  • 财政年份:
    2023
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Standard Grant
Collaborative Research: Hardware-Aware Matrix Computations for Deep Learning Applications
协作研究:深度学习应用的硬件感知矩阵计算
  • 批准号:
    2247015
  • 财政年份:
    2023
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Standard Grant
Electromagnetic field computations for multi-physics phenomena: new techniques for emerging applications
多物理现象的电磁场计算:新兴应用的新技术
  • 批准号:
    RGPIN-2018-04650
  • 财政年份:
    2022
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Biomolecular Structure and Dynamics
生物分子结构与动力学
  • 批准号:
    10684911
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
Surveillance genome sequencing to detect SARS-CoV-2 virus variants in Montana
监测基因组测序以检测蒙大拿州的 SARS-CoV-2 病毒变异
  • 批准号:
    10684476
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
Biomolecular Structure and Dynamics: Equipment Supplement for Zeiss 880 Airyscan Upgrade
生物分子结构和动力学:Zeiss 880 Airyscan 升级的设备补充
  • 批准号:
    10580417
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
Electromagnetic field computations for multi-physics phenomena: new techniques for emerging applications
多物理现象的电磁场计算:新兴应用的新技术
  • 批准号:
    RGPIN-2018-04650
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
    Discovery Grants Program - Individual
Biomolecular Structure and Dynamics: Equipment Supplement for Formulatrix NT8 and Rock Imager 54
生物分子结构和动力学:Formulatrix NT8 和 Rock Imager 54 的设备补充
  • 批准号:
    10794832
  • 财政年份:
    2021
  • 资助金额:
    $ 3.79万
  • 项目类别:
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了