Knowledge that Transforms

Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting recharging stations during the course of a route. In this paper, we consider four variants of the electric vehicle-routing problem with time windows: (i) at most a single recharge per route is allowed, and batteries are fully recharged on visit of a recharging station; (ii) multiple recharges per route, full recharges only; (iii) at most a single recharge per route, and partial battery recharges are possible; and (iv) multiple, partial recharges. For each variant, we present exact branch-price-and-cut algorithms that rely on customized monodirectional and bidirectional labeling algorithms for generating feasible vehicle routes. In computational studies, we find that all four variants are solvable for instances with up to 100 customers and 21 recharging stations. This success can be attributed to the tailored resource extension functions (REFs) that enable efficient labeling with constant time feasibility checking and strong dominance rules, even if these REFs are intricate and rather elaborate to derive. The studies also highlight the superiority of the bidirectional labeling algorithms compared to the monodirectional ones. Finally, we find that allowing multiple as well as partial recharges both help to reduce routing costs and the number of employed vehicles in comparison to the variants with single and with full recharges.

Robust optimization is a methodology that has gained a lot of attention in the recent years. This is mainly due to the simplicity of the modeling process and ease of resolution even for large scale models. Unfortunately, the second property is usually lost when the cost function that needs to be “robustified” is not concave (or linear) with respect to the perturbing parameters. In this paper we study robust optimization of sums of piecewise linear functions over polyhedral uncertainty set. Given that these problems are known to be intractable, we propose a new scheme for constructing conservative approximations based on the relaxation of an embedded mixed-integer linear program and relate this scheme to methods that are based on exploiting affine decision rules. Our new scheme gives rise to two tractable models that, respectively, take the shape of a linear program and a semidefinite program, with the latter having the potential to provide solutions of better quality than the former at the price of heavier computations. We present conditions under which our approximation models are exact. In particular, we are able to propose the first exact reformulations for a robust (and distributionally robust) multi-item newsvendor problem with budgeted uncertainty set and a reformulation for robust multiperiod inventory problems that is exact whether the uncertainty region reduces to a L1-norm ball or to a box. An extensive set of empirical results will illustrate the quality of the approximate solutions that are obtained using these two models on randomly generated instances of the latter problem.

We consider a seller’s problem of determining revenue-maximizing prices for an assortment of products that exhibit network effects. Customers make purchase decisions according to a multinomial logit choice model, modified—to incorporate network effects—so that the utility each individual customer gains from purchasing a particular product depends on the market’s total consumption of that product. In the setting of homogeneous products, we show that if the network effect is comparatively weak, then the optimal pricing decision of the seller is to set identical prices for all products. However, if the network effect is strong, then the optimal pricing decision is to set the price of one product low and to set the prices of all other products to a single high value. This boosts the sales of the single low-price product in comparison to the sales of all other products. We also obtain comparative statics results that describe how optimal prices and sales levels vary with a parameter that determines the strength of the network effects. We extend our analysis to settings with heterogeneous products and establish that optimal solutions have a structure similar to that found in the homogeneous case: either maintain a semblance of balance among all products or boost the sales of just one product. Based on this structure, we propose an effective computational algorithm for such general heterogeneous settings.

We develop a new approach for solving the optimal retirement problem for an individual with an unhedgeable income risk. The income risk stems from a forced unemployment event, which occurs as an exponentially distributed random shock. The optimal retirement problem is to determine an individual’s optimal consumption and investment behaviors and optimal retirement time simultaneously. We introduce a new convex-duality approach for reformulating the original retirement problem and provide an iterative numerical method to solve it. Reasonably calibrated parameters say that our model can give an explanation for lower consumption and risky investment behaviors of individuals, and for relatively higher stock holdings of the poor. We also analyze the sensitivity of an individual’s optimal behavior in changing her wealth level, investment opportunity, and the magnitude of preference for postretirement leisure. Finally, we find that our model explains a countercyclical pattern of the number of unemployed job leavers.

We consider a market in which suppliers with asymmetric capacities and asymmetric marginal and fixed costs compete to satisfy a deterministic and inelastic demand of a commodity in a single period. The suppliers bid their costs to an auctioneer who determines the optimal allocation and the resulting payments, a typical situation in deregulated electricity markets. Under classical marginal-cost pricing, the nonconvexity of the total cost may result in losses for some suppliers because they may fail to recover their fixed cost through commodity payments only. To address this problem, various pricing schemes that lift the price above marginal cost and/or provide side-payments (uplifts) have been proposed in the literature. We review several of these schemes, also proposing a new variant, in a two-supplier setting. We derive closed-form expressions for the price, uplifts, and profits that each scheme generates that enable us to analytically compare these schemes along these three dimensions. Our analysis complements known numerical comparisons available in the literature. We extend some of our analytical comparisons to the case of more than two suppliers and discuss extant numerical comparisons for this case. Further, we present known results concerning the potential for supplier strategic bidding behavior in the context of the considered pricing schemes, emphasizing when possibilities for market manipulation exist.

