Abstract: Publication date: Available online 12 September 2019Source: Operations Research LettersAuthor(s): Denis Cornaz, Fabio Furini, Enrico Malaguti, Alberto Santini We extend a one-to-one correspondence between the set of all colorings of any graph and the set of all stable sets of an auxiliary graph, from graphs to partitioned graphs. This correspondence has an application to Selective Coloring and to Selective Max-Coloring.

Abstract: Publication date: Available online 9 September 2019Source: Operations Research LettersAuthor(s): Daniel Bienstock, Abhinav Verma We prove that testing feasibility for an AC power flow system is a strongly NP-hard problem.

Abstract: Publication date: Available online 9 September 2019Source: Operations Research LettersAuthor(s): Mariska Heemskerk, Michel Mandjes This short communication considers an infinite-server system with overdispersed input. The objective is to identify the exact tail asymptotics of the number of customers present at a given point in time under a specific scaling of the model (which involves both the arrival rate and time). The proofs rely on a change-of-measure approach. The results obtained are illustrated by a series of examples.

Abstract: Publication date: Available online 7 September 2019Source: Operations Research LettersAuthor(s): Tao Jiang, Lu Liu, Qingqing Ye, Xudong Chai This study examines service systems with transfers of customers in an alternating environment. We model the service system as a two-server two-parallel queue (primary and auxiliary queues), that has various applications especially in manufacturing and healthcare systems. We establish a sufficient stability condition, and based on the censoring technique, we provide sufficient conditions under which the stationary distribution possesses an exactly geometric tail along the direction of the queue length in the primary queue.

Abstract: Publication date: Available online 7 September 2019Source: Operations Research LettersAuthor(s): Ramez Kian, Emre Berk, Ülkü Gürler In this paper, we consider a particular form of inequalities which involves product of multiple variables with rational exponents. These inequalities can equivalently be represented by a number of conic quadratic forms called cone constraints. We propose an integer programming model and a heuristic algorithm to obtain the minimum number of cone constraints which equivalently represent the original inequality. The performance of the proposed algorithm and the computational effect of reformulations are numerically illustrated.

Abstract: Publication date: Available online 7 September 2019Source: Operations Research LettersAuthor(s): Wenbo Chen, Huixiao Yang Consider-then-choose models, borne out by empirical literature in marketing and psychology, note that customers follow a two-stage procedure to choose among alternatives. In this paper, we consider the assortment optimization problem of a retailer who manages a category of vertically differentiated products under customers’ consider-then-choose behavior. We characterize some structural results of the optimal assortment and find that the problem can be solved as the shortest path problem. Also, we develop an efficient algorithm to identify an optimal assortment.

Abstract: Publication date: Available online 6 September 2019Source: Operations Research LettersAuthor(s): Mathieu Martin, Zéphirin Nganmeni In this note, we focus on a result stated by Bräuninger that the finagle point is within the ϵ -core in a spatial voting game with Euclidean individual preferences. Through a counter-example with 7 players, we show that Bräuninger’s result is not valid.

Abstract: Publication date: Available online 4 September 2019Source: Operations Research LettersAuthor(s): Ying Cao, Zuo-Jun Max Shen In this paper, a single-step framework for predicting quantiles of time series is presented. Subsequently, we propose that this technique can be adopted as a data-driven approach to determine stock levels in the environment of newsvendor problem and its multi-period extension. Theoretical and empirical findings suggest that our method is effective at modeling both weakly stationary and some nonstationary time series. On both simulated and real-world datasets, the proposed approach outperforms existing statistical methods and yields good newsvendor solutions.

Abstract: Publication date: Available online 2 September 2019Source: Operations Research LettersAuthor(s): Vasily V. Gusev, Vladimir V. Mazalov The existence of a Nash-stable coalition structure in cooperative games with the Aumann–Dreze value is investigated. Using the framework of potential functions, it is proved that such a coalition structure exists in any cooperative game. In addition, a similar result is established for some linear values of the game, in particular, the Banzhaf value. For a cooperative game with vector payments, a type of stability based on maximizing the guaranteed payoffs of all players is proposed.

Abstract: Publication date: Available online 17 August 2019Source: Operations Research LettersAuthor(s): Byung-Cheon Choi, Yunhong Min, Myoung-Ju Park We consider a single-machine scheduling problem with generalized and periodic due dates such that each due date is assigned not to a specific job but to a position and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total deviation, which is calculated as the sum of the earliness and tardiness of each job. We show that the problem is strongly NP-hard. We develop a heuristic and verify its performance via experiments.

Abstract: Publication date: Available online 16 August 2019Source: Operations Research LettersAuthor(s): Onno J. Boxma, David Perry, Wolfgang Stadje We explore the relationship between the (S−1,S) inventory model and three well-known queueing models: the Erlang loss system, the machine-repair model and a two-node Jackson network. Exploiting this relationship allows us to obtain key performance measures of the (S−1,S) model, like the so-called virtual outdating time, the number of items on the shelf in steady state, the long-run rate of unsatisfied demands and the distribution of the empty shelf period.

