Operations Research

Biologically Inspired Parent Selection in Genetic Algorithms Abstract In this paper we suggest a new rule for parent selection in genetic algorithms inspired by natural evolutionary processes. The new rule is simple to implement in any genetic or hybrid genetic algorithm. We also review some biological principles that inspire genetic algorithms and their extensions. The new rule is tested on the planar p-median problem, also termed the location–allocation problem or the multi-source Weber problem, and the quadratic assignment problem. The genetic algorithm incorporating the new rule provided better results without increasing the computing time including five new best known solutions to well researched problem instances.

Detecting bubbles in Bitcoin price dynamics via market exuberance Abstract Empirical evidence suggests the presence of bubble effects on Bitcoin price dynamics during its lifetime, starting in 2009. Previous research, mostly empirical, focused on statistical tests in order to detect a bubble behavior at some point in time. Few exceptions suggested specific time series models capable to describe such phenomena. We contribute this stream of literature by considering a continuous time stochastic model for Bitcoin dynamics, depending on a market attention factor, which is proven to boost in a bubble under suitable conditions. Here, we define a bubble following the theory of mathematical bubbles introduced by Philip E. Protter and coauthors. Specifically, we prove that the presence of a bubble is related to the correlation between the market attention factor on Bitcoin and Bitcoin returns being above a threshold, i.e. when marked attention affects Bitcoin prices and converse, creating a vicious loop. This phenomenon has been labelled market exuberance by Robert J. Shiller, recipient of the 2013 Nobel prize in Economic Sciences. The model is fitted on historical data of Bitcoin prices, by considering either the total trading volumeor the Google Search Volume Index as proxies for the attention measure. According to our numerical results, a bubble effect is evidenced in the early years of Bitcoin introduction, namely 2012–2013, as well as in the recent race of 2017.

Excessive backlog probabilities of two parallel queues Abstract Let X be the constrained random walk on \({\mathbb Z}_+^2\) with increments (1, 0), \((-1,0)\) , (0, 1) and \((0,-1)\) ; X represents, at arrivals and service completions, the lengths of two queues (or two stacks in computer science applications) working in parallel whose service and interarrival times are exponentially distributed with arrival rates \(\lambda _i\) and service rates \(\mu _i\) , \(i=1,2\) ; we assume \(\lambda _i < \mu _i\) , \(i=1,2\) , i.e., X is assumed stable. Without loss of generality we assume \(\rho _1 =\lambda _1/\mu _1 \geqslant \rho _2 = \lambda _2/\mu _2\) . Let \(\tau _n\) be the first time X hits the line \(\partial A_n = \{x \in {\mathbb Z}^2:x(1)+x(2) = n \}\) , i.e., when the sum of the components of X equals n for the first time. Let Y be the same random walk as X but only constrained on \(\{y \in {{\mathbb {Z}}}^2: y(2)=0\}\) and its jump probabilities for the first component reversed. Let \(\partial B =\{y \in {{\mathbb {Z}}}^2: y(1) = y(2) \}\) and let \(\tau \) be the first time Y hits \(\partial B\) . The probability \(p_n = P_x(\tau _n < \tau _0)\) is a key performance measure of the queueing system (or the two stacks) represented by X (if the queues/stacks share a common buffer, then \(p_n\) is the probability that this buffer overflows during the system’s first busy cycle). Stability of the process implies that \(p_n\) decays exponentially in n when the process starts off the exit boundary \(\partial A_n.\) We show that, for \(x_n= \lfloor nx \rfloor \) , \(x \in {{\mathbb {R}}}_+^2\) , \(x(1)+x(2) \leqslant 1\) , \(x(1) > 0\) , \(P_{(n-x_n(1),x_n(2))}( \tau < \infty )\) approximates \(P_{x_n}(\tau _n < \tau _0)\) with exponentially vanishing relative error. Let \(r = (\lambda _1 + \lambda _2)/(\mu _1 + \mu _2)\) ; for \(r^2 < \rho _2\) and \(\rho _1 \ne \rho _2\) , we construct a class of harmonic functions from single and conjugate points on a related characteristic surface for Y with which the probability \(P_y(\tau < \infty )\) can be approximated with bounded relative error. For \(r^2 = \rho _1 \rho _2\) , we obtain the exact formula \(P_y(\tau < \infty ) = r^{y(1)-y(2)} +\frac{r(1-r)}{r-\rho _2}\left( \rho _1^{y(1)} - r^{y(1)-y(2)} \rho _1^{y(2)}\right) .\)

Scheduling a forge with due dates and die deterioration Abstract In this paper a new scheduling problem is presented, which originates from the steel processing industry. The optimal scheduling of a steel forge is investigated with the goal of minimizing setup and storage costs under strict deadlines and special resource constraints. The main distinctive feature of the problem is the deterioration of some equipment, in this case, the so-called forging dies. While the aging effect has been widely investigated in scheduling approaches, where production speed decreases through time, durability deterioration caused by equipment setup has not been addressed yet. In this paper a mixed-integer linear programming model is proposed for solving the problem. The model uses a uniform discrete time representation and resource-balance constraints based on the resource–task network model formulation method. The proposed method was tested on 3-week long schedules based on real industrial scenarios. Computational results show that the approach is able to provide optimal short-term schedules in reasonable time.

