Abstract: Suppose that on any day, calls for service are generated by nodes of a transportation network independently with known probabilities. The calls are allocated to p service units that visit the allocated customers on shortest closed tours. That is, each service unit performs an optimal traveling salesman tour on its set of allocated calls (customers). We need to find optimal locations for the service units to minimize the expected travel distance. For this problem on a path, we present an \(O(n^4)\) algorithm, where n is the number of nodes of the network. We also present an \(O(n^5)\) algorithm for the problem on a tree with \(p=2\). PubDate: 2020-03-01

Abstract: The increasing maritime traffic forces terminal operators to efficiently reduce the container ships’ service time in order to maintain or increase their market share. This situation gives rise to the well-known berth allocation problem. Its goal is to determine the allocation and the berthing time of container ships arriving to the port with the aim of minimizing the total service time. For tackling this problem, we propose a dynamic programming-based matheuristic that allows to derive lower and upper bounds, and therefore, evaluate the optimality of the provided solutions. Its behavior is assessed on realistic problem instances from the related literature as well as on a new set of larger instances with 150 ships and 15 berths. The results indicate that our proposed approach shows a competitive performance. PubDate: 2020-03-01

Abstract: Based on a case study, this paper deals with the production planning and scheduling problem of the glass container industry. This is a facility production system that has a set of furnaces where the glass is produced in order to meet the demand, being afterwards distributed to a set of parallel molding machines. Due to huge setup times involved in a color changeover, manufacturers adopt their own mix of furnaces and machines to meet the needs of their customers as flexibly and efficiently as possible. In this paper we proposed an optimization model that maximizes the fulfillment of the demand considering typical constraints from the planning production formulation as well as real case production constraints such as the limited product changeovers and the minimum run length in a machine. The complexity of the proposed model is assessed by means of an industrial real instance. PubDate: 2020-03-01

Abstract: In this era of ubiquitous networks that become increasingly vulnerable to disruptions, network reliability has emerged as a critical issue in their design and operation. Businesses and individuals become ever more dependent on networks and demand reliable delivery of critical services every time. This paper finds Pareto optimal locations for a single facility on an existing tree network that maximizes service availability to customers by considering both the average and the lowest level of service delivery with respect to all customers. Examples are the location of decision entities on information infrastructures, servers or databases on computer networks, control systems on telecommunication networks, critical information on social networks, supply centers on supply chain networks, and location of emergency response facilities to intentional or natural disasters. Model properties are identified in decision and objective space and used to develop an efficient algorithm for finding the efficient and the non-dominated sets. Numerical examples are provided to illustrate the algorithm and to show special conditions for the efficient and non-dominated sets to be continuous. PubDate: 2020-03-01

Abstract: In data envelopment analysis (DEA) it is usually necessary to perform some data preprocessing routines. For example, in many practical situations, it may occur that some of the input and/or output values are not available for all the decision-making units (DMUs). Therefore, in such situations, it becomes necessary to set up a strategy to deal with the missing data. In this context, the present work proposes the application of a recent matrix approximation approach, known as low-rank matrix completion, for preprocessing missing data in DEA. The proposed method is evaluated through a number of numerical experiments carried out on both synthetic and actual data. We compare, for a wide range of missing data proportions, the efficiencies of DMUs obtained after recovering the missing entries to those obtained in an ideal situation, in which all data is known. We also provide comparisons with other approaches that deal with missing data in the context of DEA. The results attest the viability of the application of the proposed low-rank matrix completion strategy to DEA. PubDate: 2020-03-01