Abstract: Publication date: Available online 9 August 2019Source: Operations Research LettersAuthor(s): Nadav Hallak, Marc Teboulle We propose a method that incorporates a non-Euclidean gradient descent step with a generic matrix sketching procedure, for solving unconstrained, nonconvex, matrix optimization problems, in which the decision variable cannot be saved in memory due to its size, and the objective function is the composition of a vector function on a linear operator. The method updates the sketch directly without updating nor storing the decision variable. Subsequence convergence, global convergence under the Kurdyka–Lojasiewicz property, and rate of convergence, are established.

Abstract: Publication date: Available online 5 August 2019Source: Operations Research LettersAuthor(s): Xiaolong Li, Jiannan Ke We consider robust assortment optimization problems with partial distributional information of parameters in the multinomial logit choice model. The objective is to find an assortment that maximizes a revenue target using a distributionally robust chance constraint, which can be approximated by the worst-case Conditional Value-at-Risk. We show that our problems are equivalent to robust assortment optimization problems over special uncertainty sets of parameters, implying the optimality of revenue-ordered assortments under certain conditions.

Abstract: Publication date: Available online 5 August 2019Source: Operations Research LettersAuthor(s): Kristoffer Lindensjö Control problems not admitting the dynamic programming principle are known as time-inconsistent. The game-theoretic approach is to interpret such problems as intrapersonal dynamic games and look for subgame perfect Nash equilibria. A fundamental result of time-inconsistent stochastic control is a verification theorem saying that solving the extended HJB system is a sufficient condition for equilibrium. We show that solving the extended HJB system is a necessary condition for equilibrium, under regularity assumptions. The controlled process is a general Itô diffusion.

Abstract: Publication date: Available online 25 July 2019Source: Operations Research LettersAuthor(s): Yasuhito Tanaka We study a dynamic free-entry oligopoly with sluggish entry and exit of firms under general demand and cost functions. We show that the number of firms in a steady-state open-loop solution for a dynamic free-entry oligopoly is smaller than that at static equilibrium and that the number of firms in a steady-state memoryless closed-loop solution is larger than that in an open-loop solution.

Abstract: Publication date: Available online 23 July 2019Source: Operations Research LettersAuthor(s): Yanyi Xu, Sang-Phil Kim, Arnab Bisi, Suresh Chand, Maqbool Dada We consider an infinite horizon periodic review base-stock inventory system with discrete demand and lost sales. Every T periods the inventory is reviewed and an order, with arbitrary lead time L, is placed to bring the inventory position to R. Using a recursive Markovian representation, we develop the operating characteristics for any system with positive integer-valued base-stock R, review period T, and lead time L. Then, we develop an algorithm to find the optimal stationary R. Surprisingly, computational results yield the unintuitive findings that the optimal base-stock and cost are not monotone in L given T.

Abstract: Publication date: Available online 19 July 2019Source: Operations Research LettersAuthor(s): E.J. Vanderperre, S.S. Makhanov We analyse the point availability of Gaver’s parallel system supervised by a safety device. For safety reasons, no unit is allowed to operate without supervision. The entire system is attended by two heterogeneous repairmen. Our methodology is based on the theory of sectionally holomorphic functions combined with the notion of dual transforms. As an application we consider Coxian repair time distributions.

Abstract: Publication date: Available online 16 July 2019Source: Operations Research LettersAuthor(s): Sang Won Bae This paper addresses the problem of computing a minimum-width axis-aligned cubic shell enclosing a given set of n points in R3. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior to this work, there was no known algorithm for this problem in the literature. We present the first nontrivial algorithm whose running time is O(nlog2n) in the worst case. Our approach extends to higher dimension d>3, resulting in an algorithm in O(n⌊d∕2⌋logd−1n) expected time.

Abstract: Publication date: Available online 15 July 2019Source: Operations Research LettersAuthor(s): Benjamin Legros We analyze the transient behavior of the M/M/1+D queue. Considering an Erlang distribution for customers’ waiting time, we approximate the real system by a Markov chain. We obtain the Laplace Transform of the transient probabilities in the approximated model and the Laplace transform of the main performance measures for the real system. We next analyze the busy period of this queue. One interesting insight is that the busy period of the unstable M/M/s queue has a finite coefficient of variation.

Abstract: Publication date: September 2019Source: Operations Research Letters, Volume 47, Issue 5Author(s): Shiran Rachmilevitch Kalai and Kalai (2013) presented five axioms for solutions of 2-person semi-cooperative games: games in which the basic data specifies individual strategies and payoffs, but in which the players can sign binding contracts and make utility transfers. The axioms pin down a unique solution, the coco value. I show that if one adds a mild dummy player axiom to the list, then the axioms become inconsistent when there are more than two players.

Abstract: Publication date: September 2019Source: Operations Research Letters, Volume 47, Issue 5Author(s): G. Bergantiños, A. Navarro-Ramos In this paper we provide an axiomatic characterization of the folk rule for minimum cost spanning tree problems with multiple sources. The properties we need are: cone-wise additivity, cost monotonicity, symmetry, isolated agents, and equal treatment of source costs.

