Knowledge that Transforms

We develop a family of rollout policies based on fixed routes to obtain dynamic solutions to the vehicle routing problem with stochastic demand and duration limits (VRPSDL). In addition to a traditional one-step rollout policy, we leverage the notions of the pre- and post-decision state to distinguish two additional rollout variants. We tailor our rollout policies by developing a dynamic decomposition scheme that achieves high quality solutions to large problem instances with reasonable computational effort. Computational experiments demonstrate that our rollout policies improve upon the performance of a rolling horizon procedure and commonly employed fixed-route policies, with improvement over the latter being more substantial.

It is known that the incorporation of weight restrictions in models of data envelopment analysis may result in their infeasibility. In our paper we investigate this effect in detail. We show that the infeasibility is only one of several possible outcomes that point to a particular problem with weight restrictions. For example, the use of weight restrictions may also lead to zero or negative efficiency scores of some units. Removing problematic units from the data set does not necessarily remove the underlying problem caused by the weight restrictions and only makes it undetected. We prove that all such problems arise when weight restrictions induce free or unlimited production of outputs in the underlying technology. This is unacceptable from the production theory point of view and indicates that the weight restrictions need reassessing. We develop analytical criteria and computational methods that allow us to identify the above problematic situations.

In this paper we discuss multistage programming with the data process subject to uncertainty. We consider a situation where the data process can be naturally separated into two components: one can be modeled as a random process, with a specified probability distribution, and the other one can be treated from a robust (worst-case) point of view. We formulate this in a time consistent way and derive the corresponding dynamic programming equations. To solve the obtained multistage problem, we develop a variant of the stochastic dual dynamic programming method. We give a general description of the algorithm and present computational studies related to planning of the Brazilian interconnected power system.

Modern electronic markets have been characterized by a relentless drive toward faster decision making. Significant technological investments have led to dramatic improvements in latency, the delay between a trading decision and the resulting trade execution. We describe a theoretical model for the quantitative valuation of latency. Our model measures the trading frictions created by the presence of latency, by considering the optimal execution problem of a representative investor. Via a dynamic programming analysis, our model provides a closed-form expression for the cost of latency in terms of well-known parameters of the underlying asset. We implement our model by estimating the latency cost incurred by trading on a human time scale. Examining NYSE common stocks from 1995 to 2005 shows that median latency cost across our sample roughly tripled during this time period. Furthermore, using the same data set, we compute a measure of implied latency and conclude that the median implied latency decreased by approximately two orders of magnitude. Empirically calibrated, our model suggests that the reduction in cost achieved by going from trading on a human time scale to a low latency time scale is comparable with other execution costs faced by the most cost efficient institutional investors, and it is consistent with the rents that are extracted by ultra-low latency agents, such as providers of automated execution services or high frequency traders.

Game-theoretic tools are becoming a popular design choice for distributed resource allocation algorithms. A central component of this design choice is the assignment of utility functions to the individual agents. The goal is to assign each agent an admissible utility function such that the resulting game possesses a host of desirable properties, including scalability, tractability, and existence and efficiency of pure Nash equilibria. In this paper we formally study this question of utility design on a class of games termed distributed welfare games. We identify several utility design methodologies that guarantee desirable game properties irrespective of the specific application domain. Lastly, we illustrate the results in this paper on two commonly studied classes of resource allocation problems: “coverage” problems and “coloring” problems.

Connectivity requirements are a common component of forest planning models, with important examples arising in wildlife habitat protection. In harvest scheduling models, one way of addressing preservation concerns consists of requiring that large contiguous patches of mature forest are maintained. In the context of nature reserve design, it is common practice to select a connected region of forest, as a reserve, in such a way as to maximize the number of species and habitats protected. Although a number of integer programming formulations have been proposed for these forest planning problems, most are impractical in that they fail to solve reasonably sized scheduling instances. We present a new integer programming methodology and test an implementation of it on five medium-sized forest instances publicly available in the Forest Management Optimization Site repository. Our approach allows us to obtain near-optimal solutions for multiple time-period instances in fewer than four hours.

We study optimal bidding strategies for advertisers in sponsored search auctions. In general, these auctions are run as variants of second-price auctions but have been shown to be incentive incompatible. Thus, advertisers have to be strategic about bidding. Uncertainty in the decision-making environment, budget constraints, and the presence of a large portfolio of keywords makes the bid optimization problem nontrivial. We present an analytical model to compute the optimal bids for keywords in an advertiser's portfolio. To validate our approach, we estimate the parameters of the model using data from an advertiser's sponsored search campaign and use the bids proposed by the model in a field experiment. The results of the field implementation show that the proposed bidding technique is very effective in practice. We extend our model to account for interactions between keywords, in the form of positive spillovers from generic keywords into branded keywords. The spillovers are estimated using a dynamic linear model framework and are used to jointly optimize the bids of the keywords using an approximate dynamic programming approach. Accounting for the interaction between keywords leads to an additional improvement in the campaign performance.

The robust capacitated vehicle routing problem (CVRP) under demand uncertainty is studied to address the minimum cost delivery of a product to geographically dispersed customers using capacity-constrained vehicles. Contrary to the deterministic CVRP, which postulates that the customer demands for the product are deterministic and known, the robust CVRP models the customer demands as random variables, and it determines a minimum cost delivery plan that is feasible for all anticipated demand realizations. Robust optimization counterparts of several deterministic CVRP formulations are derived and compared numerically. Robust rounded capacity inequalities are developed, and it is shown how they can be separated efficiently for two broad classes of demand supports. Finally, it is analyzed how the robust CVRP relates to the chance-constrained CVRP, which allows a controlled degree of supply shortfall to decrease delivery costs.