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.**