In this paper we consider the notion of rectangularity of a set of probability measures from a somewhat different point of view. We define rectangularity as a property of dynamic decomposition of a distributionally robust stochastic optimization problem and show how it relates to the modern theory of coherent risk measures. Consequently, we discuss robust formulations of multistage stochastic optimization problems in frameworks of stochastic programming, stochastic optimal control, and Markov decision processes.

This paper attempts to provide a decision-theoretic foundation for the measurement of economic tail risk, which is not only closely related to utility theory but also relevant to statistical model uncertainty. The main result is that the only risk measures that satisfy a set of economic axioms for the Choquet expected utility and the statistical property of general elicitability (i.e., there exists an objective function such that minimizing the expected objective function yields the risk measure) are the mean functional and value-at-risk (VaR), in particular the median shortfall, which is the median of tail loss distribution and is also the VaR at a higher confidence level. We also discuss various approaches of backtesting and their relations to elicitability and co-elicitability; in particular, we show that the co-elicitability of VaR and expected shortfall does not lead to a reliable backtesting method for expected shortfall and there have been only indirect backtesting methods for expected shortfall. Furthermore, we extend the result to address model uncertainty by incorporating multiple scenarios. As an application, we argue that median shortfall is a better alternative than expected shortfall for setting capital requirements in Basel Accords.

We propose a new and systematic reformulation and algorithmic approach to solve a complex class of stochastic programming problems involving a joint chance constraint with random technology matrix and stochastic quadratic inequalities. The method is general enough to apply to nonconvex as well as nonseparable quadratic terms. We derive two new reformulations and give sufficient conditions under which the reformulated problem is equivalent. The second reformulation provides a much sparser representation of the feasible set of the chance constraint and offers tremendous computational advantages. This new reformulation method can be used for linear stochastic inequalities and will also significantly improve the solution of such joint chance-constrained problems. We provide general and easily identifiable conditions under which the base reformulations can be linearized. We show that the size of the reformulated problems, in particular, their number of binary variables and quadratic mixed-integer terms, does not grow linearly with the number of scenarios used to represent uncertainty. We propose two new nonlinear branch-and-bound algorithms for the nonconvex quadratic integer reformulations. We present detailed empirical results, comparing the various reformulations and several algorithmic ideas that improve the performance of the mixed-integer nonlinear solver Couenne for solving these problems. Guidelines on how to tune the solver and to select reformulations are presented. The test instances are epidemiology and disaster management facility location models and cover the three types of stochastic quadratic inequalities, namely, product of two decision variables that are both binary, binary and continuous, or both continuous.

This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in the literature: (i) their solution quality is extremely close to that of the standard SDP relaxation (the best one is within 99.96% of the SDP relaxation on average for all the IEEE test cases) and consistently outperforms previously proposed convex quadratic relaxations of the OPF problem, (ii) the solutions from the strong SOCP relaxations can be directly used as a warm start in a local solver such as IPOPT to obtain a high quality feasible OPF solution, and (iii) in terms of computation times, the strong SOCP relaxations can be solved an order of magnitude faster than the standard SDP relaxation. For example, one of the proposed SOCP relaxations together with IPOPT produces a feasible solution for the largest instance in the IEEE test cases (the 3375-bus system) and also certifies that this solution is within 0.13% of global optimality, all this computed within 157.20 seconds on a modest personal computer. Overall, the proposed strong SOCP relaxations provide a practical approach to obtain feasible OPF solutions with extremely good quality within a time framework that is compatible with the real-time operation in the current industry practice.

We present an exact characterization of utilities in competitive equilibria of two-sided matching markets in which the utility of each agent depends on the choice of partner and the terms of the partnership, potentially including monetary transfer. Examples of such markets include sellers and buyers or jobs and workers. Demange and Gale showed that the set of competitive equilibria in this type of market forms a complete lattice with each extreme point of the lattice representing an equilibrium with the highest utilities for the agents on one side and the lowest utilities for the agents on the opposite side. Our characterization is based on establishing a connection between the competitive equilibria of a market and the competitive equilibria of certain strict subsets of that market—each obtained by removing exactly one agent. This characterization captures the effect of competition when agents are added to the market or removed from the market. It gives a precise procedure for constructing competitive equilibria and provides a constructive proof of existence of such equilibria; in contrast, previous proofs have been based on fixed point theorems.