Dimension reduction techniques for mixed integer programs

混合整数规划的降维技术

基本信息

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

项目摘要

This proposed Discovery Grant research program will investigate methods for solving mixed integer optimization models. These models are frequently used to solve a wide array of problems in various industry and business sectors. Typically, the difficult part of solving a mixed integer model is the large number of integer-valued variables, which we refer to as the dimension of the model. In this program, we will focus on ways of reducing a model's dimension so that it can be solved more efficiently. We will pursue the following four directions of research. (i) Mixed integer models with linear constraints are used to solve problems in business, engineering, and health care. Classic tools for solving these models include the introduction of new constraints and divide-and-conquer methods. We plan to add to this toolbox by examining how many integer variables are actually needed to compute an optimal solution. This study will allow us to determine when a model can be optimized by simply optimizing a lower-dimensional model, where some integer constraints are relaxed.  (ii) Many models exhibit patterns in their constraints. This occurs, for instance, when we model decisions made over time such as deciding how to distribute energy in a power grid over the course of a day. Here, we will study how patterns can be leveraged to reformulate a model to have fewer integer variables. Furthermore, we will investigate patterns that appear in models of real-world problems, including those from scheduling and energy planning. (iii) Research directions (i) and (ii) simplify a high-dimensional model so that it can be solved by an algorithm designed for low-dimensional models. Alternatively, one can extend algorithms for continuous models, i.e., models with no integer variables, so that they apply to models with integer models. The continuous convex model captures problems in statistics and finance. Gradient descent is a particularly effective algorithm for solving continuous convex models. Under this investigative line, we will extend gradient descent to handle integer variables. (iv) Heuristics are frequently used in optimization to make immediate progress towards an optimal solution. In recent years, machine learning (ML) has been used to improve heuristics for the classic optimization tools mentioned in (i). We will implement ML techniques to design heuristics for reformulating integer variables as outlined in (i) and (ii). This research program will develop general tools for reducing the dimension of a mixed integer model. We expect these new tools to make long-term improvements to state-of-the-art optimization software. Mixed integer models are already used to address problems in Canadian society; for example, the problem of matching organ donors with patients or the problem of mapping local power grids. Therefore, we anticipate that this research will also lead to faster methods for solving preexisting models used by Canadian organizations and businesses.
这项拟议的发现拨款研究计划将研究求解混合整数优化模型的方法。这些模型经常被用来解决各种工业和商业部门的各种问题。通常,求解混合整数模型的困难部分是大量的整数值变量,我们将其称为模型的维度。在本节目中,我们将重点介绍如何降低模型的维度,以便更有效地求解。我们将进行以下四个方面的研究。(I)线性约束的混合整数模型用于解决商业、工程和医疗保健方面的问题。解决这些模型的经典工具包括引入新的约束和分而治之的方法。我们计划通过检查实际需要多少个整数变量来计算最优解来增加此工具箱。这项研究将使我们能够确定何时可以通过简单地优化低维模型来优化模型,其中一些整数约束被放松。(Ii)许多模型在其约束中表现出模式。例如,当我们对随着时间推移所做的决策进行建模时,例如决定如何在一天的过程中在电网中分配能源时,就会发生这种情况。在这里,我们将研究如何利用模式来重新制定模型,使其具有更少的整数变量。此外,我们将研究现实世界问题模型中出现的模式,包括来自调度和能源规划的模式。(3)研究方向(一)和(二)简化高维模型,以便可以用为低维模型设计的算法来求解。或者,人们可以扩展用于连续模型的算法,即没有整数变量的模型,以便它们适用于具有整数模型的模型。连续凸模型捕捉了统计学和金融学中的问题。梯度下降算法是求解连续凸模型的一种特别有效的算法。在这一研究思路下,我们将把梯度下降扩展到处理整数变量。(4)在优化中经常使用启发式方法,以便立即获得最优解。近年来,机器学习(ML)被用于改进(I)中提到的经典优化工具的启发式算法。我们将实现ML技术来设计启发式算法,以重新定义整数变量,如(I)和(Ii)所述。这项研究计划将开发用于混合整数模型降维的通用工具。我们预计这些新工具将对最先进的优化软件进行长期改进。混合整数模型已经被用来解决加拿大社会中的问题;例如,器官捐赠者与患者匹配的问题或绘制当地电网图的问题。因此,我们预计这项研究还将导致解决加拿大组织和企业使用的先前存在的模型的更快方法。

