Better algorithms for discrete optimization, with applications

许多重要的业务活动可以有效地表示为优化模型，在这些模型中，我们希望找到一些决策变量的最佳可能的可行值，以最大化或最小化某个目标函数。这些模型中一个具有挑战性但很重要的子集要求决策变量只取整数值。这类“离散优化”问题通常是困难的，但在许多特殊情况下，可以证明一个相当简单的模型保证了整数最优解。*不幸的是，在许多这种情况下，还不知道如何有效地找到这样的整数最优解。这项拟议的研究大多致力于扩展我们可以有效地找到此类解决方案的问题类别。一个重要的类别来自一种称为子模的凸性的离散模拟，它类似于经济学中的互补性。我建议研究如何更快地优化子模块结构，在参数优化中使用子模块，并表征包含子模块的供应链结构。*另一类重要的类别来自网络中的流。我建议使用网络流方法来寻找“分离算法”的算法，即作为一种方法来解决在解决更困难的问题时出现的更容易的子问题。这也涉及到参数和子模块问题。*这项研究的另一部分涉及竞争零售商有过剩需求的情况，这些需求可以由客户或零售商来满足，这些零售商安排不满意的客户从另一家确实有库存的商店获得产品。这种可能性如何影响市场中的激励、合同和价格？我们的研究旨在回答这些问题。**

Many important business activities can usefully be represented as optimization models where we want to find the best possible feasible values of some decision variables that maximize or minimize some objective function. A challenging but important subset of these models require that the decision variables take only integer values. Such "discrete optimization" problems are provably hard in general, but there are many special cases where it can be proved that a fairly simple model has guaranteed integer optimal solutions.****Unfortunately, in many of these cases it is not yet known how to efficiently find such integer optimal solutions. Much of this proposed research is dedicated to extending the classes of problems where we can efficiently find such solutions. One important class comes from a discrete analog of convexity called submodularity, which is similar to complementarity in economics. I propose to investigate how to optimize submodular structures faster, use submodularity in parametric optimization, and to characterize supply chain structures containing submodularity.****Another important class comes from flows in networks. I propose to use network flow methods to find algorithms for "separation algorithms", i.e, as a way of solving easier subproblems that arise when solving more difficult problems. This also connects to parametric and submodular problems. ****Another part of this research concerns situations where competing retailers have excess demand that can be satisfied by either customers or the retailers arranging that unsatisfied customers get the product from another store that does have stock available. How does this possibility affect incentives, contracts, and prices in the marketplace? Our research aims to answer such questions.**