Abstract: Given a simple graph G, a set \(C \subseteq V(G)\) is a neighborhood cover set if every edge and vertex of G belongs to some G[v] with \(v \in C\), where G[v] denotes the subgraph of G induced by the closed neighborhood of the vertex v. Two elements of \(E(G) \cup V(G)\) are neighborhood-independent if there is no vertex \(v\in V(G)\) such that both elements are in G[v]. A set \(S\subseteq V(G)\cup E(G)\) is neighborhood-independent if every pair of elements of S is neighborhood-independent. Let \(\rho _{\mathrm {n}}(G)\) be the size of a minimum neighborhood cover set and \(\alpha _{\mathrm {n}}(G)\) of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs G as those where the equality \(\rho _{\mathrm {n}}(G^\prime ) = \alpha _{\mathrm {n}}(G^\prime )\) holds for every induced subgraph \(G^\prime \) of G. In this work we prove forbidden induced subgraph characterizations of the class of neighborhood-perfect graphs, restricted to two superclasses of cographs: \(P_4\)-tidy graphs and tree-cographs. We give as well linear-time algorithms for solving the recognition problem of neighborhood-perfect graphs and the problem of finding a minimum neighborhood cover set and a maximum neighborhood-independent set in these same classes. Finally we prove that although for complements of trees finding these optimal sets can be achieved in linear-time, for complements of bipartite graphs it is \(\mathrm {NP}\)-hard. PubDate: 2020-03-01

Abstract: In this paper, we study an inventory system for products where demand depends on time and price. Shortages are allowed and are fully backordered. We suppose that the demand rate is the product of a power time pattern and a three-parametric exponential price function. The objective is to determine the economic lot size, the optimal shortage level and the best selling price to maximize the total profit per unit time. We present an efficient procedure to determine the optimal solution of the inventory problem for all possible scenarios. This procedure is illustrated with several numerical examples. A sensitivity analysis of the optimal inventory policy with respect to the parameters of the demand rate function is also given. Finally, the main contributions of this paper are highlighted and future research directions are introduced. PubDate: 2020-03-01

Abstract: In 2000, Chile introduced profound health reforms to achieve a more equitable and fairer system (GES plan). The reforms established a maximum waiting time between diagnosis and treatment for a set of diseases, described as an opportunity guarantee within the reform. If the maximum waiting time is exceeded, the patient is referred to another (private) facility and receives a voucher to cover the additional expenses. This voucher is paid by the health provider that had to do the procedure, which generally is a public hospital. In general, this reform has improved the service for patients with GES pathologies at the expense of patients with non-GES pathologies. These new conditions create a complicated planning scenario for hospitals, in which the hospital’s OR Manager must balance the fulfillment of these opportunity guarantees and the timely service of patients not covered by the guarantee. With the collaboration of the Instituto de Neurocirugía, in Santiago, Chile, we developed a mathematical model based on stochastic dynamic programming to schedule surgeries in order to minimize the cost of referrals to the private sector. Given the large size of the state space, we developed an heuristic to compute good solutions in reasonable time and analyzed its performance. Our experimental results, with both simulated and real data, show that our algorithm performs close to optimum and improves upon the current practice. When we compared the results of our heuristic against those obtained by the hospital’s OR manager in a simulation setting with real data, we reduced the overtime from occurring 21% of the time to zero, and the non-GES average waiting list’s length from 71 to 58 patients, without worsening the average throughput. PubDate: 2020-03-01

Abstract: This paper addresses the edge coloring by total labeling graph problem. This is a labeling of the vertices and edges of a graph such that the weights (colors) of the edges, defined by the sum of its label and the labels of its two endpoints, determine a proper edge coloring of the graph. We propose two integer programming formulations and derive valid inequalities which are added as cutting planes on a Branch-and-Cut framework. In order to improve the efficiency of the algorithm, we also develop initial and primal heuristics. The algorithm is tested on random instances and the computational results show that it is very effective in comparison with CPLEX. It is displayed that it reduces both the CPU time (for solved instances) and the final percentage gap (for unsolved instances), and that it is capable of solving instances that are out of the reach of CPLEX. PubDate: 2020-03-01

