通过对其目标函数的随机扰动,为整数线性程序找到多个最佳解决方案
Noah Schulhof1,2, Pattara Sukprasert3, Eytan Ruppin1
1Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD 20892, USA.
新的算法MORSE有效地为整数线性程序 (ILP) 找到多个最佳解决方案. 这种方法克服了现有的解决方案的局限性,使生物医学等领域的分析更好.
科学领域:
- 运营研究 运营研究
- 计算生物学 计算生物学
- 计算机科学 计算机科学
背景情况:
- 整数线性程序 (ILP) 和混合整数程序 (MIP) 经常具有多个不同的最佳解决方案.
- 像Gurobi这样的标准解决器可能会出现偏差,更频繁地返回某些最佳值,这限制了全面分析.
- 识别和分析各种最佳解决方案对于生物医学等领域的领域特定见解至关重要.
研究的目的:
- 介绍MORSE (通过随机抽样和仔细选择参数Epsilon) 的多重最佳值,这是一个新奇的随机算法,用于有效地生成ILP的多重最佳值.
- 证明MORSE能够克服现有解决器在探索ILP的解决空间方面的局限性.
- 为研究和应用提供一种有价值的各种最佳解决方案的方法.
主要方法:
- 莫尔斯使用对象函数的系数的乘法扰动,创建保留原始最佳的修改实例.
- 该算法旨在随机化和并行化,以实现高效的计算.
- 理论证明证明了在特定条件下保持最佳值的可能性,并且在 0/1 选择问题中找到不同的最佳值的概率相等.
主要成果:
- 摩尔斯被评估使用指标,如发现的不同最佳数量和解决方案多样性 (平均对式哈明距离,香农).
- 经验结果表明,MORSE的表现优于古罗比方法和未加权的MORSE变异.
- 在混合整数编程库 (MIPLIB) 实例和癌症基因组学组合优化问题上测试了性能.
结论:
- MORSE是一种有效的算法,用于发现ILP的多个不同的最佳解决方案.
- 该方法通过更全面地探索解决方案景观,比传统的解决方案提供了优势.
- 摩尔斯能够产生多种优化的能力对计算生物学,癌症基因组学和其他需要深入分析优化问题的领域的研究有重大影响.
更多相关视频
13:54A Workflow for Lipid Nanoparticle LNP Formulation Optimization using Designed Mixture-Process Experiments and Self-Validated Ensemble Models SVEM
Published on: August 18, 2023
13:04Measuring the Subjective Value of Risky and Ambiguous Options using Experimental Economics and Functional MRI Methods
Published on: September 19, 2012
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Randomized Experiments
Simple randomization
Simple...
Random Error
Linear Approximation in Time Domain
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
Propagation of Uncertainty from Random Error
Routh-Hurwitz Criterion II
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
