Location–Allocation of Multiple-Server Service Centers with Constrained Queues or Waiting Times

Recently, the authors have formulated new models for the location of congested facilities, so to maximize population covered by service with short queues or waiting time. In this paper, we present an extension of these models, which seeks to cover all population and includes server allocation to the facilities. This new model is intended for the design of service networks, including health and EMS services, banking or distributed ticket-selling services. As opposed to the previous Maximal Covering model, the model presented here is a Set Covering formulation, which locates the least number of facilities and allocates the minimum number of servers (clerks, tellers, machines) to them, so to minimize queuing effects. For a better understanding, a first model is presented, in which the number of servers allocated to each facility is fixed. We then formulate a Location Set Covering model with a variable (optimal) number of servers per service center (or facility). A new heuristic, with good performance on a 55-node network, is developed and tested.     

The Robust Set Covering Problem with interval data

We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

Computational experience with approximation algorithms for the set covering problem

The Set Covering problem (SCP) is a well known combinatorial optimization problem, which is NP-hard. We conducted a comparative study of nine different approximation algorithms for the SCP, including several greedy variants, fractional relaxations, randomized algorithms and a neural network algorithm. The algorithms were tested on a set of random-generated problems with up to 500 rows and 5000 columns, and on two sets of problems originating in combinatorial questions with up to 28160 rows and 11264 columns.On the random problems and on one set of combinatorial problems, the best algorithm among those we tested was a randomized greedy algorithm, with the neural network algorithm very close in second place. On the other set of combinatorial problems, the best algorithm was a deterministic greedy variant, and the randomized algorithms (both randomized greedy and neural network) performed quite poorly. The other algorithms we tested were always inferior to the ones mentioned above.     

Joint ground and air emergency medical services coverage models: A greedy heuristic solution approach

Aeromedical and ground ambulance services often team up in responding to trauma crashes, especially when the emergency helicopter is unable to land at the crash scene. We propose location-coverage models and a greedy heuristic for their solution to simultaneously locate ground and air ambulances, and landing zones (transfer points). We provide a coverage definition based on both response time and total service time, and consider three coverage options; only ground emergency medical services (EMS) coverage, only air EMS coverage, or joint coverage of ground and air EMS in which the patient is transferred from an ambulance into an emergency helicopter at a transfer point. To analyze this complex coverage situation we develop two sets of models, which are variations of the Location Set Covering Problem (LSCP) and the Maximal Covering Location Problem (MCLP). These models address uncertainty in spatial distribution of motor vehicle crash locations by providing coverage to a given set of both crash nodes and paths. The models also consider unavailability of ground ambulances by drawing upon concepts from backup coverage models. We illustrate our results on a case study that uses crash data from the state of New Mexico. The case study shows that crash node and path coverage percentage values decrease when ground ambulances are utilized only within their own jurisdiction.     

Computational experience with general cutting planes for the Set Covering problem

In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by running an “exact” separation algorithm over the subproblems defined by suitably small subsets of the formulation constraints. Computational results on difficult small-medium size instances are reported.     

Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem

This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem. The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover, the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz.     

带核箱覆盖问题的在线算法

经典的箱覆盖问题是组合优化中一个著名的问题,并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界,指出仅在条件三下才存在渐近比好于０的在线算法,并给出了在此条件下一个渐近比为１／２的最好的在线算法。     

On Covering Methods for D.C. Optimization

Covering methods constitute a broad class of algorithms for solving multivariate Global Optimization problems. In this note we show that, when the objective f is d.c. and a d.c. decomposition for f is known, the computational burden usually suffered by multivariate covering methods is significantly reduced. With this we extend to the (non-differentiable) d.c. case the covering method of Breiman and Cutler, showing that it is a particular case of the standard outer approximation approach. Our computational experience shows that this generalization yields not only more flexibility but also faster convergence than the covering method of Breiman-Cutler.     

