SGER: Duality and Warm Starting in Integer Programming

SGER：整数规划中的对偶性和热启动

• 批准号: 0534862
• 负责人: Theodore Ralphs
• 金额: --
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2006-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0534862&HistoricalAwards=false
• 关键词: SGER; Duality; Warm; Starting; Integer

Large-scale optimization problems arise in a wise variety of important application areas, such as the design of supply chains, logistics networks, telecommunications networks, cancer treatment plans, and pharmaceutical products. Many of the models that arise in these important areas involve variables that must take on integer values. Such models are notoriously difficult to solve and the data that are needed to form the models are rarely known with certainty in advance. Hence, such models are subject to change, even after the solution process is underway. Current solution methods addresses only static models and does not allow for this kind of change. A change to the model once the solution process is underway generally means that the model must be resolved from scratch. This SGER grant provides funding for the development of tools that will help alleviate this problem by providing post-solution sensitivity analysis and resolve capabilities that can be integrated with existing solution algorithms. Such tools will enable the user to either quickly approximate the effect of a given change in the input data on the final solution or to efficiently resolve the problem without starting from scratch.If successful, this work will allow the development of tools for solving difficult, large-scale optimization problems for which the input data are subject to change or for which it is desirable to be able to answer various "what-if" questions after the fact. It will also enable more efficient implementation of various methodologies that require the iterative solution of a series of very similar models. Such methodologies will benefit greatly from the development of the "warm-starting" procedures that we are proposing, which will allow the solution process to be started from an advanced starting point based on information gained from prior solution of a similar model. All of the methodology developed will be implemented and made freely available as open source software in order to reach the widest possible audience

大规模优化问题出现在许多重要的应用领域，如供应链、物流网络、电信网络、癌症治疗计划和药品的设计。在这些重要领域中出现的许多模型都涉及必须采用整数值的变量。众所周知，这样的模型很难求解，而形成模型所需的数据也很少能事先确定。因此，即使在解决方案过程进行之后，这样的模型也会发生变化。当前的解决方案方法只处理静态模型，不允许这种类型的更改。一旦解决方案流程正在进行，对模型的更改通常意味着必须从头开始解决模型。SGER拨款为工具的开发提供资金，通过提供解决方案后的敏感性分析和解决能力，可以与现有的解决方案算法集成，从而帮助缓解这个问题。这些工具将使用户能够快速估计输入数据中给定更改对最终解决方案的影响，或者无需从头开始就能有效地解决问题。如果成功，这项工作将允许开发工具来解决困难的、大规模的优化问题，这些问题的输入数据可能会发生变化，或者希望能够在事实之后回答各种“假设”问题。它还能够更有效地实现各种方法，这些方法需要对一系列非常相似的模型进行迭代解决。这些方法将极大地受益于我们提出的“预热启动”程序的发展，这将允许基于从类似模型的先前解中获得的信息从高级起点开始求解过程。所开发的所有方法都将作为开源软件实现并免费提供，以便接触到尽可能广泛的受众