SGER: Duality and Warm Starting in Integer Programming

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

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