Abstract: Publication date: Available online 7 November 2019Source: Operations Research LettersAuthor(s): Sven O. Krumke, Huy Minh Le We investigate a robust single machine scheduling-location problem with uncertainty in edge lengths. Jobs are located at the vertices of a given tree. Given a location for a single machine, the jobs travel to the location and are processed there sequentially. The goal is to find a location of the machine and simultaneously a sequence to minimize the makespan value in the worst-case. We use the concept of gamma-robustness to model uncertainty. Our main result is a polynomial time algorithm.

Abstract: Publication date: Available online 5 November 2019Source: Operations Research LettersAuthor(s): Shaojie Tang, Jing Yuan The goal of Influence maximization (IM) is to select a set of most influential users in a social network subject to a budget constraint. In this work, we propose to study the adaptive IM problem under partial-feedback model. Our main contribution in this paper is to introduce a novel adaptive policy with bounded approximation ratio. One nice feature of our policy is that we can balance the delay and performance tradeoff by adjusting the value of a controlling parameter.

Abstract: Publication date: Available online 2 November 2019Source: Operations Research LettersAuthor(s): Yann Disser, Jannik Matuschke The Maximum Robust Flow problem asks for a flow on the paths of a network maximizing the guaranteed amount of flow surviving the removal of any k arcs. We point out a flaw in a previous publication that claimed NP-hardness for this problem when k=2. For the case that k is part of the input, we present a new hardness proof. We also discuss the complexity of the integral version of the problem.

Abstract: Publication date: November 2019Source: Operations Research Letters, Volume 47, Issue 6Author(s): Stefano Coniglio, Fabio D’Andreagiovanni, Fabio Furini We propose an exact lexicographic dynamic programming pricing algorithm for solving the Fractional Bin Packing Problem with column generation. The new algorithm is designed for generating maximal columns of minimum reduced cost which maximize, lexicographically, one of the measures of maximality we investigate. Extensive computational experiments reveal that a column generation algorithm based on this pricing technique can achieve a substantial reduction in the number of columns and the computing time, also when combined with a classical smoothing technique from the literature.

Abstract: Publication date: November 2019Source: Operations Research Letters, Volume 47, Issue 6Author(s): Pasi Lassila, Samuli Aalto We analyze an energy-aware MX/G/1 queue under LAS scheduling with a setup delay and an idle timer that controls the delay before the server enters a sleep state. Through a classical busy period analysis, the expression for the mean conditional delay is derived, which generalizes the earlier well-known result for the ordinary M/G/1-LAS queue. We also analyze the performance-energy tradeoff and show that two well-known cost metrics, weighted sum and product of the mean delay and mean power, are minimized by setting the timer equal to zero or infinite, i.e., a finite idle timer is never used.

Abstract: Publication date: Available online 24 October 2019Source: Operations Research LettersAuthor(s): Shiran Rachmilevitch I present an example of a symmetric repeated game in which an arbitrarily small change in the discount factor can lead to a discontinuous change in the level of symmetry that can be sustained in equilibrium.

Abstract: Publication date: Available online 23 October 2019Source: Operations Research LettersAuthor(s): Xiangyin Kong, Huihui Wang, Xi Chen, Gengzhong Feng This paper investigates a single-product, periodic-review, non-stationary inventory system with total maximum capacity commitment and fixed ordering costs over a finite planning horizon. We characterize the optimal ordering policy as a state-dependent (s,S) policy whose parameters only depend on the sum of the net inventory and the remaining capacity. We show that such policy can degenerate into two simple policies in two special cases respectively. We also derive bounds on parameters of the optimal ordering policy.

Abstract: Publication date: Available online 23 October 2019Source: Operations Research LettersAuthor(s): Onno Boxma, Offer Kella, Liron Ravner We present a model of parallel Lévy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.

Abstract: Publication date: Available online 22 October 2019Source: Operations Research LettersAuthor(s): Anna Castañer, Jesús Marín-Solano, Carmen Ribas We study a class of collusive equilibria in differential games with asymmetric players discounting the future at different rates. For such equilibria, at each moment, weights of players can depend on the state of the system. To fix them, we propose using a bargaining procedure according to which players can bargain again at every future moment. By choosing as threat point the feedback noncooperative outcome, the corresponding solution, if it exists, is agreeable. An exhaustible resource game illustrates the results.

Abstract: Publication date: Available online 19 October 2019Source: Operations Research LettersAuthor(s): Qiulan Zhao, Jinjiang Yuan We consider the single-machine scheduling to tradeoff between the number of tardy jobs and the start time of machine. For this problem, Hoogeveen and T’kindt (2012) proposed an O(n4) algorithm and Gafarov et al. (2010) gave an O(n2) algorithm. In this paper, we present an improved O(nlogn) algorithm. This also provides a new O(nlogn) algorithm for problem 1 ∑Uj.

Abstract: Publication date: Available online 16 October 2019Source: Operations Research LettersAuthor(s): Chengcheng Liu, John J. Hasenbein This paper examines an extension of Naor’s observable queueing model in which the arrival rate is not known with certainty by either customers or the system manager. Further, customers are heterogeneous in terms of their service valuation and waiting time cost. We analyze the stability of the system and properties of the revenue maximizing fee and socially optimal fee.

