-
Competing for the most profitable tour: The orienteering interdiction game
Authors:
Eduardo Álvarez-Miranda,
Markus Sinnl,
Kübra Tanınmış
Abstract:
The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which…
▽ More
The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which a competitor (the leader) tries to minimize the total prize that the follower can collect within a feasible tour. To this end, the leader interdicts some of the nodes so that the follower cannot collect their prizes. The resulting interdiction game is formulated as a bilevel optimization problem, and a single-level reformulation is obtained based on interdiction cuts. A branch-and-cut algorithm with several enhancements, including the use of a solution pool, a cut pool and a heuristic method for the follower's problem, is proposed. In addition to this exact approach, a genetic algorithm is developed to obtain high-quality solutions in a short computing time. In a computational study based on instances from the literature for the orienteering problem, the usefulness of the proposed algorithmic components is assessed, and the branch-and-cut and genetic algorithms are compared in terms of solution time and quality.
△ Less
Submitted 3 July, 2024;
originally announced July 2024.
-
Exact and heuristic algorithms for the weighted total domination problem
Authors:
Eduardo Álvarez-Miranda,
Markus Sinnl
Abstract:
Dominating set problems are among the most important class of combinatorial problems in graph optimization, from a theoretical as well as from a practical point of view. In this paper, we address the recently introduced (minimum) weighted total domination problem. In this problem, we are given an undirected graph with a vertex weight function and an edge weight function. The goal is to find a tota…
▽ More
Dominating set problems are among the most important class of combinatorial problems in graph optimization, from a theoretical as well as from a practical point of view. In this paper, we address the recently introduced (minimum) weighted total domination problem. In this problem, we are given an undirected graph with a vertex weight function and an edge weight function. The goal is to find a total dominating set D in this graph with minimal weight. A total dominating set D is a subset of the vertices such that every vertex in the graph, including vertices in D, is adjacent to a vertex in D. The weight is measured as the sum of all vertex weights of vertices in D, plus the edge weights in the subgraph induced by D, plus for each vertex not in D the minimum weight of an edge from it to a vertex in D. In this paper, we present two new Mixed-Integer Programming models for the problem, and design solution frameworks based on them. These solution frameworks also include valid inequalities, starting heuristics and primal heuristics. In addition, we also develop a genetic algorithm, which is based on a greedy randomized adaptive search procedure version of our starting heuristic. We carry out a computational study to assess the performance of our approaches when compared to the previous work for the same problem. The study reveals that our exact solution algorithms are up to 500 times faster compared to previous exact approaches and instances with up to 125 vertices can be solved to optimality within a timelimit of 1800 seconds. Moreover, the presented genetic algorithm also works well and often finds the optimal or a near-optimal solution within a short runtime. Additionally, we also analyze the influence of instance-characteristics on the performance of our algorithms.
△ Less
Submitted 8 October, 2019;
originally announced October 2019.
-
An exact solution framework for the multiple gradual cover location problem
Authors:
Eduardo Álvarez-Miranda,
Markus Sinnl
Abstract:
Facility and covering location models are key elements in many decision aid tools in logistics, supply chain design, telecommunications, public infrastructure planning, and many other industrial and public sectors. In many applications, it is likely that customers are not dichotomously covered by facilities, but gradually covered according to, e.g., the distance to the open facilities. Moreover, c…
▽ More
Facility and covering location models are key elements in many decision aid tools in logistics, supply chain design, telecommunications, public infrastructure planning, and many other industrial and public sectors. In many applications, it is likely that customers are not dichotomously covered by facilities, but gradually covered according to, e.g., the distance to the open facilities. Moreover, customers are not served by a single facility, but by a collection of them, which jointly serve them. In this paper we study the recently introduced multiple gradual cover location problem (MGCLP). The MGCLP addresses both of the issues described above.
We provide four different mixed-integer programming formulations for the MGCLP, all of them exploiting the submodularity of the objective function and developed a branch-and-cut framework based one these formulations. The framework is further enhanced by starting and primal heuristics and initialization procedures.
The computational results show that our approach allows to effectively address different sets of instances. We provide optimal solution values for 13 instances from literature, where the optimal solution was not known, and additionally provide improved solution values for seven instances. Many of these instances can be solved within a minute. We also analyze the dependence of the solution-structure on instance-characteristics.
△ Less
Submitted 11 September, 2019;
originally announced September 2019.
-
The Generalized Reserve Set Covering Problem with Connectivity and Buffer Requirements
Authors:
Eduardo Álvarez-Miranda,
Marcos Goycoolea,
Ivana Ljubić,
Markus Sinnl
Abstract:
The design of nature reserves is becoming, more and more, a crucial task for ensuring the conservation of endangered wildlife. In order to guarantee the preservation of species and a general ecological functioning, the designed reserves must typically verify a series of spatial requirements. Among the required characteristics, practitioners and researchers have pointed out two crucial aspects: (i)…
▽ More
The design of nature reserves is becoming, more and more, a crucial task for ensuring the conservation of endangered wildlife. In order to guarantee the preservation of species and a general ecological functioning, the designed reserves must typically verify a series of spatial requirements. Among the required characteristics, practitioners and researchers have pointed out two crucial aspects: (i) connectivity, so as to avoid spatial fragmentation, and (ii) the design of buffer zones surrounding (or protecting) so-called core areas. In this paper, we introduce the Generalized Reserve Set Covering Problem with Connectivity and Buffer Requirements. This problem extends the classical Reserve Set Covering Problem and allows to address these two requirements simultaneously. A solution framework based on Integer Linear Programming and branch-and-cut is developed. The framework is enhanced by valid inequalities, a construction and a primal heuristic and local branching. An extensive computational study on grid-graph instances and real-life instances based on data from three states of the U.S. and one region of Australia is carried out to assess the suitability of the proposed model to deal with the challenges faced by decision-makers in natural reserve design. The results show, on the one hand, the flexibility of the proposed models to provide solutions according to the decision-makers' requirements, and on the other hand, the effectiveness of the devised algorithm for providing' good solutions in reasonable computing times.
△ Less
Submitted 11 September, 2019; v1 submitted 10 September, 2019;
originally announced September 2019.