Abstract: This article concerns operations of businesses that own inventories of rental items, and can hire additional items from secondary sources whenever they face a temporary exhaustion of their inventories. This set-up is relevant to many operations: the items may be tools, trucks, containers, communication channels, or individuals who provide services such as repairmen. A fundamental problem that emerges in the design of these operations is to determine the optimal size of the inventory of items the business should own. To solve this problem, this article takes the view of a finite horizon project and proposes an approach that chooses the inventory size that minimizes the expected present cost of the project. This approach models random times between consecutive item requests and random rental durations with corresponding expectations that may vary along the day. The expected present cost uses non-stationary transition probabilities that recent articles have computed resorting to stationary approximations. This article, in contrast, computes these probabilities faster solving a differential equation without resorting to such approximations. If the present cost is of interest, an analysis that plugs-in the optimal size into the present cost ignores the sampling variability that transfers from the traffic data to the optimal size. This article complements the analysis with simulations that provide the sampling distribution of the present cost. PubDate: 2020-03-01

Abstract: The alternate direction method of multipliers (ADMM) has received significant attention recently as a powerful algorithm to solve convex problems with a block structure. The vast majority of applications focus on deterministic problems. In this paper we show that ADMM can be applied to solve two-stage stochastic programming problems, and we propose an implementation in three blocks with or without proximal terms. We present numerical results for large scale instances, and extend our findings for risk averse formulations using utility functions. PubDate: 2020-03-01

Abstract: In the last decades, a wide body of literature has been devoted to study different saliency detection methods. These methods are typically devised on the basis of different image analysis paradigms, which leads to different performances that are not always rankable, but rather complementary. In this paper, a network design-based framework for multicriteria robust saliency detection is proposed. The key idea is that a suitable blending of the salient regions obtained by different methods leads to a salient region that outperforms the results obtained, individually, by these methods. Moreover, besides of considering state-of-the-art saliency detection approaches, a new method, which incorporates a novel tool for image contour detection, is designed. Results obtained on different sets of benchmark instances show that the proposed multicriteria robust framework exhibits high accuracy in the detection of salience objects; i.e., the pixels comprising the blended salient object are likely to be part of the actual salient object. This work aims at building further bridges between the areas of image processing and the areas of operations research. PubDate: 2020-03-01

Abstract: This paper analyzes the procedure used by FIFA up until 2018 to rank national football teams and define by random draw the groups for the initial phase of the World Cup finals. A predictive model is calibrated to form a reference ranking to evaluate the performance of a series of simple changes to that procedure. These proposed modifications are guided by a qualitative and statistical analysis of the FIFA ranking. We then analyze the use of this ranking to determine the groups for the World Cup finals. After enumerating a series of deficiencies in the group assignments for the 2014 World Cup, a mixed integer linear programming model is developed and used to balance the difficulty levels of the groups. PubDate: 2020-03-01

Abstract: This paper considers the problem of zone delineation management and crop planning. The problem consists of selecting which crops to plant in different management zones in order to minimize the total costs subjected to a given demand requirement. From a hierarchical point of view, the process starts by generating a partition of an agricultural field into homogeneous management zones, according to a given soil property. Then, the best crop rotation must be assigned to each management zone, applying agronomic practices in a site-specific manner in each zone. This hierarchical approach establishes two decision making levels of planning. At each level, a two-stage stochastic optimization model is proposed, representing the uncertain behavior of a soil property and crop yields by using a finite set of scenarios. Next, we combined them into a new two-stage stochastic program, solving an integrated approach by simultaneously determining an optimal zoning and allocation. Results from a set of evaluated instances showed the relevance of the proposed methodology and the benefits of the hierarchical approach over the integrated one. PubDate: 2020-03-01

Abstract: This paper deals with the Flooding Problem on graphs. This problem consists in finding the shortest sequence of flooding moves that turns a colored graph into a monochromatic one. The problem has applications in some areas as disease propagation, for example. Three metaheuristics versions are proposed and compared with the literature results. A new integer programming formulation is also proposed and tested with the only formulation known. The obtained results indicate that both the proposed formulation and the Evolutionary Algorithm are, respectively, the best exact and heuristic approaches for the problem. PubDate: 2020-03-01

