Search

In Weighted Scoring Rules and Convex Risk Measures, Dr. Zachary J. Smith and Prof. J. Eric Bickel (both at the University of Texas at Austin) present a general connection between weighted proper scoring rules and investment decisions involving the minimization of a convex risk measure. Weighted scoring rules are quantitative tools for evaluating the accuracy of probabilistic forecasts relative to a baseline distribution. In their paper, the authors demonstrate that the relationship between convex risk measures and weighted scoring rules relates closely with previous economic characterizations of weighted scores based on expected utility maximization. As illustrative examples, the authors study two families of weighted scoring rules based on phi-divergences (generalizations of the Weighted Power and Weighted Pseudospherical Scoring rules) along with their corresponding risk measures. The paper will be of particular interest to the decision analysis and mathematical finance communities as well as those interested in the elicitation and evaluation of subjective probabilistic forecasts. This paper establishes a new relationship between proper scoring rules and convex risk measures. Specifically, we demonstrate that the entropy function associated with any weighted scoring rule is equal to the maximum value of an optimization problem where an investor maximizes a concave certainty equivalent (the negation of a convex risk measure). Using this connection, we construct two classes of proper weighted scoring rules with associated entropy functions based on ϕ-divergences. These rules are generalizations of the weighted power and weighted pseudospherical rules. [ABSTRACT FROM AUTHOR]

In this paper, we provide a flexible framework allowing for a unified study of time consistency of risk measures and performance measures (also known as acceptability indices). The proposed framework not only integrates existing forms of time consistency, but also provides a comprehensive toolbox for analysis and synthesis of the concept of time consistency in decision making. In particular, it allows for in-depth comparative analysis of (most of) the existing types of time consistency--a feat that has not been possible before and, which is done in the companion paper by the authors. In our approach, the time consistency is studied for a large class of maps that are postulated to satisfy only two properties--monotonicity and locality. We call these maps LM-measures. The time consistency is defined in terms of an update rule. The form of the update rule introduced here is novel, and is perfectly suited for developing the unifying framework that is worked out in this paper. As an illustration of the applicability of our approach, we show how to recover almost all concepts of weak time consistency by means of constructing appropriate update rules. [ABSTRACT FROM AUTHOR]

This paper proposes a computationally efficient simulation-based optimization (SO) algorithm suitable to address large-scale generally constrained urban transportation problems. The algorithm is based on a novel metamodel formulation. We embed the metamodel within a derivative-free trust region algorithm and evaluate the performance of this SO approach considering tight computational budgets. We address a network-wide traffic signal control problem using a calibrated microscopic simulation model of evening peak period traffic of the full city of Lausanne, Switzerland, which consists of more than 600 links and 200 intersections. We control 99 signal phases of 17 intersections distributed throughout the entire network. This SO problem is a high-dimensional nonlinear constrained problem. It is considered large-scale and complex in the fields of derivative-free optimization, traffic signal optimization, and simulation-based optimization. We compare the performance of the proposed metamodel method to that of a traditional metamodel method and that of a widely used commercial signal control software. The proposed method systematically and efficiently identifies signal plans with improved average city-wide travel times. [ABSTRACT FROM AUTHOR]

Intensive care unit (ICU) beds are valuable resources that are typically in short supply and therefore their effective and efficient use is essential particularly during periods when patient demand is high. In "Allocation of Intensive Care Unit Beds in Periods of High Demand," H. Ouyang, N.T. Argon, and S. Ziya provide insights into what kind of patient prioritization decisions are likely to improve patient health outcomes by analyzing stylized mathematical formulations that capture the fundamental trade-off involved in ICU bed management. They also propose simple policies that are likely to perform well in practice and test them with a simulation study. Findings suggest that even simple policies are likely to bring significant benefits, although more work is needed to investigate whether there could be benefits to using methods that aim to capture patient health condition in a manner that is more precise than assumed in the paper. The objective of this paper is to use mathematical modeling and analysis to develop insights into and policies for making bed allocation decisions in an intensive care unit (ICU) of a hospital during periods when patient demand is high. We first develop a stylized mathematical model in which patients' health conditions change over time according to a Markov chain. In this model, each patient is in one of two possible health stages, one representing the critical and the other representing the highly critical health stage. The ICU has limited bed availability and therefore when a patient arrives and no beds are available, a decision needs to be made as to whether the patient should be admitted to the ICU and if so, which patient in the ICU should be transferred to the general ward. With the objective of minimizing the long-run average mortality rate, we provide analytical characterizations of the optimal policy under certain conditions. Then, based on these analytical results, we propose heuristic methods, which can be used under assumptions that are more general than what is assumed for the mathematical model. Finally, we demonstrate that the proposed heuristic methods work well by a simulation study, which relaxes some of the restrictive assumptions of the mathematical model by considering a more complex transition structure for patient health and allowing for patients to be possibly queued for admission to the ICU and readmitted from the general ward after they are discharged. [ABSTRACT FROM AUTHOR]

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases. [ABSTRACT FROM AUTHOR]

