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.