The discrete a-neighbor p-center problem (d-a-pCP) is an emerging variant of the classical p-center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we nee...
详细信息
The discrete a-neighbor p-center problem (d-a-pCP) is an emerging variant of the classical p-center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate p facilities on these points in such a way that the maximum distance between each point where no facility is located and its a-closest facility is minimized. The only existing algorithms in literature for solving the d-a-pCP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d-a-pCP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch-and-cut (B&C ) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances.
The p-median problem is a classic discrete location problem with numerous applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders dec...
详细信息
The p-median problem is a classic discrete location problem with numerous applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We show that the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm that outperforms state-of-the-art methods on benchmark instances by an order of magnitude and allows to exactly solve for the first time several instances among which are large TSP instances and BIRCH instances. We also show that our implementation easily applies to the uncapacitated facility location problem.(c) 2022 Elsevier B.V. All rights reserved.
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to i...
详细信息
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. Further, we investigate computable lower bounds on rc(X) with the particular focus on the existence of a finite set Y subset of Z(d) such that separating X and Y \ X allows us to deduce rc(X) >= k. In particular, we show for some choices of X that no such finite set Y exists to certify the value of rc(X), providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for rc(X) for specific classes of sets X and present the first practically applicable approach to compute rc(X) for sets X that admit a finite certificate.
For a given undirected graph G = (V, E) with a non-negative weight function w : E -> R+ and subsets G(1),..., G(k) of V, the Group Steiner Tree (GST) problem consists of constructing a tree T = (V-T, E-T) with mini...
详细信息
ISBN:
(纸本)9783031629112;9783031629129
For a given undirected graph G = (V, E) with a non-negative weight function w : E -> R+ and subsets G(1),..., G(k) of V, the Group Steiner Tree (GST) problem consists of constructing a tree T = (V-T, E-T) with minimal cost, where V-T. subset of V, E-T subset of E, and T spans at least one node from each of the groups. We develop a VNS-based metaheuristics approach for solving the GST problem. Our main contribution is that we propose a new problem-specific node release strategy that mimics the steps of a VNS-based heuristic. Instead of exploring different neighborhoods by combinatorially enumerating neighboring solutions, as in classical local search, we use a provably good integer Linear programming (ILP) formulation to solve a sequence of subproblems of the original problem. Our approach leads to an improvement over the state-of-theart Gurobi solver both in terms of quality and runtime of the instances available in the literature.
In this paper, we propose optimization models to address flexible staff scheduling problems and some main issues arising from efficient workforce management during the Covid-19 pandemic. The adoption of precautionary ...
详细信息
In this paper, we propose optimization models to address flexible staff scheduling problems and some main issues arising from efficient workforce management during the Covid-19 pandemic. The adoption of precautionary measures to prevent the pandemic from spreading has raised the need to rethink quickly and effectively the way in which the workforce is scheduled, to ensure that all the activities are conducted in a safe and responsible manner. The emphasis is on novel optimization models that take into account demand requirements, employees' personal and family responsibilities, and anti-Covid-19 measures at the same time. It is precisely considering the anti-Covid-19 measures that the models allow to define the working mode to be assigned to the employees: working remotely or on-site. The last optimization model, which can be viewed as the most general and the most flexible formulation, has been developed to capture the specificity of a real case study of an Italian University. In order to improve employees' satisfaction and ensure the best work/life balance possible, an alternative partition of a workday into shifts to the usual two shifts, morning and afternoon, is proposed. The model has been tested on real data provided by the Department of Mechanical, Energy and Management Engineering, University of Calabria, Italy. The computational experiments show good performance and underline the potentiality of the model to handle worker safety requirements and practicalities and to ensure work activities continuity. In addition, the non-cyclic workforce policy, based on the proposed workday organization, is preferred by employees, since it allows them to better meet their needs.
The p-center problem (pCP) is a fundamental problem in location science, where we are given customer demand points and possible facility locations, and we want to choose p of these locations to open a facility such th...
详细信息
The p-center problem (pCP) is a fundamental problem in location science, where we are given customer demand points and possible facility locations, and we want to choose p of these locations to open a facility such that the maximum distance of any customer demand point to its closest open facility is minimized. State-of-the-art solution approaches of pCP use its connection to the set cover problem to solve pCP in an iterative fashion by repeatedly solving set cover problems. The classical textbook integerprogramming (IP) formulation of pCP is usually dismissed due to its size and bad linear programming (LP)-relaxation *** present a novel solution approach that works on a new IP formulation that can be obtained by a projection from the classical formulation. The formulation is solved by means of branch-and-cut, where cuts for demand points are iteratively generated. Moreover, the formulation can be strengthened with combinatorial information to obtain a much tighter LP-relaxation. In particular, we present a novel way to use lower bound information to obtain stronger cuts. We show that the LP-relaxation bound of our strengthened formulation has the same strength as the best known bound in literature, which is based on a ***, we also present a computational study on instances from the literature with up to more than 70 0,0 0 0 customers and locations. Our solution algorithm is competitive with highly sophisticated set cover-based solution algorithms, which depend on various components and parameters.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://***/licenses/by/4.0/ )
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool ...
详细信息
ISBN:
(纸本)9783030738792;9783030738785
The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc g (X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. We also present an explicit formula for rc(X) of a specific class of sets X and present numerical experiments on the distribution of rc(X) in dimension 2.
We consider the Block Relocation Problem, that has a crucial role in the logistics of containers. It consists of minimizing the number of container relocations within a container bay/yard. Since the number of containe...
详细信息
We consider the Block Relocation Problem, that has a crucial role in the logistics of containers. It consists of minimizing the number of container relocations within a container bay/yard. Since the number of containers shipped worldwide grew dramatically in the last years, the problem has been widely investigated. Here we propose an exact algorithm for the restricted version of the Block Relocation Problem, based on a new integer linear programmingformulation. We compare such new approach with the state-of-art exact methods. The computational results prove its effectiveness and show that it outperforms all the previously proposed procedures, in almost all the considered instances. (C) 2020 Elsevier B.V. All rights reserved.
A desirable property of integerformulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially ma...
详细信息
A desirable property of integerformulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integerformulation. Moreover, we show that there exist undirected graphs such that (in a natural model) every integerformulation of stable sets requires exponentially large coefficients if the number of non-trivial inequalities is bounded by a constant. (C) 2020 The Author(s). Published by Elsevier B.V.
In this article, we study the k-edge-connected L-hop-constrained network design problem. Given a weighted graph , a set D of pairs of nodes, two integers and , the problem consists in finding a minimum weight subgraph...
详细信息
In this article, we study the k-edge-connected L-hop-constrained network design problem. Given a weighted graph , a set D of pairs of nodes, two integers and , the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair . We consider the problem in the case where L=2, 3 and . We first discuss integer programming formulations introduced in the literature. Then, we introduce new integer programming formulations for the problem that are based on the transformation of the initial undirected graph into directed layered graphs. We present a theoretical comparison of these formulations in terms of LP-bound. Finally, these formulations are tested using CPLEX and compared in a computational study for k=3, 4, 5. (c) 2015 Wiley Periodicals, Inc. NETWORKS, 67(2), 148-169 2016
暂无评论