Recommendation stability measures the extent to which a recommendation algorithm provides predictions that are consistent with each other. Several approaches have been proposed in prior work to defining, measuring, and improving the stability of recommendation algorithms. Previous studies have focused primarily on understanding and evaluating recommendation stability in prediction-oriented settings, i.e., recommendation settings where it is crucial to provide the precise prediction of a user's preference rating for an item. However, the research literature has been largely silent on the topic of recommendation stability in other important types of settings, such as classification-oriented (i.e., where it is important to accurately classify the item as relevant versus irrelevant, without having to quantify the user's preference precisely), ranking-oriented (i.e., where it is important to provide accurate relative ranking of items to users), or top-K oriented (i.e., where it is important to suggest K items that are most appealing to the user). Therefore, this paper builds on prior work by generalizing the notion of stability to a broader set of recommendation settings and developing corresponding stability metrics. The paper also provides a comprehensive empirical analysis of classification, ranking, and top-K stability performance of popular recommender algorithms on real-world rating data sets under a variety of settings. [ABSTRACT FROM AUTHOR]

A newsvendor game allows the players to collaborate on inventory pooling and share the resulting total cost. There are several possible ways to allocate the cost. Previous studies have focused on the core of the game. It is known that the core of the newsvendor game is nonempty, and one can use duality theory in stochastic programming to construct an allocation—referred to as the dual-based allocation—belonging to the core. Yet, an allocation that lies in the core does not necessarily guarantee the unhindered formation of a coalition, as some existing members' allocated costs may increase when new members are added in the process. In this work, we use the concept of population monotonic allocation scheme (PMAS), which requires the cost allocated to every member of a coalition to decrease as the coalition grows, to study allocation schemes in a growing population. We show that when the demands faced by the newsvendors are independent, log-concavity of their distributions is sufficient to guarantee the existence of a PMAS. Specifically, for continuous demands, log-concavity ensures that the game is convex, which in turn implies a PMAS exists. We also show that under the same condition the dual-based allocation scheme is a PMAS. For discrete and log-concave demands, however, the game may no longer be convex, but we manage to show that, even so, the dual-based allocation scheme is a PMAS. When the demands are dependent, the game is in general not convex. We derive a sufficient condition based on the dependence structure, measured by the copula, to ensure that the dual-based allocation scheme is still a PMAS. We also include an example of a game with no PMAS. This paper was accepted by Yinyu Ye, optimization. The online appendix is available at https://doi.org/10.1287/mnsc.2018.3053. [ABSTRACT FROM AUTHOR]

In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs. [ABSTRACT FROM AUTHOR]

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets. [ABSTRACT FROM AUTHOR]

We consider small-influence aggregative games with a large number of players n. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria in quasi-linear (in n) number of steps, and the quasi-linear bound is tight. Second, Nash approximate equilibria are played by the dynamic with a limit frequency that is exponentially (in n) close to 1. [ABSTRACT FROM AUTHOR]

In the Anscombe-Aumann setup, we provide conditions for a collection of observations to be consistent with a well-known class of smooth ambiguity preferences (Klibanoff P, Marinacci M, Mukerji S (2005) A smooth model of decision making under ambiguity. Econometrica 73(6):1849-1892.). Each observation is assumed to take the form of an equivalence between an uncertain act and a certain outcome. We provide three results that describe these conditions for data sets of different cardinality. Our findings uncover surprising links between the smooth ambiguity model and classic mathematical results in complex and functional analysis. [ABSTRACT FROM AUTHOR]

Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings. In this paper we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids. [ABSTRACT FROM AUTHOR]

We consider a centralized multisensor online quickest disorder detection problem where the observation from each sensor is a Wiener process gaining a constant drift at a common unobservable disorder time. The objective is to detect the disorder time as quickly as possible with small probability of false alarms. Unlike the earlier work on multisensor change detection problems, we assume that the observer can apply a sequential sensor installation policy. At any time before a disorder alarm is raised, the observer can install new sensors to collect additional signals. The sensors are statistically identical, and there is a fixed installation cost per sensor. We propose a Bayesian formulation of the problem. We identify an optimal policy consisting of a sequential sensor installation strategy and an alarm time, which minimize a linear Bayes risk of detection delay, false alarm, and new sensor installations. We also provide a numerical algorithm and illustrate it on examples. Our numerical examples show that significant reduction in the Bayes risk can be attained compared to the case where we apply a static sensor policy only. In some examples, the optimal sequential sensor installation policy starts with 30% less number of sensors than the optimal static sensor installation policy and the total percentage savings reach to 12%. [ABSTRACT FROM AUTHOR]

