A compact mixed integer linear formulation for safe set problems
- PDF / 409,468 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 227 Views
A compact mixed integer linear formulation for safe set problems Pierre Hosteins1 Received: 16 April 2019 / Accepted: 28 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The Safe Set Problem is a type of partitioning problem with particular constraints on the weight of adjacent partition components. Several theoretical results exist in the literature along with a mixed integer linear formulation. We propose a new, more compact, Mixed Integer Linear Program for the (Weighted) Safe Set Problem and Connected Safe Set Problem with a polynomial number of variables and constraints, based on a flow from an additional fictitious node. The model is enriched by symmetrybreaking considerations and a variable reduction subproblem. We test the model on a benchmark of small instances which underline the difficulty of solving the Safe Set Problem through mathematical programming approaches. We also compare it with the only existing formulation in the literature and find that our approach is usually more efficient on a set of benchmark instances. Keywords Graph partitioning · Network control · Safe set · Connected safe set · Mixed integer linear programming · Symmetry-breaking · Variable reduction
1 Introduction Consider an undirected and connected graph G = (V , E) with node weights wi ≥ 0 for i ∈ V . We call Ni ⊂ V the set of neighbours of node i ∈ V and define a nonV empty subset S ⊂ V which induces a subgraph G[S]. The function w : 2 → R+ is defined as w(S) = i∈S wi , i.e. the total weight of a subset of nodes S ⊆ V . S is said to be a safe set if S = ∅ and for any maximally connected component C in G[S] and C in G[V \S] we have w(C) ≥ w(C ) whenever an edge exists between C and C . The Weighted Safe Set problem (WSSP) consists in finding the safe set with minimum total weight, while the simpler Safe Set Problem (SSP) considers only unit node weights. The Connected Safe Set Problem (CSSP) is a Safe Set Problem where
B 1
Pierre Hosteins [email protected] IFSTTAR, COSYS, ESTAS, Univ Gustave Eiffel, 59650 Villeneuve d’Ascq, Lille, France
123
P. Hosteins
Fig. 1 Example of a feasible safe set for a small instance of the SSP. The nodes in the safe set are displayed in black
the safe set is connected (i.e. G[S] has only one component). An optimal solution of any Safe Set variant is denoted as S ∗ . We observe that if G is not connected, the problem decomposes completely on each of the connected components of G. Thus, we assume without loss of generality that G is connected. An example of a feasible safe set on a small graph is illustrated in Fig. 1. The SSP was first defined in [7] as a way to determine important influential communities in a social network. Another application is invoked in [13] where one looks for a subspace inside a building that can shelter the people from nearby spaces in a case of a catastrophe, i.e. a building design problem. From a more general point of view, the SSP is designed to determine the smallest subset of a network which we need to control (or equ
Data Loading...