Minimum cost edge blocker clique problem Abstract Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold \(\tau >0\) , the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges so that each clique’s weight is bounded above by \(\tau \) . Clusters composed of important actors with quick communications can be effectively modeled as large-weight cliques in real-world settings such as social, communication, and biological systems. Here, we prove that EBCP is NP-hard even when \(\tau \) is a fixed parameter, and propose a combinatorial lower bound for its optimal objective. A class of inequalities that are valid for the set of feasible solution to EBCP is identified, and sufficient conditions for these inequalities to induce facets are presented. Using this class of inequalities, EBCP is formulated as a linear 0–1 program including potentially exponential number of constraints. We develop the first problem-specific branch-and-cut algorithm to solve EBCP, which utilizes the aforementioned constraints in a lazy manner. We also developed the first combinatorial branch-and-bound solution approach for this problem, which aims to handle large graph instances. Finally, computational results of solving EBCP on a collection of random graphs and power-law real-world networks by using our proposed exact algorithms are also provided.

How entry crowds and grows markets: the gradual disaster management view of market dynamics in the retail industry Abstract Entrepreneurial, innovative entry can have devastating effects disrupting a market. However, the many players involved including all current producers, sellers and suppliers and the often non-technological but organizational nature of the innovation may lead to a gradual restoration of the market, viz., to a new equilibrium. Entrepreneurial entry can be regarded as a disaster while the restoration towards a new equilibrium as disaster management. Hardly any empirical models have been developed in order to test these ideas. This paper conducts the first empirical dynamic simultaneous equilibrium analysis of the role of entry and exit of firms, the number of firms in an industry, and profit levels in industry dynamics. Our model enables to discriminate between the entrants’ entrepreneurial function of creating disequilibrium and their conventional role of moving the industry to a new equilibrium. Using a rich data set of the retail industry, we find that indeed entrants perform an entrepreneurial function causing long periods of disequilibrium after which a new equilibrium is attained. Notably, shocks to the entry rate have permanent effects on the industry, emphasizing the entrepreneurial function of entrants rather than their passive reactive function as postulated in classical economics.

A two-stage intervened decision system with multi-state decision units and dynamic system configuration Abstract This paper develops the performability and cost–benefit models for a two-stage intervened decision system with majority voting rule and binary input and output. The decision process of the system contains two stages: an inspection stage (stage 1) and a result submission stage (stage 2). During the first stage, each decision unit in the system will have multiple states and a supervisor will come to visit each unit and check its state for at most twice. The supervisor will conduct the first visit to each unit for certain. However, the behavior of the second visit to each unit will be determined by its state during the first visit. In addition, each decision unit may be removed from the system given certain states during each visit. Therefore the structure of system may change during the decision process. The units which are not removed during the first stage can submit the result at any time during the second stage. However, the performance of each remaining unit will be determined by the ending state of the first stage. Moreover, in order to improve the efficiency of the decision process, a check point is added to the second stage. The performability and cost–benefit models for this dynamic system are developed by considering the distribution of states at the end of the first stage. A three-step method will be proposed for model optimization. Some numerical examples for the three-step method will be presented. The proposed intervened decision system in this paper can be applied in many contexts such as financial investment, paper submission review and proposal evaluation, credit evaluation and loan application and product release and recall.

Estimating criteria weight distributions in multiple criteria decision making: a Bayesian approach Abstract A common way to model decision maker (DM) preferences in multiple criteria decision making problems is through the use of utility functions. The elicitation of the parameters of these functions is a major task that directly affects the validity and practical value of the decision making process. This paper proposes a novel Bayesian method that estimates the weights of criteria in linear additive utility functions by asking the DM to rank or select the best alternative in groups of decision alternatives. Our method computes the entire probability distribution of weights and utility predictions based on the DM’s answers. Therefore, it enables the DM to estimate the expected value of weights and predictions, and the uncertainty regarding these values. Additionally, the proposed method can estimate the weights by asking the DM to evaluate few groups of decision alternatives since it can incorporate various types of inputs from the DM in the form of rankings, constraints and prior distributions. Our method successfully estimates criteria weights in two case studies about financial investment and university ranking decisions. Increasing the variety of inputs, such as using both ranking of decision alternatives and constraints on the importance of criteria, enables our method to compute more accurate estimations with fewer inputs from the DM.

Axiomatizations of inconsistency indices for triads Abstract Pairwise comparison matrices often exhibit inconsistency, therefore many indices have been suggested to measure their deviation from a consistent matrix. A set of axioms has been proposed recently that is required to be satisfied by any reasonable inconsistency index. This set seems to be not exhaustive as illustrated by an example, hence it is expanded by adding two new properties. All axioms are considered on the set of triads, pairwise comparison matrices with three alternatives, which is the simplest case of inconsistency. We choose the logically independent properties and prove that they characterize, that is, uniquely determine the inconsistency ranking induced by most inconsistency indices that coincide on this restricted domain. Since triads play a prominent role in a number of inconsistency indices, our results can also contribute to the measurement of inconsistency for pairwise comparison matrices with more than three alternatives.

Trimmed fuzzy clustering of financial time series based on dynamic time warping Abstract In finance, cluster analysis is a tool particularly useful for classifying stock market multivariate time series data related to daily returns, volatility daily stocks returns, commodity prices, volume trading, index, enhanced index tracking portfolio, and so on. In the literature, following different methodological approaches, several clustering methods have been proposed for clustering multivariate time series. In this paper by adopting a fuzzy approach and using the Partitioning Around Medoids strategy, we suggest to cluster multivariate financial time series by considering the dynamic time warping distance. In particular, we proposed a robust clustering method capable to neutralize the negative effects of possible outliers in the clustering process. The clustering method achieves its robustness by adopting a suitable trimming procedure to identify multivariate financial time series more distant from the bulk of data. The proposed clustering method is applied to the stocks composing the FTSE MIB index to identify common time patterns and possible outliers.