Abstract: The objective of territorial design for a distribution company is the definition of geographic areas that group customers. These geographic areas, usually called districts or territories, should comply with operational rules while maximizing potential sales and minimizing incurred costs. Consequently, territorial design can be seen as a clustering problem in which clients are geographically grouped according to certain criteria which usually vary according to specific objectives and requirements (e.g. costs, delivery times, workload, number of clients, etc.). In this work, we provide a novel hybrid approach for territorial design by means of combining a K-means-based approach for clustering construction with an optimization framework. The K-means approach incorporates the novelty of using tour length approximation techniques to satisfy the conditions of a pork and poultry distributor based in the region of Valparaíso in Chile. The resulting method proves to be robust in the experiments performed, and the Valparaíso case study shows significant savings when compared to the original solution used by the company. PubDate: 2020-03-01

Abstract: This paper addresses the petrol station replenishment problem with periodicity constraints and introduces the frequency service choice as a decision variable. We present a mathematical optimization model for the problem and we develop first a simple heuristic method that is able to handle the complexity of the problem and then two metaheuristic approaches based on a novel two-level evolutionary algorithm. The first level deals with the periodicity and frequency selection of the visits to the petrol stations. The second level of evolution assigns the stations to the tank-trucks such that the total traveled distance is minimized. The effectiveness of the proposed approaches has been tested by means of a comprehensive experimental study by using first a set of randomly generated test cases and then a real-life problem. PubDate: 2020-03-01

Abstract: This research addresses a scheduling problem for chemotherapy patients, which is divided in two subproblems: patient scheduling on an infinite horizon and daily patient scheduling. We consider the requirement for available laboratory hours to prepare the medicine for every patient as an additional complexity. A methodology was formulated that addresses the problem in two stages. The first one is based on previous research and implements a scheduling policy for chemotherapy. The result of this first stage is the input for the second stage, which is addressed by generating treatment patterns. The benefits of both stages of the proposed methodology are evaluated for two real cases, one of them in the Chemotherapy Division of Hospital Salvador, and the other in the Cancer Center, of the Clinical Hospital of the Pontificia Universidad Católica de Chile, both in Santiago, Chile. Regarding the costs’ impact, the method proposed manages to reduce 20% and 17% the operational costs in these cases, due to less extra treatment hours needed. On the other hand, the proposed daily scheduling method for patients presents an improvement of 21% and 9% in care slots usage and 22% and 17% in laboratory slots usage for an average demand day, which translates in a reduction of both extra hours used and workday duration, for the case of the Chemotherapy Division and Cancer Center, respectively. PubDate: 2020-03-01

Abstract: This paper develops a multiproduct economic production quantity inventory model for a vendor–buyer system in which several products are manufactured on a single machine. The vendor delivers the products to customer in small batches. The number of orders must be a discrete value. Moreover, benefitting from a just-in-time policy, the buyer decides the size of the delivered batches. Due to the fact that several products are manufactured on one machine, this makes that the production capacity be considered as a constraint. The aim of this study is to determine the optimal cycle length and the number of delivered batches for each product so that the total inventory cost is minimized. The problem under study is modeled as a mixed integer nonlinear programing problem considering maximum number of orders, capacity and budget constraints. Three different methods are developed and employed to solve this problem: an exact method, a heuristic algorithm and a hybrid genetic algorithm. Based on the results, the three algorithms have near efficiency with different running times. The results shows that the heuristic algorithm obtains a good solution in a short time and the hybrid genetic algorithm finds solutions with higher quality in an acceptable time. Finally, a sensitivity analysis is done to evaluate the effect of changes in the parameters of problem. PubDate: 2020-03-01