-
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.
-
Benders decomposition algorithms for minimizing the spread of harmful contagions in networks
Authors:
Kübra Tanınmış,
Necati Aras,
Evren Güney,
Markus Sinnl
Abstract:
The COVID-19 pandemic has been a recent example for the spread of a harmful contagion in large populations. Moreover, the spread of harmful contagions is not only restricted to an infectious disease, but is also relevant to computer viruses and malware in computer networks. Furthermore, the spread of fake news and propaganda in online social networks is also of major concern. In this study, we int…
▽ More
The COVID-19 pandemic has been a recent example for the spread of a harmful contagion in large populations. Moreover, the spread of harmful contagions is not only restricted to an infectious disease, but is also relevant to computer viruses and malware in computer networks. Furthermore, the spread of fake news and propaganda in online social networks is also of major concern. In this study, we introduce the measure-based spread minimization problem (MBSMP), which can help policy makers in minimizing the spread of harmful contagions in large networks. We develop exact solution methods based on branch-and-Benders-cut algorithms that make use of the application of Benders decomposition method to two different mixed-integer programming formulations of the MBSMP: an arc-based formulation and a path-based formulation. We show that for both formulations the Benders optimality cuts can be generated using a combinatorial procedure rather than solving the dual subproblems using linear programming. Additional improvements such as using scenario-dependent extended seed sets, initial cuts, and a starting heuristic are also incorporated into our branch-and-Benders-cut algorithms. We investigate the contribution of various components of the solution algorithms to the performance on the basis of computational results obtained on a set of instances derived from existing ones in the literature.
△ Less
Submitted 25 April, 2024; v1 submitted 22 March, 2023;
originally announced March 2023.
-
Exact solution approaches for the discrete $α$-neighbor $p$-center problem
Authors:
Elisabeth Gaar,
Markus Sinnl
Abstract:
The discrete $α$-neighbor $p$-center problem (d-$α$-$p$CP) 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 $α$-closest facility is minimized.…
▽ More
The discrete $α$-neighbor $p$-center problem (d-$α$-$p$CP) 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 $α$-closest facility is minimized. The only existing algorithms in literature for solving the d-$α$-$p$CP are approximation algorithms and two recently proposed heuristics.
In this work, we present two integer programming formulations for the d-$α$-$p$CP, 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.
△ Less
Submitted 5 June, 2023; v1 submitted 23 November, 2022;
originally announced November 2022.
-
On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
Authors:
Elisabeth Gaar,
Jon Lee,
Ivana Ljubić,
Markus Sinnl,
Kübra Tanınmış
Abstract:
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing re…
▽ More
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables.
We present an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our binary instances.
△ Less
Submitted 8 January, 2023; v1 submitted 11 July, 2022;
originally announced July 2022.
-
A matheuristic for tri-objective binary integer programming
Authors:
Duleabom An,
Sophie N. Parragh,
Markus Sinnl,
Fabien Tricoire
Abstract:
Many real-world optimisation problems involve multiple objectives. When considered concurrently, they give rise to a set of optimal trade-off solutions, also known as efficient solutions. These solutions have the property that neither objective can be improved without deteriorating another objective. Motivated by the success of matheuristics in the single-objective domain, we propose a linear prog…
▽ More
Many real-world optimisation problems involve multiple objectives. When considered concurrently, they give rise to a set of optimal trade-off solutions, also known as efficient solutions. These solutions have the property that neither objective can be improved without deteriorating another objective. Motivated by the success of matheuristics in the single-objective domain, we propose a linear programming-based matheuristic for tri-objective binary integer programming. To achieve a high-quality approximation of the optimal set of trade-off solutions, a lower bound set is first obtained using the vector linear programming solver Bensolve. Then, feasibility pump-based ideas in combination with path relinking are applied in novel ways so as to obtain a high quality upper bound set. Our matheuristic is compared to a recently-suggested algorithm that is, to the best of our knowledge, the only existing matheuristic method for tri-objective integer programming. In an extensive computational study, we show that our method generates a better approximation of the true Pareto front than the benchmark method on a large set of tri-objective benchmark instances. Since the developed approach starts from a potentially fractional lower bound set, it may also be used as a primal heuristic in the context of linear relaxation-based multi-objective branch-and-bound algorithms.
△ Less
Submitted 5 May, 2022;
originally announced May 2022.
-
An Exact Method for Fortification Games
Authors:
Markus Leitner,
Ivana Ljubić,
Michele Monaci,
Markus Sinnl,
Kübra Tanınmış
Abstract:
A fortification game (FG) is a three-level, two-player Stackelberg game, also known as defender-attacker-defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while a…
▽ More
A fortification game (FG) is a three-level, two-player Stackelberg game, also known as defender-attacker-defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while at the innermost level the defender solves a recourse problem over the surviving or partially damaged assets. Fortification games have applications in various important areas, such as military operations, design of survivable networks, protection of facilities, or power grid protection. In this work, we present an exact solution algorithm for FGs, in which the recourse problems correspond to (possibly NP-hard) combinatorial optimization problems. The algorithm is based on a new generic mixed-integer linear programming reformulation in the natural space of fortification variables. Our new model makes use of fortification cuts that measure the contribution of a given fortification strategy to the objective function value. These cuts are generated on-the-fly by solving separation problems, which correspond to (modified) middle-level interdiction games. We design a branch-and-cut-based solution algorithm based on fortification cuts, their lifted versions, and other speed-up techniques. We present a computational study using the knapsack fortification game and the shortest path fortification game. For the latter one, we include a comparison with a state-of-the-art solution method from the literature. Our algorithm outperforms this method and allows us to solve previously unsolved instances to optimality.
△ Less
Submitted 9 February, 2022; v1 submitted 26 November, 2021;
originally announced November 2021.
-
SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs
Authors:
Elisabeth Gaar,
Jon Lee,
Ivana Ljubić,
Markus Sinnl,
Kübra Tanınmış
Abstract:
We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of d…
▽ More
We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.
△ Less
Submitted 8 March, 2022; v1 submitted 12 November, 2021;
originally announced November 2021.
-
A scaleable projection-based branch-and-cut algorithm for the $p$-center problem
Authors:
Elisabeth Gaar,
Markus Sinnl
Abstract:
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 pro…
▽ More
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 integer programming (IP) formulation of pCP is usually dismissed due to its size and bad linear programming (LP)-relaxation bounds.
We 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 semi-relaxation.
Finally, we also present a computational study on instances from the literature with up to more than 700000 customers and locations. Our solution algorithm is competitive with highly sophisticated set-cover-based solution algorithms, which depend on various components and parameters.
△ Less
Submitted 29 January, 2022; v1 submitted 16 August, 2021;
originally announced August 2021.
-
An iterative exact algorithm for the weighted fair sequences problem
Authors:
Markus Sinnl
Abstract:
In this work, we present a new iterative exact solution algorithm for the weighted fair sequences problem, which is a recently introduced NP-hard sequencing problem with applications in diverse areas such as TV advertisement scheduling, periodic machine maintenance and real-time scheduling. In the problem we are given an upper bound on the allowed solution sequence length and a list of symbols. Fo…
▽ More
In this work, we present a new iterative exact solution algorithm for the weighted fair sequences problem, which is a recently introduced NP-hard sequencing problem with applications in diverse areas such as TV advertisement scheduling, periodic machine maintenance and real-time scheduling. In the problem we are given an upper bound on the allowed solution sequence length and a list of symbols. For each symbols, there is a positive weight and a number, which gives the minimum times the symbol has to occur in a feasible solution sequence. The goal is to find a feasible sequence, which minimizes the maximum weight-distance product, which is calculated for each consecutive appearance of each symbol in the sequence, including the last and first appearance in the sequence, i.e., the sequence is considered to be circular for the calculation of the objective function. Our proposed solution algorithm is based on a new mixed-integer programming model for the problem for a fixed sequence length. The model is enhanced with valid inequalities and variable fixings. We also develop an extended model, which allows the definition of an additional set of valid inequalities and present additional results which can allow us to skip the solution of the mixed-integer program for some sequence lengths. We conduct a computational study on the instances from literature to assess the efficiency of our newly proposed solution approach. Our approach manages to solve 404 of 440 instances to optimality within the given timelimit, most of them within five minutes. The previous best existing solution approach for the problem only managed to solve 229 of these instances, and its exactness depends on an unproven conjecture. Moreover, our approach is up to two magnitudes faster compared to this best existing solution approach.
△ Less
Submitted 6 August, 2021;
originally announced August 2021.
-
An outer approximation algorithm for multi-objective mixed-integer linear and non-linear programming
Authors:
Fritz Bökler,
Sophie N. Parragh,
Markus Sinnl,
Fabien Tricoire
Abstract:
In this paper, we present the first outer approximation algorithm for multi-objective mixed-integer linear programming problems with any number of objectives. The algorithm also works for certain classes of non-linear programming problems. It produces the non-dominated extreme points as well as the facets of the convex hull of these points. The algorithm relies on an oracle which solves single-obj…
▽ More
In this paper, we present the first outer approximation algorithm for multi-objective mixed-integer linear programming problems with any number of objectives. The algorithm also works for certain classes of non-linear programming problems. It produces the non-dominated extreme points as well as the facets of the convex hull of these points. The algorithm relies on an oracle which solves single-objective weighted-sum problems and we show that the required number of oracle calls is polynomial in the number of facets of the convex hull of the non-dominated extreme points in the case of multiobjective mixed-integer programming (MOMILP). Thus, for MOMILP problems for which the weighted-sum problem is solvable in polynomial time, the facets can be computed with incremental-polynomial delay. From a practical perspective, the algorithm starts from a valid lower bound set for the non-dominated extreme points and iteratively improves it. Therefore it can be used in multi-objective branch-and-bound algorithms and still provide a valid bound set at any stage, even if interrupted before converging. Moreover, the oracle produces Pareto optimal solutions, which makes the algorithm also attractive from the primal side in a multi-objective branch-and-bound context. Finally, the oracle can also be called with any relaxation of the primal problem, and the obtained points and facets still provide a valid lower bound set. A computational study on a set of benchmark instances from the literature and new non-linear multi-objective instances is provided.
△ Less
Submitted 2 May, 2022; v1 submitted 30 March, 2021;
originally announced March 2021.
-
A branch-and-cut algorithm for submodular interdiction games
Authors:
Kübra Tanınmış,
Markus Sinnl
Abstract:
Many relevant applications from diverse areas such as marketing, wildlife conservation, or defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective…
▽ More
Many relevant applications from diverse areas such as marketing, wildlife conservation, or defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective value achievable by the follower, who seeks to maximize a submodular set function over the uninterdicted items subject to knapsack constraints.
We propose an exact branch-and-cut algorithm for these kind of interdiction games. The algorithm is based on interdiction cuts which allow to capture the follower's objective function value for a given interdiction decision of the leader and exploit the submodularity of the objective function. We also present extensions and liftings of these cuts and discuss additional preprocessing procedures.
We test our solution framework on the weighted maximal covering interdiction game and the bipartite inference interdiction game. For both applications, the improved variants of our interdiction cut perform significantly better than its basic version. For the weighted maximal covering interdiction game for which a mixed-integer bilevel linear programming (MIBLP) formulation is available, we compare the results with those of a state-of-the-art MIBLP solver. While the MIBLP solver yields a minimum of 54% optimality gap within one hour, our best branch-and-cut setting solves all but 4 of 108 instances to optimality with a maximum of 3% gap among unsolved ones.
△ Less
Submitted 29 March, 2021;
originally announced March 2021.
-
A LP relaxation based matheuristic for multi-objective integer programming
Authors:
Duleabom An,
Sophie N. Parragh,
Markus Sinnl,
Fabien Tricoire
Abstract:
Motivated by their success in the single-objective domain, we propose a very simple linear programming-based matheuristic for tri-objective binary integer programming. To tackle the problem, we obtain lower bound sets by means of the vector linear programming solver Bensolve. Then, simple heuristic approaches, such as rounding and path relinking, are applied to this lower bound set to obtain high-…
▽ More
Motivated by their success in the single-objective domain, we propose a very simple linear programming-based matheuristic for tri-objective binary integer programming. To tackle the problem, we obtain lower bound sets by means of the vector linear programming solver Bensolve. Then, simple heuristic approaches, such as rounding and path relinking, are applied to this lower bound set to obtain high-quality approximations of the optimal set of trade-off solutions. The proposed algorithm is compared to a recently suggested algorithm which is, to the best of our knowledge, the only existing matheuristic method for tri-objective integer programming. Computational experiments show that our method produces a better approximation of the true Pareto front using significantly less time than the benchmark method on standard benchmark instances for the three-objective knapsack problem.
△ Less
Submitted 6 February, 2021;
originally announced February 2021.
-
A note on computational approaches for the antibandwidth problem
Authors:
Markus Sinnl
Abstract:
In this note, we consider the antibandwidth problem, also known as dual bandwidth problem, separation problem and maximum differential coloring problem. Given a labeled graph (i.e., a numbering of the vertices of a graph), the antibandwidth of a node is defined as the minimum absolute difference of its labeling to the labeling of all its adjacent vertices. The goal in the antibandwidth problem is…
▽ More
In this note, we consider the antibandwidth problem, also known as dual bandwidth problem, separation problem and maximum differential coloring problem. Given a labeled graph (i.e., a numbering of the vertices of a graph), the antibandwidth of a node is defined as the minimum absolute difference of its labeling to the labeling of all its adjacent vertices. The goal in the antibandwidth problem is to find a labeling maximizing the antibandwidth. The problem is NP-hard in general graphs and has applications in diverse areas like scheduling, radio frequency assignment, obnoxious facility location and map-coloring. There has been much work on deriving theoretical bounds for the problem and also in the design of metaheuristics in recent years. However, the optimality gaps between the best known solution values and reported upper bounds for the HarwellBoeing Matrix-instances, which are the commonly used benchmark instances for this problem, are often very large (e.g., up to 577%). The upper bounds reported in literature are based on the theoretical bounds involving simple graph characteristics, i.e., size, order and degree, and a mixed-integer programming (MIP) model. We present new MIP models for the problem, together with valid inequalities, and design a branch-and-cut algorithm and an iterative solution algorithm based on them. These algorithms also include two starting heuristics and a primal heuristic. We also present a constraint programming approach, and calculate upper bounds based on the stability number and chromatic number. Our computational study shows that the developed approaches allow to find the proven optimal solution for eight instances from literature, where the optimal solution was unknown and also provide reduced gaps for eleven additional instances, including improved solution values for seven instances, the largest optimality gap is now 46%.
△ Less
Submitted 8 October, 2019;
originally announced October 2019.
-
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.
-
Algorithmic expedients for the S-labeling problem
Authors:
Markus Sinnl
Abstract:
Graph labeling problems have been widely studied in the last decades and have a vast area of application. In this work, we study the recently introduced S-labeling problem, in which the nodes get labeled using labels from 1 to |V | and for each edge the contribution to the objective function, called S-labeling number of the graph, is the minimum label of its end-nodes. The goal is to find a labeli…
▽ More
Graph labeling problems have been widely studied in the last decades and have a vast area of application. In this work, we study the recently introduced S-labeling problem, in which the nodes get labeled using labels from 1 to |V | and for each edge the contribution to the objective function, called S-labeling number of the graph, is the minimum label of its end-nodes. The goal is to find a labeling with minimum value. The problem is NP-hard for planar subcubic graphs, although for many other graph classes the complexity status is still unknown. In this paper, we present different algorithmic approaches for tackling this problem: We develop an exact solution framework based on Mixed-Integer Programming (MIP) which is enhanced with valid inequalities, starting and primal heuristics and specialized branching rules. We show that our MIP formulation has no integrality gap for paths, cycles and perfect n-ary trees, and, to the best of our knowledge, we give the first polynomial-time algorithm for the problem on n-ary trees as well as a closed formula for the S-labeling number for such trees. Moreover, we also present a Lagrangian heuristic and a constraint programming approach. A computational study is carried out in order to (i) investigate if there may be other special graph classes, where our MIP formulation has no integrality gap, and (ii) assess the effectiveness of the proposed solution approaches for solving the problem on a dataset consisting of general graphs.
△ Less
Submitted 11 September, 2019; v1 submitted 10 September, 2019;
originally announced September 2019.