相同装卸工情况下装卸工问题的最优解

装卸工问题是一个新的NP困难的组合最优化问题,寻找其性能优良的近似算法是有重要的理论意义和实用价值的.相同装卸工情况下装卸工问题的系数矩阵是全么模矩阵,利用全么模矩阵的性质可以证明这种情况下的装卸工问题是多项式可解的.然而用全么模阵的性质还不能得到解的表达式.对这种情况下一辆货车的装卸工问题,用对偶单纯形法可得到最优解和最优值的解析表达式,从而可以把这个可解问题的最优值作为一般装卸工问题的近似值.这对于分析近似算法的性态是非常重要的.     

Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes

An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identified) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identified, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set (which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size) and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard (whereas in all previous works, their complexity was the same). We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set differ.     

Calculating approximation guarantees for partial set cover of pairs

As a part of a heuristic for the fast detection of new word combinations in text streams, we consider the NP-hard Partial Set Cover of Pairs problem. There we wish to cover a maximum number of pairs of elements by a prescribed number of sets from a given set family. While the approximation ratio of the greedy algorithm for the classic Partial Set Cover problem is completely understood, the same question for covering of pairs is intrinsically more complicated, since the pairs insert some graph-theoretic structure. The best approximation guarantee for the first greedy step can be rephrased as a problem in extremal combinatorics: Assume that we may place a fixed number of subsets of fixed and equal size in a set, how many different pairs of elements can we cover? In this paper we introduce a method to calculate optimal approximation guarantees, and we demonstrate its use on the smallest set families.     

最大割问题和最大平分割问题基于半定规划松弛的近似算法

考虑每条边具有非负权重的无向图, 最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大. 当最大割问题半定规划松弛的最优解落到二维空间时, Goemans将近似比从0.87856...改进为0.88456. 依赖于半定规划松弛的目标值与总权和的比值的曲线, 此曲线的最低点为0.88456, 当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时, 利用Gegenbauer多项式舍入技巧, 改进了Zwick的近似比曲线. 进一步, 考虑最大割问题的重要变形------最大平分割问题, 在此问题中增加了划分的两部分的点数相等的要求. 同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形, 并利用前述的Gegenbauer多项式舍入技巧得到0.7091-近似算法.     

Approximation algorithms for single machine scheduling with one unavailability period

In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.      

A 3/2-Approximation for the proportionate two-machine flow shop scheduling with minimum delays

We study the two-machine flow shop problem with minimum delays. The problem is known to be strongly NP-hard even in the case of unit processing times and to be approximable within a factor of 2 of the length of an optimal schedule in the general case. The question whether there exists a polynomial-time algorithm with a better approximation ratio has been posed by several researchers but still remains open. In this paper, we improve the above bound to 3/2 for the special case of the problem when both operations of each job have equal processing times (this case of flow shop is known as the proportionate flow shop). Our analysis of the algorithm relies upon a nontrivial generalization of the lower bound established by W. Yu for the case of unit processing times.     

Genetic algorithms for the bus driver scheduling problem: a case study

This paper describes an application of genetic algorithms to the bus driver scheduling problem. The application of genetic algorithms extends the traditional approach of Set Covering/Set Partitioning formulations, allowing the simultaneous consideration of several complex criteria. The genetic algorithm is integrated in a DSS but can be used as a very interactive tool or a stand-alone application. It incorporates the user's knowledge in a quite natural way and produces solutions that are almost directly implemented by the transport companies in their operational planning processes. Computational results with airline and bus crew scheduling problems from real world companies are presented and discussed.     

Bin covering with a general profit function: approximability results

In the recent paper (Benk? et al. 2010) we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a “good and fast” packing or covering. In the present paper we investigate the offline case. For the analysis, a novel view on “offline optimum” is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an asymptotic approximation ratio better than 6/7 if $P\ne NP$ .     

Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

On the minimum corridor connection problem and other generalized geometric problems

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.