项目成果

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

Paat, Joseph其他文献

Distances between optimal solutions of mixed-integer programs
  • DOI:
    10.1007/s10107-018-1323-z
  • 发表时间:
    2020-01-01
  • 期刊:
  • 影响因子:
    2.7
  • 作者:
    Paat, Joseph;Weismantel, Robert;Weltge, Stefan
  • 通讯作者:
    Weltge, Stefan

Paat, Joseph的其他文献

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

{{ truncateString('Paat, Joseph', 18)}}的其他基金

Dimension reduction techniques for mixed integer programs
混合整数规划的降维技术
  • 批准号:
    RGPIN-2021-02475
  • 财政年份:
    2022
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Grants Program - Individual
Dimension reduction techniques for mixed integer programs
混合整数规划的降维技术
  • 批准号:
    DGECR-2021-00013
  • 财政年份:
    2021
  • 资助金额:
    $ 2.62万
  • 项目类别:
    Discovery Launch Supplement

相似国自然基金

兼捕减少装置(Bycatch Reduction Devices, BRD)对拖网网囊系统水动力及渔获性能的调控机制
  • 批准号:
    32373187
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目
转运蛋白RCP调控巨噬细胞脂肪酸氧化参与系统性红斑狼疮发病的机制研究
  • 批准号:
    82371798
  • 批准年份:
    2023
  • 资助金额:
    49.00 万元
  • 项目类别:
    面上项目
某些非线性椭圆偏微分方程解的集中现象
  • 批准号:
    10926057
  • 批准年份:
    2009
  • 资助金额:
    3.0 万元
  • 项目类别:
    数学天元基金项目

相似海外基金

Identifying Predictors of Condom Use
确定安全套使用的预测因素
  • 批准号:
    10821861
  • 财政年份:
    2024
  • 资助金额:
    $ 2.62万
  • 项目类别:
Computational Modeling Core
计算建模核心
  • 批准号:
    10551707
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Nitrosative stress and NO detoxifying reaction mechanisms in microbial nonheme diiron proteins
微生物非血红素二铁蛋白的亚硝化应激和NO解毒反应机制
  • 批准号:
    10656107
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Pre-clinical testing of low intensity ultrasound as novel strategy to prevent paclitaxel-induced hair follicle damage in a humanized mouse model of chemotherapy-induced alopecia
低强度超声的临床前测试作为预防化疗引起的脱发人源化小鼠模型中紫杉醇引起的毛囊损伤的新策略
  • 批准号:
    10722518
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Core 1: Biostatistics & Bioinformatics Core
核心1:生物统计学
  • 批准号:
    10716157
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
The Pain in a Dish Assay (PIDA): a high throughput system featuring human stem cell-derived nociceptors and dorsal horn neurons to test compounds for analgesic activity
皿中疼痛测定 (PIDA):一种高通量系统,具有人类干细胞来源的伤害感受器和背角神经元,用于测试化合物的镇痛活性
  • 批准号:
    10759735
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Animal Models and Histology Core
动物模型和组织学核心
  • 批准号:
    10715404
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Transcriptional Activation of p62 by the master antioxidant NRF2 in EBV latency
EBV潜伏期主要抗氧化剂NRF2对p62的转录激活
  • 批准号:
    10726975
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Community-engaged implementation strategies for acceptance interventions to improve access to care for people with HIV and injection drug use
社区参与的接受干预实施战略,以改善艾滋病毒感染者和注射吸毒者获得护理的机会
  • 批准号:
    10762655
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
Platelet Metabolic Stress Induces Thrombo-Inflammation to Drive Endothelial Dysfunction in PH
PH 中血小板代谢应激诱导血栓炎症导致内皮功能障碍
  • 批准号:
    10736724
  • 财政年份:
    2023
  • 资助金额:
    $ 2.62万
  • 项目类别:
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了