Abstract: Publication date: Available online 10 July 2019Source: Operations Research LettersAuthor(s): Jack Brimberg, Zvi Drezner This paper examines a special case of multi-facility location problems where the set of demand points is partitioned into a given number of subsets or clusters that can be treated as smaller independent sub-problems once the number of facilities allocated to each cluster is determined. A dynamic programming approach is developed to determine the optimal allocation of facilities to clusters. The use of clusters is presented as a new idea for designing heuristics to solve general multi-facility location problems.

Abstract: Publication date: Available online 9 July 2019Source: Operations Research LettersAuthor(s): Vijay Kamble I consider a worker’s optimal per-unit-time pricing problem on an on-demand service platform. I establish that if the customer arrival process is Poisson, then any price discrimination must result only from differences in the customers’ willingness-to-pay distributions, and not from differences in their arrival or service-time characteristics. For multiple customer classes that differ in their willingness-to-pay distributions, I present a simple procedure to compute the optimal prices. Finally, I analyze price competition across workers in the presence of reputation effects.

Abstract: Publication date: Available online 3 July 2019Source: Operations Research LettersAuthor(s): Ahmad Abdi, Gérard Cornuéjols A subset of the unit hypercube {0,1}n is cube-ideal if its convex hull is described by hypercube and generalized set covering inequalities. In this note, we study sets S⊆{0,1}n such that, for any subset X⊆{0,1}n of cardinality at most 2, S∪X is cube-ideal.

Abstract: Publication date: Available online 3 July 2019Source: Operations Research LettersAuthor(s): Adam N. Letchford, Georgia Souli The most effective software packages for solving mixed 0-1 linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.

Abstract: Publication date: Available online 24 June 2019Source: Operations Research LettersAuthor(s): Christopher Hojny, Hendrik Lüthen, Marc E. Pfetsch This paper considers integer formulations of binary sets X of minimum sparsity, i.e., the maximal number of non-zeros for each row of the corresponding constraint matrix is minimized. Providing a constructive mechanism for computing the minimum sparsity, we derive sparsest integer formulations of several combinatorial problems, including the traveling salesman problem. We also show that sparsest formulations are NP-hard to separate, while (under mild assumptions) there exists a dense formulation of X separable in polynomial time.

Abstract: Publication date: Available online 20 June 2019Source: Operations Research LettersAuthor(s): Siao-Leu Phouratsamay, T.C.E. Cheng We consider the single-item lot-sizing problem with inventory bounds under a carbon emissions constraint with two options for producing items: regular or green. We wish to find the optimal production plan so that the total carbon emissions from production cannot exceed the carbon emissions capacity in each period. Extending a problem without fixed carbon emissions and inventory bounds, we show that the extended problem is polynomially solvable by a dynamic programming algorithm.

Abstract: Publication date: Available online 18 June 2019Source: Operations Research LettersAuthor(s): Haris Aziz We consider exchange markets with single-unit endowments and demands where there is a bound on the size of the exchange cycles. The computational problem we study is that of computing a Pareto optimal and individually rational allocation. We present polynomial-time algorithms to compute a Pareto optimal and individually rational allocation when preferences are strict, the exchange bound is two, or when Pareto optimality is replaced with weak Pareto optimality.

Abstract: Publication date: Available online 7 June 2019Source: Operations Research LettersAuthor(s): Li Chen, Chengyu Wu In this paper, we show some counter-intuitive observations regarding the open-loop policies in a Bayesian dynamic pricing problem. Specifically, while the common intuition that a policy incorporating more information performs better continues to hold under ample inventory for sale, it breaks down in the case where inventory is limited. This can be explained by the unique feature of selling a limited amount of inventory: information updating may stop prematurely when inventory is depleted, rendering certain demand information being inconsequential.

Abstract: Publication date: Available online 4 June 2019Source: Operations Research LettersAuthor(s): Matthias Walter, Stefan Weltge This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.

Abstract: Publication date: Available online 4 June 2019Source: Operations Research LettersAuthor(s): Franklyn Wang, Ravi Jagadeesan, Scott Duke Kominers We introduce a new model of school choice with reserves in which asocial planner is constrained by a limited supply of reserve seats and tries to find an optimal matching according to a social welfare function. We construct the optimal distribution of reserves via a quartic-time dynamic programming algorithm. Due to the modular nature of the dynamic program, the mechanism is strategy-proof for reserve-eligible students.

Abstract: Publication date: Available online 30 May 2019Source: Operations Research LettersAuthor(s): Yonghui Huang, Zhaotong Lian, Xianping Guo This paper deals with risk-sensitive piecewise deterministic Markov decision processes, where the expected exponential utility of a finite-horizon reward is to be maximized. Both the transition rates and reward functions are allowed to be unbounded. The Feynman–Kac’s formula is developed in our setup, using which along with an approximation technique, we establish the associated Hamilton–Jacobi-Bellman equation and the existence of risk-sensitive optimal policies under suitable conditions.