Knowledge that Transforms

In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (cvrp) and the vehicle routing problem with time windows (vrptw) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351–385] for the cvrp. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's vrptw instances and significantly improves the running times of state-of-the-art algorithms for both vrptw and cvrp.

This paper describes an exact algorithm capable of solving large-scale instances of the well-known uncapacitated hub location problem with multiple assignments. The algorithm applies Benders decomposition to a strong path-based formulation of the problem. The standard decomposition algorithm is enhanced through the inclusion of several features such as the use of a multicut reformulation, the generation of strong optimality cuts, the integration of reduction tests, and the execution of a heuristic procedure. Extensive computational experiments were performed to evaluate the efficiency and robustness of the algorithm. Computational results obtained on classical benchmark instances (with up to 200 nodes) and on a new and more difficult set of instances (with up to 500 nodes) confirm the efficiency of the algorithm.

In this paper we study resource allocation problems that involve multiple self-interested parties or players and a central decision maker. We introduce and study the price of fairness, which is the relative system efficiency loss under a “fair” allocation assuming that a fully efficient allocation is one that maximizes the sum of player utilities. We focus on two well-accepted, axiomatically justified notions of fairness, viz., proportional fairness and max-min fairness. For these notions we provide a tight characterization of the price of fairness for a broad family of problems.

Using the well-known product-limit form of the Kaplan-Meier estimator from statistics, we propose a new class of nonparametric adaptive data-driven policies for stochastic inventory control problems. We focus on the distribution-free newsvendor model with censored demands. The assumption is that the demand distribution is not known and there are only sales data available. We study the theoretical performance of the new policies and show that for discrete demand distributions they converge almost surely to the set of optimal solutions. Computational experiments suggest that the new policies converge for general demand distributions, not necessarily discrete, and demonstrate that they are significantly more robust than previously known policies. As a by-product of the theoretical analysis, we obtain new results on the asymptotic consistency of the Kaplan-Meier estimator for discrete random variables that extend existing work in statistics. To the best of our knowledge, this is the first application of the Kaplan-Meier estimator within an adaptive optimization algorithm, in particular, the first application to stochastic inventory control models. We believe that this work will lead to additional applications in other domains.

The pickup and delivery problem with time windows (PDPTW) is a generalization of the vehicle routing problem with time windows. In the PDPTW, a set of identical vehicles located at a central depot must be optimally routed to service a set of transportation requests subject to capacity, time window, pairing, and precedence constraints. In this paper, we present a new exact algorithm for the PDPTW based on a set-partitioning–like integer formulation, and we describe a bounding procedure that finds a near-optimal dual solution of the LP-relaxation of the formulation by combining two dual ascent heuristics and a cut-and-column generation procedure. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between a known upper bound and the lower bound achieved. If the resulting problem has moderate size, it is solved by an integer programming solver; otherwise, a branch-and-cut-and-price algorithm is used to close the integrality gap. Extensive computational results over the main instances from the literature show the effectiveness of the proposed exact method.

Failure of many engineering systems usually results from a gradual and irreversible accumulation of damage, a degradation process. Most degradation processes can be monitored using sensor technology. The resulting degradation signals are usually correlated with the degradation process. A system is considered to have failed once its degradation signal reaches a prespecified failure threshold. This paper considers a replacement problem for components whose degradation process can be monitored using dedicated sensors. First, we present a stochastic degradation modeling framework that characterizes, in real time, the path of a component's degradation signal. These signals are used to predict the evolution of the component's degradation state. Next, we formulate a single-unit replacement problem as a Markov decision process and utilize the real-time signal observations to determine a replacement policy. We focus on exponentially increasing degradation signals and show that the optimal replacement policy for this class of problems is a monotonically nondecreasing control limit policy. Finally, the model is used to determine an optimal replacement policy by utilizing vibration-based degradation signals from a rotating machinery application.

A multiname credit derivative is a security that is tied to an underlying portfolio of corporate bonds and has payoffs that depend on the loss due to default in the portfolio. The value of a multiname derivative depends on the distribution of portfolio loss at multiple horizons. Intensity-based models of the loss point process that are specified without reference to the portfolio constituents determine this distribution in terms of few economically meaningful parameters and lead to computationally tractable derivatives valuation problems. However, these models are silent about the portfolio constituent risks. They cannot be used to address applications that are based on the relationship between portfolio and component risks, for example, constituent risk hedging. This paper develops a method that extends these models to the constituents. We use random thinning to decompose the portfolio intensity into a sum of constituent intensities. We show that a thinning process, which allocates the portfolio intensity to constituents, uniquely exists, and is a probabilistic model for the next-to-default. We derive a formula for the constituent default probability in terms of the thinning process and the portfolio intensity, and develop a semi-analytical transform approach to evaluate it. The formula leads to a calibration scheme for the thinning processes and an estimation scheme for constituent hedge sensitivities. An empirical analysis for September 2008 shows that the constituent hedges generated by our method outperform the hedges prescribed by the Gaussian copula model, which is widely used in practice.

We cast models of the generation capacity expansion type formally developed for the monopoly regime into equilibrium models better adapted for a competitive environment. We focus on some of the risks faced today by investors in generation capacity and thus pose the problem as a stochastic equilibrium model. We illustrate the approach on the problem of the incentive to invest. Agents can be risk neutral or risk averse. We model risk aversion through the CVaR of plants' profit. The CVaR induces risk-adjusted probabilities according to which investors value their plants. The model is formulated as a complementarity problem (including the CVaR valuation of investments). An illustration is provided on a small problem that captures several features of today's electricity world: a choice often restricted to coal and gas units, a peaky load curve because of wind penetration, uncertain fuel prices, and an evolving carbon market. We assess the potential of the approach by comparing energy-only and capacity market organizations in this risky environment. Our results can be summarized as follows: a deterministic analysis overlooks some changes of capacity structure induced by risk, whether in the capacity market or energy-only organizations. The risk-neutral analysis also misses a shift towards less capital-intensive technologies that may result from risk aversion. Last, risk aversion also increases the shortage of capacity compared to the risk-neutral view in the energy-only market when the price cap is low. This may have a dramatic impact on the bill to the final consumer. The approach relies on mathematical programming techniques and can be extended to full-size problems. The results are illustrative and may deserve more investigation.