We propose and solve a general entrepreneurial/managerial decision-making problem. Instead of employing concave objective functions, we use a broad class of nonconcave objective functions. We approach the problem by a martingale method. We show that the optimization problem with a nonconcave objective function has the same solution as the optimization problem when the objective function is replaced by its concave hull, and thus the problems are equivalent to each other. The value function is shown to be strictly concave and to satisfy the Hamilton-Jacobi-Bellman equation of dynamic programming. We also show that the final wealth cannot take values in the region where the objective function is not concave: the entrepreneur would like to avoid her or his wealth ending up in the nonconcave region. Because of this, the entrepreneur's risk taking explodes as time nears maturity if her his wealth is equal to the right end point of the nonconcave region. [ABSTRACT FROM AUTHOR]

An operator of a network of battery swap stations for electric vehicles must make a long-term investment decision on the number of batteries and charging bays in the system and periodic short-term decisions on when and how many batteries to recharge. Both decisions must be made concurrently, because there exists a trade-off between the long-term investment in batteries and charging bays, and short-term expenses for operating the system. Costs for electric energy as well as demand rates for batteries are stochastic: We consider an infinite time horizon for operation of the system. We derive an optimization problem, which cannot be solved optimally in a reasonable time for real world instances. By optimally solving various small problem instances, we show the mechanics of the model and the influence of its parameters on the optimal cost. We then develop a near-optimal solution heuristic based on Monte Carlo sampling following the ideas of approximate dynamic programming for the infinite horizon dynamic program. We show that operating battery swap stations in a network where lateral transshipments are allowed can substantially decrease expected operating costs. The online appendix is available at https://doi.org/10.1287/trsc.2017.0781 [ABSTRACT FROM AUTHOR]

We use probabilistic methods to characterise time-dependent optimal stopping boundaries in a problem of multiple optimal stopping on a finite time horizon. Motivated by financial applications, we consider a payoff of immediate stopping of "put" type, and the underlying dynamics follows a geometric Brownian motion. The optimal stopping region relative to each optimal stopping time is described in terms of two boundaries, which are continuous, monotonic functions of time and uniquely solve a system of coupled integral equations of Volterra-type. Finally, we provide a formula for the value function of the problem. [ABSTRACT FROM AUTHOR]

We consider two-person zero-sum games where the players control, at discrete times{tn} g induced by a partition Π of R+, a continuous time Markov process. We prove that the limit of the values vΠ exist as the mesh of Π goes to 0. The analysis covers the cases of (1) stochastic games (where both players know the state), and (2) games with unknown state and symmetric signals. The proof is by reduction to deterministic differential games. [ABSTRACT FROM AUTHOR]

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix. [ABSTRACT FROM AUTHOR]

A new approach to solve the continuous-time stochastic inventory problem using the fluctuation theory of Lévy processes is developed. This approach involves the recent developments of the scale function that is capable of expressing many fluctuation identities of spectrally one-sided Lévy processes. For the case with a fixed cost and a general spectrally positive Lévy demand process, we show the optimality of an ( s, S)-policy. The optimal policy and the value function are concisely expressed via the scale function. Numerical examples under a Lévy process in the β-family with jumps of infinite activity are provided to confirm the analytical results. Furthermore, the case with no fixed ordering costs is studied. [ABSTRACT FROM AUTHOR]

We study the mixed capacitated general routing problem (MCGRP) in which a fleet of capacitated vehicles has to serve a set of requests by traversing a mixed weighted graph. The requests may be located on nodes, edges, and arcs. The problem has theoretical interest because it is a generalization of the capacitated vehicle routing problem (CVRP), the capacitated arc routing problem (CARP), and the general routing problem. It is also of great practical interest since it is often a more accurate model for real-world cases than its widely studied specializations, particularly for so-called street routing applications. Examples are urban waste collection, snow removal, and newspaper delivery. We propose a new iterated local search metaheuristic for the problem that also includes vital mechanisms from adaptive large neighborhood search combined with further intensification through local search. The method utilizes selected, tailored, and novel local search and large neighborhood search operators, as well as a new local search strategy. Computational experiments show that the proposed metaheuristic is highly effective on five published benchmarks for the MCGRP. The metaheuristic yields excellent results also on seven standard CARP data sets, and good results on four well-known CVRP benchmarks, including improvement of the best known upper bound for one instance. [ABSTRACT FROM AUTHOR]

