Abstract: Abstract We consider a risk-sensitive continuous-time Markov decision process over a finite time duration. Under the conditions that can be satisfied by unbounded transition and cost rates, we show the existence of an optimal policy, and the existence and uniqueness of the solution to the optimality equation out of a class of possibly unbounded functions, to which the Feynman–Kac formula was also justified to hold. PubDate: 2019-12-01
Abstract: Abstract The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of \(n \ge 4\) data objects and their pairwise costs (or distances), one wants to construct an optimal tree from the \(3 \cdot {n \atopwithdelims ()4}\) quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem. PubDate: 2019-12-01
Abstract: Abstract Automated Guide Vehicles (AGVs) are widely used in material handling systems. In practice, to achieve more space utilization, safety, cost reduction, and increased flexibility, only a limited number of manufacturing cells may be preferred to have direct access to AGV travel paths, and the other cells are chosen to have no or indirect access to them. This paper investigates the problem of determining a single loop in a block layout with two criteria: loop length and loop-adjacency desirability. Unlike the traditional single shortest loop design problem, where all cells must be located next to the loop, the proposed problem considers a more realistic assumption that each cell in the block layout has a different preference with regard to being adjacent to the loop: some cells must be located adjacent to the loop, some must not be adjacent to the loop, and others can be located next to the loop but with different positive or negative priorities. The problem is formulated as a bi-objective integer linear programming model with two exponential-size constraint sets. A cutting-plane algorithm is proposed to solve the model under important methods commonly used to deal with a bi-objective model. The numerical results show the high efficiency of the proposed algorithm in large scales. PubDate: 2019-12-01
Abstract: Abstract Quantum Bridge Analytics relates generally to methods and systems for hybrid classical-quantum computing, and more particularly is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the first of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications, with an emphasis on supplementing models with numerical illustrations. In Part 1 (the present paper) we focus on the Quadratic Unconstrained Binary Optimization model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems. PubDate: 2019-11-26
Abstract: Abstract This paper investigates how the production policy, as well as other factors, affect the facility location-allocation decisions. We focus on a p-median location problem in which one single perishable product is to be produced and shipped to a set of users. The time-correlated demands of the clients are generated by autoregressive processes, and they are forecasted from historical data. Empirically, we show that: (i) embedding the production policy in the location-allocation decision problem may lead to a facilities-clients assignment which does not necessarily correspond to the minimum cost allocation, but produces better profits, (ii) taking into account the autocorrelation of the demand can significantly improve the performance of the supply chain, and (iii) the variability of the demand strongly affects the performance of the supply chain, so a careful choice of production strategy is especially recommended in this case. PubDate: 2019-11-21
Abstract: Abstract We introduce the Chinese deliveryman problem where the goal of the deliveryman is to visit every house in his neighborhood such that the average time of arrival is minimized. We show that, in contrast to the well-known Chinese postman problem, the Chinese deliveryman problem is APX-hard in general and NP-hard for planar graphs. We give a simple \(\sqrt{2}\) -approximation for undirected graphs and a 4 / 3-approximation for 2-edge connected graphs. We observe that there is a PTAS for planar graphs and that depth first search is optimal for trees. PubDate: 2019-10-19
Abstract: Abstract Different grids of points to solve cutting and packing problems with rectangular shaped items are discussed in this work. The grids are the canonical dissections (also known as normal patterns), useful numbers, reduced raster points, regular normal patterns, and meet-in-the-middle patterns. Theoretical results involving the size and subset relations among the grids are proposed, besides practical procedures to reduce the size. Computational experiments are performed in which the two-dimensional (2D) knapsack problem is solved with an integer linear programming model. The results show the impact on the grids before and after applying the reduction procedures, concluding that the reduced raster points and meet-in-the-middle patterns are generally the grids with the smallest number of points. PubDate: 2019-09-24
Abstract: Abstract Based on a singular value analysis conducted on the Dai–Liao conjugate gradient method, it is shown that when the gradient approximately lies in the direction of the maximum magnification by the search direction matrix, the method may get into some computational errors and also, the convergence may occur hardly. Hence, we obtain a formula for computing the Dai–Liao parameter which makes the direction of the maximum magnification by the search direction matrix to be orthogonal to the gradient. We briefly discuss global convergence of the corresponding Dai–Liao method with and without convexity assumption on the objective function. Numerical experiments on a set of test problems of the CUTEr collection show practical effectiveness of the suggested adaptive choice of the Dai–Liao parameter in the sense of the Dolan–Moré performance profile. PubDate: 2019-09-01
Abstract: Abstract This paper examines the long-term impact of loyalty programs on a company’s profit and reputation among customers, and with different durations of product use. We analyze how the launch of loyalty programs may change the profitability of optimal advertising activities. The basis of this study is a modified goodwill model where the market is segmented according to usage experience. The main novelty is the role of loyalty programs and consumer recommendations in the creation of product goodwill, and also their influence on optimal advertising. The dynamics of goodwill are described by a partial differential equation. The firm maximizes the sum of discounted profits by choosing a different advertising campaign for each market segment. For a high-quality product, we observe that there is a trade off between the loyalty program and optimal advertising strategies. For a low-quality product, the loyalty program causes more profitable companies to invest heavily in additional advertising efforts. PubDate: 2019-09-01
Abstract: Abstract We propose a two-phase heuristic for the generalized assignment problem (GAP). The first phase—a generic variable-fixing method—heuristically eliminates up to 98% of the variables without sacrificing the solution quality. The second phase takes as input the small reduced GAP obtained during the first phase and applies a very large scale neighborhood search. The definition of the successive exponential size neighborhoods is guided by the subgradient method applied to the Lagrangian relaxation of the knapsack constraints via the reduced costs. Searching the proposed neighborhood is NP-hard and amounts to solving a monotone binary program (BP) with m constraints and p variables, where m and p are respectively the number of agents and tasks of the reduced GAP (monotone BPs are BPs with two nonzero coefficients of opposite sign per column). To the best of our knowledge, this is the first time the above ideas are exposed. Extensive testing on large scale GAP instances is presented and previously unknown better values for eight instances are obtained. Comparison to well-established methods shows that this new approach is competitive and constitutes a substantial addition to the arsenal of tools for solving GAP. PubDate: 2019-09-01
Abstract: Abstract The line planning problem that arises in the planning of a passenger railway involves selecting a number of lines from a potential pool to provide sufficient passenger capacity, meeting operational requirements, while optimising some measure of line quality. We model, and solve, the problem of minimising the average passenger system time, including frequency-dependent estimates for switching between lines in collaboration with Danish State Railways (DSB). We present a multi-commodity flow formulation for the problem of freely routing passengers, coupled to discrete line-frequency decisions selecting lines from a predefined pool. The performance of the developed methodology is analysed on instances taken from the suburban commuter network, DSB S-tog, in Copenhagen, Denmark. We show that the proposed approach yields line plans that are superior from both an operator and a passenger perspective to line plans that have been implemented in practice. PubDate: 2019-09-01
Abstract: Abstract We study scheduling and due-window assignment problems with the objective function of a minmax type, i.e., the goal is to minimize the largest cost among all scheduled jobs. We assume that the processing times of jobs are position-dependent in the most general way. For a single machine and for a proportionate flow shop environment we present polynomial time solution procedures that are based on solving a linear assignment problem as a subroutine. We further extend the single machine model by allowing job-rejection, provided that the processing times deteriorate, i.e., the position-dependent processing times are non-decreasing functions of the job position. For this setting, the scheduler may decide not to process certain jobs, and each rejected job is penalized accordingly. The problem with the objective that additionally involves a maximum rejection cost component is also shown to be solvable in polynomial time. PubDate: 2019-08-30
Abstract: Abstract Firms in the fashion industry frequently launch new styles of their products, thereby leading to a ‘two-period’ phenomenon in product sales: the normal selling time and the last salvage time. Researches about cooperative (co-op) advertising, however, seldom concentrate on this phenomenon. This study explores co-op advertising in a two-period fashion supply chain system in which the retailer offers a price discount in the second period. We derive the optimal pricing, product design level and advertising efforts in two scenarios: a decentralised scenario with a co-op advertising program and integrated scenario. Additionally, we propose a bilateral participation-revenue-sharing contract to coordinate this channel. Some insights and management implications are obtained. Firstly, if the consumers are insensitive to the first-period price, the retailer will set a high retail price in this period, while selling the product at a big discount in the second period to stimulate extra consumption. Secondly, if the price elasticity of demand is small, the retailer will spend more on the advertisement, otherwise the condition is opposite. Lastly, this study verifies that the bilateral participation-revenue-sharing contract can achieve a seamless coordination in this supply chain with a transfer payment. PubDate: 2019-08-22
Hybrid journal (It can contain Open Access articles)
[2573 journals]