Abstract: Publication date: Available online 11 October 2019Source: Operations Research LettersAuthor(s): Joey Huchette, Juan Pablo Vielma We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2×(#of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.

Abstract: Publication date: Available online 10 October 2019Source: Operations Research LettersAuthor(s): Erfang Shan, Jiayu Han, Jilei Shi In this paper we introduce a class of efficient extensions of the Myerson value for games with communication graph structures in which the surplus is allocated in proportion to measures defined on the graph. We show that the efficient proportional Myerson values can be characterized by efficiency, coherence with the Myerson value for connected graphs, and α-fairness of surplus. The axiomatization implies a new characterization of the efficient egalitarian Myerson value proposed by van den Brink et al. (2012).

Abstract: Publication date: Available online 8 October 2019Source: Operations Research LettersAuthor(s): Ting-Yu Ho, Shan Liu, Zelda B. Zabinsky We embed an approximate dynamic program into a branch-and-bound framework to solve sequential resource allocation problems in population disease management. The proposed algorithm is capable of providing an optimality guarantee and getting bounds on the optimality gap of healthcare interventions. A numerical study on screening and treatment policy implementation for chronic hepatitis C virus (HCV) infection provides useful insights regarding HCV elimination for baby boomers.

Abstract: Publication date: Available online 5 October 2019Source: Operations Research LettersAuthor(s): Niv Buchbinder, Roy Schwartz, Baruch Weizman Multiway Cut is a classic graph partitioning problem in which the goal is to disconnect a given set of special vertices called terminals. This problem admits a rich sequence of works. Unfortunately, most of these works resort to the mix of multiple algorithmic components, resulting in both complicated algorithms and analysis. We present a simple algorithm for the Multiway Cut problem that is comprised of a single algorithmic component and achieves an approximation of 118=1.375.

Abstract: Publication date: November 2019Source: Operations Research Letters, Volume 47, Issue 6Author(s): Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi This corrigendum provides corrections for several errors in the previously published letter “Heavy-Traffic Asymptotics for Stationary GI/G/1-Type Markov Chains” [Operations Research Letters 40 (2012) 185–189].

Abstract: Publication date: Available online 3 October 2019Source: Operations Research LettersAuthor(s): Vincent Leclère We consider relaxation of almost sure constraint in dynamic stochastic optimization problems and their convergence. We show an epiconvergence result relying on the Kudo convergence of σ-algebras and continuity of the objective and constraint operators. We present classical constraints and objective functions with conditions ensuring their continuity. We are motivated by a Lagrangian decomposition algorithm, known as Dual Approximate Dynamic Programming, that relies on relaxation, and can also be understood as a decision rule approach in the dual.

Abstract: Publication date: Available online 3 October 2019Source: Operations Research LettersAuthor(s): Refail Kasimbeyli, Masoud Karimi The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.

Abstract: Publication date: Available online 26 September 2019Source: Operations Research LettersAuthor(s): N.H. Chieu, T.D. Chuong, V. Jeyakumar, G. Li We present a new copositive Farkas lemma for a general conic quadratic system with binary constraints under a convexifiability requirement. By employing this Farkas lemma, we establish that a minimally exact conic programming relaxation holds for a convexifiable robust quadratic optimization problem with binary and quadratic constraints under a commonly used ellipsoidal uncertainty set of robust optimization. We then derive a minimally exact copositive relaxation for a robust binary quadratic program with conic linear constraints where the convexifiability easily holds.

Abstract: Publication date: Available online 24 September 2019Source: Operations Research LettersAuthor(s): Michela Chessa We define two mechanisms. The first one implements the Shapley value to define some monetary transfers, but it is not incentive compatible. The second one implements only in expectation the same solution and it is a Groves mechanism. While inheriting all the properties of this family, it is also budget-balanced (still in expectation). The trick is to ask the mechanism designer to insert/remove some utility and to take/give it back at the end.

Abstract: Publication date: Available online 23 September 2019Source: Operations Research LettersAuthor(s): Vladimir Dvorkin, Jalal Kazempour, Pierre Pinson We study a competitive electricity market equilibrium with two trading stages, day-ahead and real-time. The welfare of each market agent is exposed to uncertainty (here from renewable energy production), while agent information on the probability distribution of this uncertainty is not identical at the day-ahead stage. We show a high sensitivity of the equilibrium solution to the level of information asymmetry and demonstrate economic, operational, and computational value for the system stemming from potential information sharing.

Abstract: Publication date: Available online 23 September 2019Source: Operations Research LettersAuthor(s): Venus Lo, Huseyin Topaloglu In synergistic assortment optimization, a product’s attractiveness changes as a function of which other products are offered. We represent synergy structure graphically. Vertices denote products. An edge denotes synergy between two products, which increases their attractiveness when both are offered. Finding an assortment to maximize retailer’s expected profit is NP-hard in general. We present efficient algorithms when the graph is a path, a tree, or has low treewidth. We give a linear program to recover the optimal assortment for paths.

Abstract: Publication date: Available online 20 September 2019Source: Operations Research LettersAuthor(s): Matteo Cosmi, Gianpaolo Oriolo, Veronica Piccialli, Paolo Ventura We investigate optimization models for meal delivery that do not involve routing. We focus on the simplest case, with a single restaurant and a single courier, and reduce it to the throughput maximization single machine scheduling problem, with release times and bounded slacks. In the meal delivery setting, slacks are small for QoS purposes and we indeed show the scheduling problem can be solved in polynomial time when slacks are bounded. We discuss extensions to more couriers and restaurants.

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 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 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.