A k-club is a subset of vertices of a graph that induces a subgraph of diameter at most k, where k is a positive integer. By definition, 1-clubs are cliques and the model is a distance-based relaxation of the clique definition for larger values of k. The k-club model is particularly interesting to study from a polyhedral perspective as the property is not hereditary on induced subgraphs when k is larger than one. This article introduces a new family of facet-defining inequalities for the 2-club polytope that unifies all previously known facets through a less restrictive combinatorial property, namely, independent (distance) 2-domination. The complexity of separation over this new family of inequalities is shown to be NP-hard. An exact formulation of this separation problem and a greedy separation heuristic are also proposed. The polytope described by the new inequalities (and nonnegativity) is then investigated and shown to be integral for acyclic graphs. An additional family of facets is also demonstrated for cycles of length indivisible by three. The effectiveness of these new facets as cutting planes and the difficulty of solving the separation problem in practice are then investigated via computational experiments on a test bed of benchmark instances. [ABSTRACT FROM AUTHOR]

We consider a nonstationary, stochastic, multistage supply system with a general assembly structure, in which customers can place orders in advance of their future demand requirements. This advance demand information is now recognized in both theory and practice as an important strategy for managing the mismatch between supply and demand. In conjunction, we allow expediting of components and partially completed subassemblies in the system to provide the supply chain with the means to manage the stockout risk and significantly enhance cost savings realized through advance demand information. To solve the resulting assembly system, we develop a new method based on identifying local properties of optimal decisions. This new method allows us to solve assembly systems with multiple product flows. We derive the structure of the optimal policy, which represents a double-tiered echelon basestock policy whose basestock levels depend on the state of advance demand information. This form of the optimal policy allows us to: (i) provide actionable policies for firms to manage large-scale assembly systems with expediting and advance demand information; (ii) prove that advance demand information and expediting of stock both reduce the amount of inventory optimally held in the system; and (iii) numerically solve such assembly systems, and quantify the savings realized. In contrast to the conventional wisdom, we discover that advance demand information and expediting of stock are complementary under short demand information horizons. They are substitutes only under longer information horizons. [ABSTRACT FROM AUTHOR]

We give an algorithmic solution of the optimal consumption problem , where Ct denotes the accumulated consumption until time t, and τ denotes the time of ruin. Moreover, the endowment process Xt is modeled by . We solve the problem by showing that the function provided by the algorithm solves the Hamilton-Jacobi (HJ) equation in a viscosity sense and that the same is true for the value function of the problem. The argument is finished by a uniqueness result. It turns out that one has to change the optimal strategy at a sequence of endowment values, described by a free boundary value problem. Finally we give an illustrative example. [ABSTRACT FROM AUTHOR]

The switching multiple disorder problem seeks to determine an ordered infinite sequence of times of alarms which are as close as possible to the unknown times of disorders, or change-points, at which the observable process changes its probability characteristics. We study a Bayesian formulation of this problem for an observable Brownian motion with switching constant drift rates. The method of proof is based on the reduction of the initial problem to an associated optimal switching problem for a three-dimensional diffusion posterior probability process and the analysis of the equivalent coupled parabolic-type free-boundary problem. We derive analytic-form estimates for the Bayesian risk function and the optimal switching boundaries for the components of the the posterior probability process. [ABSTRACT FROM AUTHOR]

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives. We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle k-matchoid constraints. [ABSTRACT FROM AUTHOR]

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O4n³m² log² n5 iterations if the discount factor is uniform and O4n5m³ log² n5 iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1. [ABSTRACT FROM AUTHOR]

We investigate a game of singular control and strategic exit in a model of competitive market share control. In the model, each player can make irreversible investments to increase his market share, which is modeled as a diffusion process. In addition, each player has an option to exit the market at any point in time. We formulate a verification theorem for best responses of the game and characterize Markov perfect equilibria (MPE) under a set of verifiable assumptions. We find a class of MPEs with a rich structure. In particular, each player maintains up to two disconnected intervals of singular control regions, one of which plays a defensive role, and the other plays an offensive role. We also identify a set of conditions under which the outcome of the game may be unique despite the multiplicity of the equilibria. [ABSTRACT FROM AUTHOR]

We consider a discrete optimization via simulation (DOvS) problem with stochastic constraints on secondary performance measures in which both objective and secondary performance measures need to be estimated by stochastic simulation. To solve the problem, we develop a new method called the Penalty Function with Memory (PFM). It is similar to an existing penalty-type method--which consists of a penalty parameter and a measure of violation of constraints--in a sense that it converts a DOvS problem with constraints into a series of unconstrained problems. However, PFM uses a different penalty parameter, called a penalty sequence, determined by the past history of feasibility checks on a solution. Specifically, assuming a minimization problem, a penalty sequence diverges to infinity for any infeasible solution but converges to zero for any feasible solution under certain conditions. As a result, a DOvS algorithm combined with PFM performs well even when an optimal feasible solution is a boundary solution with one or more active constraints. We prove convergence properties and discuss parameter selection for the implementation of PFM. Experimental results on a number of numerical examples show that a DOvS algorithm combined with PFM works well. [ABSTRACT FROM AUTHOR]