Tackling the Partner Units Configuration Problem

1 Introduction

In this paper we address the Partner Units Problem (PUP) [Falkner et al., 2010], a configuration problem of high relevance to surveillance and security applications where a large number of sensors is divided into possibly overlapping zones. More specifically, the PUP deals with the configuration of a network of control units ("units") for the sensors and zones.

Informally the PUP can be described as follows: Consider a set of sensors that are grouped into zones. A zone may contain many sensors, and a sensor may be attached to more than one zone. The PUP then consists of connecting the sensors and zones to control units. These control units can be connected to a given fixed maximum number UnitCap of zones and sensors. 1 Moreover, if a sensor is attached to a zone, but the sensor and the zone are assigned to different control units, then the two control units in question have to be (directly) connected. However, a control unit cannot be connected to more than InterUnitCap other control units (the partner units).

For an application scenario consider e.g. a museum where we want to keep track of the number of visitors that populate certain parts (zones) of the building. To this end the doors leading from one zone to another are equipped with sensors.

∗Work funded by EPSRC Grant EP/G055114/1. Cooperation with Siemens Austria partially funded by FFG FIT-IT Grant 825071.

1 For ease of presentation we assume that UnitCap is the same for zones and sensors.

To keep track of the visitors the zones and sensors are attached to control units; the adjacency constraints on the control units ensure that communication between control units can be kept simple. It is worth emphasizing that the PUP is not limited to this application domain: It occurs whenever sensors that are grouped into zones have to be attached to control units, and communication between units must be kept simple because of capacity constraints such as in intelligent traffic management or safeguarding semi-automated transport systems. The PUP is used as a benchmark instance at this year's answer set programming competition [ASPcomp, 2011].

Figure 1 shows a PUP instance and a solution for the case UnitCap = InterUnitCap = 2: six sensors (left) and six zones (right) which are completely inter-connected are partitioned into units - shown as squares - respecting the adjacency constraints. Note that for the given parameters this is a maximal solvable instance; it is not possible to connect a new zone or sensor to any of the existing ones.

Let us emphasize that the PUP is a typical configuration problem in the sense of [Mittal and Frayman, 1989]: Connect a fixed finite set of given components so as to meet a given objective while respecting given constraints. Solving such configuration problems is one of the major success stories of applied AI research: Starting from early work on rule based systems [McDermott, 1982], manifold general purpose AI techniques such as CSP and SAT solving, heuristic search, and description logics have successfully been applied to configuration - for a recent survey see [Junker, 2006].

Due to cost considerations our partners in industry are primarily interested in finding optimal solutions, that is, solutions that use a minimum number of units. The rationale behind this optimization criterion is that (a) units are expensive, and (b) costs for connections are negligible.

Formally, the following are the three most important reasoning tasks for the PUP:

• Decide whether there is a solution (PUDP).
• Find a solution (PUSP).
• Find an optimal solution; i.e. one that uses a minimum number of control units (PUOP): We treat this as deciding whether there is a solution that uses n or fewer units.

In this paper we study the special version of the PUP where each unit can be connected to at most k sensors or zones (UnitCap = k) and to at most two other units (InterUnitCap = 2). This version of the problem (the SPUP) is precisely the problem-description we got from our industrial project partner.

We first tried to tackle the SPUP via CSP and SAT solving technology and answer set programming, and previous approaches additionally include heuristic search methods such as simulated annealing - none of these approaches were much use on the instances encountered in practice. The insight that these instances could be directly tackled via the algorithm presented in this paper constituted a major breakthrough performance-wise. A second major breakthrough occurred when incorporating these theoretical insights into the aforementioned general AI techniques.

A Guide to the Paper. The remainder of this paper is organized as follows: In Section 2 we formally introduce the problem and state general problem properties. Among other things we show that in its most general form the PUP is NP-hard (Theorem 1). Then in Section 3 we show that the SPUDP and the SPUSP are tractable. We do this by giving the NLOGSPACE algorithm DECIDESPUP that solves the problem by constructing a path decomposition with specific properties. We also show that the SPUOP is tractable if there are not more than logarithmically many connected components in the instance. In the same section we discuss our implementation of (a deterministic version of) the DECIDESPUP algorithm. In Section 4 we briefly evaluate the performance of our algorithm and an adapted CSP encoding. In Section 5 we conclude the paper with notes on related work and an outlook on future research.

We have also been working on encodings of the general version of the PUP- that is where both UnitCap and InterUnitCap are arbitrary fixed constants - in the frameworks of answer set, integer, and constraint programming as well as SAT solving. These encodings together with a more thorough empirical evaluation of the DECIDESPUP algorithm are presented in [Aschinger et al., 2011].

2 Formal Definition of the Partner Units Problem and Basic Facts

Formally, the PUP consists of partitioning the vertices of a bipartite graph G = (V1, V2,E) into a set U of units such that each unit

• contains at most UnitCap vertices from V1 and at most UnitCap vertices from V2; and
• has at most InterUnitCap adjacent units, where the units U1 and U2 are adjacent whenever vi ∈ U1 and vj ∈ U2 and (vi, vj) ∈ E.

To every solution of the PUP we can associate a solution graph. For this we associate to every unit Ui ∈ U a vertex vUi . Then the solution graph G∗ has the vertex set V1 ∪ V2 ∪ {vUi | Ui ∈ U} and the set of edges {(v, vUi ) | v ∈ Ui ∧ Ui ∈ U} ∪ {(vUi , vUj ) | Ui and Uj are adjacent.}. In the following we will refer to the subgraph of the solution graph induced by the vUi as the unit graph.

Unfortunately, in its most general form the PUOP is intractable:

Theorem 1 (PUOP is Intractable). The PUOP is NPcomplete when InterUnitCap = 0, and UnitCap is part of the input.

Proof. Membership in NP is obvious. For hardness, we reduce from BINPACKING, given by natural numbers i1, . . . , in, BinSize and k. We make a PUOP instance by creating for every ij a biclique between one fresh sensor and ij fresh zones, setting UnitCap = BinSize and InterUnitCap = 0. A packing with k or fewer bins exists iff there exists a solution to the PUOP with k or fewer units. Finally note that BINPACKING remains NP-complete when all the numbers are expressed in unary [Garey and Johnson, 1979].

Observe, however, that the above theorem concerns the case of optimally configuring one parameter of the units, namely UnitCap, rather than finding a configuration that respects the given unit properties.

On the other hand it is not hard to show the following:

Lemma 1 (Forbidden Subgraphs of the PUP). A PUP instance has no solution if it contains K1,n or Kn,1 as a subgraph, where n = ((InterUnitCap + 1) ∗ UnitCap) + 1.

Proof. Assume some sensor s has n neighbors, and is assigned to some unit U in a solution. There can be at most InterUnitCap Ui adjacent to U, each with at most UnitCap zones attached. Hence one of the neighbors of s has to be on a unit different from U and all the Ui.

Let us next point out that the number of units used when solving an instance G = (V1, V2, E) is bounded from below by lb = ⌈ max (|V1|,|V2|) UnitCap ⌉. Clearly it can also be bounded from above by ub = |V1| + |V2| - we never need empty units. If InterUnitCap = 2 and UnitCap > 1 we can show that the stronger ub = max (|V1|, |V2|) holds for connected instances. We conjecture that this also holds for InterUnitCap > 2, but have so far been unable to prove it. Now, if there are multiple connected components Ci in the instance with upper bounds ubi, then we have ub = ∑ ubi .

3 The Case of InterUnitCap = 2

We now turn to the SPUP, the announced Special Partner Units Problem, where the number of neighbors of any given unit in a solution is bounded by 2, i.e., InterUnitCap = 2.

We will directly tackle the SPUP by giving an algorithm that decides the SPUDP in NLOGSPACE by computing a special path decomposition of the instance graph.

For ease of presentation in the sequel we make the simplifying assumption that the underlying bipartite graph is connected. This does not affect solutions of the SPUDP and the SPUSP, where the connected components can be tackled independently. For optimal solutions, however, the connected components of an underlying graph will have to be considered simultaneously; cf. the discussion in Section 3.4.

3.1 Path Decompositions

Let us next formally introduce path decompositions. A path decomposition of a graph G = (V,E) is a pair P = (P, χ) such that P is a simple path (W, F ) - i.e., P does not contain cycles. The function χ associates to every w ∈ W a subset B ⊆ V such that

1. for every vertex v in V there is a vertex w ∈ W with v ∈ χ(w);
2. for every edge (v1, v2) there is a vertex w ∈ W with {v1, v2} ⊆ χ(w); and
3. for every vertex v in V the set {w ∈ W | v ∈ χ(w)} induces a subpath of P .

Condition (3) is called the connectedness condition. The subsets B associated with the path vertices are called bags. The width of a path decomposition is maxw∈W (|χ(w) - 1|). The pathwidth pw(G) of a graph is the minimum width over all its path decompositions.

3.2 Basic Properties of the SPUP

We proceed by identifying basic properties of the SPUP. The key observation is that the units and their interconnections form a special kind of unit graph in any solution: either a simple path, or a simple cycle. This holds because each unit is connected to at most two partner units. Moreover, cycles are more general unit graphs than paths: Every solution can be extended to a cyclic solution; hence in the sequel we only consider cyclic solutions.

Now every solution of a SPUP instance given by a zonesand-sensors-graph G gives rise to a path decomposition with special properties:

Theorem 2 (SPUP is Path-Decomposable). Assume a SPUP instance given by a graph G = (V1, V2, E) is solvable using n units, that is |U| = n. Let f be the unit function that associates vertices from G to U. Then there is a path decomposition P = (P, χ) of G of pathwidth ≤ (3 ∗ 2 ∗ UnitCap) - 1:

Proof. If G is solvable then there is a solution graph G∗ whose unit graph is a cycle vU1 , . . . , vUn , vU1 . Consider P = (P = w1, . . . , wn-1, χ) where χ(wi) = f -1 (U1) ∪ f -1 (Ui) ∪ f -1 (Ui+1). This P is indeed a path decomposition:

• Every edge (v1, v2) is in some bag. Assume v1 and v2 are assigned to two different connected units Ui and Ui+1. Then {v1, v2} ⊆ χ(wi).
• The connectedness condition is satisfied: For the vertices connected to unit U1 the induced subgraph is P. All other vertices occur in at most two consecutive bags.
• Every bag in P contains ≤ (3 ∗ 2 ∗ UnitCap) elements; hence pw(P) ≤ (3 ∗ 2 ∗ UnitCap) - 1.

An optimal path decomposition of the complete bipartite graph Kn,n with n = 3∗UnitCap has width (3∗2∗UnitCap)- 1; cf. Figure 1. Hence the bound is tight.

The following conditions are easily seen to hold for the path decomposition P constructed above:

• (a) The length of P is n1; P = w1, . . . wn-1.
• (b) There are sets S1 ⊆ V1, S2 ⊆ V2 with |Si| ≤ UnitCap such that S1 ∪ S2 are in every bag of P.
• (c) Apart from S1∪S2 each bag contains at most 2∗UnitCap elements from V1 (or V2, respectively).
• (d) For any vertex v ∈ V1 ∪ V2 all neighbors of v appear in three consecutive bags of P (assuming the first and last bag to be connec ted).
• (e) For each bag χ(wi) of P it holds χ(wi) = f -1 (U1) ∪ f -1 (Ui) ∪ f -1 (Ui+1) for 1 ≤ i ≤ n - 1.
• (f) S1 = f -1 (U1) ∩ V1 and S2 = f -1 (U1) ∩ V2.

Intuitively, the vertices in the sets S1 and S2 from condition (b) above are those that close the cycle (i.e. that are connected to unit U1). These have to be in every bag as some of their neighbors might only appear on the last unit Un. If all neighbors of S1 and S2 already appear in U1 ∪ U2 then we need consider only paths as unit graphs instead of cycles, and the pathwidth is hence decreased by 2 ∗ UnitCap.

3.3 An Algorithm for the SPUP

By Theorem 2 we know that if a SPUP instance is solvable then there is a path decomposition with specific properties. But we still need an algorithm for finding such suitable path decompositions. Many algorithms for finding path decompositions of bounded width have been proposed in the literature. But, for the SPUP we want to find path decompositions P with specific properties:

• The paths should be short (the number of bags reflects the number of units); and hence,
• The bags should be rather full (in "good" solutions the units will be filled up).
• The construction of the bags must be interleaved with checking the additional constraints.

Below we introduce an algorithm that fits the bill; it is inspired by the algorithm for finding hypertree decompositions from [Gottlob et al., 2002]. This non-deterministic algorithm does the following: The bags on the path decomposition are guessed. The initial bag partitions the graph into a set of remaining components that are recursively processed simultaneously. A single bag suffices to remember which part of the graph has already been processed; the bag separates the processed part of the graph from the remaining components. Consequently, all we have to store is the current bag and the remaining components. It turns out that for this we only need logarithmic space, and thus the algorithm runs in NLOGSPACE, and hence in polynomial time [Cook, 1971].

In addition to the bags the unit function is guessed, too. According to condition (d) from above all neighbors of any vertex in G occur in three consecutive bags in P. Hence, for checking locally that the unit function is correct it suffices to remember three bags at each step.

Due to the different roles played by the units that make up a bag, the DECIDESPUP algorithm operates at the level of units rather than bags.

DECIDESPUP(G)

1 Guess disjoint non-empty U1,U2 ⊆ V (G) with |Ui ∩ V1| ≤ UnitCap ≥ |Ui ∩ V2| 2 CR ←G\ (U1 ∪U2) 3 if DECIDESPUP (CR, 〈U1,U2〉, 〈U1,U2〉) 4 then ACCEPT 5 else REJECT DECIDESPUP(CR, 〈U1, U2〉, 〈Ui-1, Ui〉) 1 if CR = ∅ 2 then 3 if ∀v ∈ U1 nb(v) ⊆ U1 ∪ U2 ∪ Ui and ∀v ∈ Ui nb(v) ⊆ Ui-1 ∪ Ui ∪ U1 4 then ACCEPT 5 else REJECT 6 else 7 Guess non-empty Ui+1 ⊆ V (⋃ CR) with |Ui+1 ∩ V1| ≤ UnitCap ≥ |Ui+1 ∩ V2| 8 For v ∈ Ui check nb(v) ⊆ (Ui-1 ∪ Ui ∪ Ui+1) 9 C ′R ← (CR \ Ui+1) 10 DECIDESPUP (C ′R, 〈U1, U2〉, 〈Ui, Ui+1〉)

Upon initialization (l. 1-5) the first two units are guessed as subsets of the vertices of the input G (l. 1). Throughout a run of the algorithm the remaining components are stored in CR (l. 2). We then proceed to the recursive case (l. 3-5).

While recursively processing G (l. 1-10) we consider two cases: (1) If there are no remaining components (l. 1) we check the termination condition in l. 3. The neighbors of U1 have to appear somewhere on the first, second, or last unit, while the neighbors of the last unit have to appear somewhere on the second-to-last, last, or first unit. Hence we store U1 and U2, as well as a a "predecessor" unit Ui-1 and a "middle" unit Ui throughout a run of the algorithm; upon termination Ui-1 is the second-to-last, and Ui is the last unit in the cycle. The recursive procedure is first called with Ui-1 = U1 and Ui = U2, and at each step the contents of the current bag is given by the union of U1 with Ui-1 ∪ Ui. (2) Otherwise, a "successor" unit Ui+1 is guessed (l. 7). In a solution, all neighbors of vertices assigned to Ui are guaranteed to appear in Ui-1 ∪ Ui ∪ Ui+1 - this is checked in l. 8. For Ui-1 this will already have been established (if i > 2), and hence in the next step Ui and Ui+1 together with U1 are again a proper separator. In l. 9 the vertices just assigned to Ui+1 are deleted from the remaining components, and in l. 10 the same procedure is called recursively.

Using this algorithm we can show the following:

Theorem 3 (Tractability of SPUDP). The decision problem for the SPUP is solvable by the algorithm DECIDESPUP in NLOGSPACE for InterUnitCap = 2 and any given fixed value of UnitCap.

Proof. First observe that if the algorithm accepts then there is a solution for the SPUP; moreover, if there is a solution of the SPUP, this clearly can be guessed. We still have to show that the workspace required by DECIDESPUP is logarithmic in the size of the input. The size of the currently retained units is bounded; hence these can be stored in logarithmic space. Moreover, the currently retained units separate the part of the input graph that has already been processed from the remaining components. Hence we only have to represent the remaining components. At each step their number is bounded by 2 ∗ 2 ∗ UnitCap: For the current units Ui-1 and Ui there can be at most 2 ∗UnitCap neighbors not yet assigned; in the worst case these can all belong to different connected components. Each of the remaining connected components can be represented by a single vertex; hence we can get by with logarithmic space.

Answer Extraction

For actually obtaining a solution to a SPUP instance we face the following problem: In general it is not possible to remember the contents of all the bags in logarithmic space. Theoretically this problem can be solved as follows: On a first accepting run of DECIDESPUP we clearly can remember the first bag's contents in logarithmic space. We can then run DECIDESPUP again with a fixed first bag, and so forth. Hence the following holds:

Theorem 4 (Tractability of SPUSP). The problem of finding a solution to the SPUP is solvable in NLOGSPACE for InterUnitCap = 2 and any given fixed value of UnitCap.

Note that the problem of answer extraction disappears when actually implementing the non-deterministic algorithm on a deterministic computer; cf. Section 3.5.

Towards an Efficient Algorithm

We next make a number of observations that can be exploited to turn DECIDESPUP into a practically efficient algorithm.

Guiding the Guessing Not all zones and sensors assigned to units have to be chosen randomly. At most UnitCap neighbors of sensors and zones on the first unit can be assigned to the last unit. Hence the following holds: 2

Moreover, the neighbors of U1 not assigned to U1 or U2 may only be guessed in the last step, where the number of unprocessed sensors (or zones) is at most UnitCap.

Starting from i ≥ 2 we have the stronger:

2 We denote by nbs(U) (nbz(U)) the set of sensors (zones) that are adjacent in the input graph to zones (sensors) assigned to U.

Finding Optimal Solutions First Next recall that "good" solutions correspond to short path decompositions with filledup bags, and the number of units used in the solution of a SPUP instance G = (V1, V2,E) is bounded by lb = ⌈ max (|V1|,|V2|) UnitCap ⌉ from below and by ub = max (|V1|, |V2|) from above. Hence we can apply iterative deepening search: First, try to find a solution with lb units; if that fails increase lb by one; hence the first solution found will be optimal. This yields the following:

Corollary 1 (Tractability of SPUOP). On connected input graphs the SPUOP is solvable in NLOGSPACE.

Note that branch-and-bound-search (on the number of units used) can not be used: E.g. a K6,6 graph does not admit solutions with more than three units.

Symmetry Breaking We already observed that cycles are more general unit graphs than paths. But with cycles for unit graphs there are two types of rotational symmetry: For a solution with unit graph vU1 , . . . , vUn , vU1 there is (1) a solution vU2 , . . . , vUn , vU1 , vU2 , etc.; in addition there also is (2) the solution vU1 , vUn , vUn-1 , . . . , vU2 , vU1 . We can break these symmetries by stipulating that

• the first sensor is assigned to unit U1; and
• the second sensor appears somewhere on the first half of the cycle.

3.4 SPUOP andMultiple Connected Components

Next let us discuss the problem of finding optimal solutions when the input graph consists of more than one connected component. Here, part of the problem is that any two connected components may either have to be assigned to the same, or to two distinct unit graph(s). A priori it is unclear which of the two choices leads to better results. E.g. if we assume that UnitCap = 2 then two K3,3 should be placed on one cyclic unit graph, while a K6,6 must stand alone. We leave the complexity of the SPUOP on arbitrary input graphs as an open problem - but we are able to show the following:

Theorem 5 (Tractability of SPUOP on Multiple Connected Components). For InterUnitCap = 2 and any given value of UnitCap the optimization problem for the SPUP on multiple connected components is solvable in NLOGSPACE if there are only logarithmically many connected components in the input graph.

Proof. (Sketch) Let a graph with c connected components be given as the union ⋃i=1..c Gi of bipartite graphs Gi = (V1,i, V2,i,Ei). The possible number of unit graphs in optimal solutions ranges from 1 to c. Set V1 = ⋃i V1,i and V2 = ⋃i V2,i. The number of units used is bounded by lb = ⌈ max (|V1|,|V2|) UnitCap ⌉ from below and ub = ∑i max (|V1,i|, |V2,i|) from above. For the lower bound we assume all components fit on a single unit graph; for the upper bound we consider the c individual upper bounds separately.

Next observe that also in the case of multiple connected components a solution to the SPUP gives rise to a path decomposition of a special form: Assume a SPUP instance given by a graph G = ⋃ Gi is solvable with a solution graph G∗ consisting of m connected components, and using n units in total. By concatenating the path decompositions as constructed in the proof of Theorem 2, we obtain a single path decomposition of length n-m. Mutatis mutandis an appropriate version of Theorem 2 is obtained.

Likewise the algorithm DECIDESPUP can be adjusted to guess appropriate path decompositions: We have to distinguish between remaining components that are currently being processed and those that are still untouched. The key is then to ensure that a new "cyclic" segment of the path decomposition may only be started if the set of remaining components that are still currently being processed is empty; i.e. there are no unassigned neighboring sensors or zones left.

Observe that the total number of remaining connected components at each step is now bounded by (4 ∗ UnitCap) + c, where c is the number of connected components in the input graph. Hence we stay within the logarithmic space bound if there are not more than logarithmically many connected components in the input graph.

3.5 Implementation

We prototypically implemented the DECIDESPUP algorithm in Java, replacing the non-determinism by a backtracking search mechanism. Our implementation can only handle connected input graphs.

In [Gottlob and Samer, 2008] a deterministic backtracking version of the non-deterministic hypertree decomposition algorithm from [Gottlob et al., 2002] is described, and the issues we face when making DECIDESPUP deterministic are very similar. To avoid repeated sub-computations we store pairs of bags and remaining components that could not be decomposed:

Observation 1 (Avoidable Sub-Computations). Assume a pair of a bag B and a set of remaining components CR could not be decomposed by DECIDESPUP. If the same pair 〈B, CR〉 occurs again on a run of DECIDESPUP it also cannot be decomposed.

If we use iterative deepening search we also have to store the number of remaining units when encountering a dead-end - it may be possible to decompose the remaining components using more units. We don't store successful pairs - the first such pair occurs when finding a solution.

It turns out that for identifying unsuccessful pairs of bags and remaining components it is enough to store the bag plus the unassigned neighbors:

Lemma 2 (Identifying Remaining Components). Given the contents of a bag and the set of currently unassigned neighbors at any step throughout a run of DECIDESPUP the remaining components are uniquely determined.

Proof. Assume to the contrary that we have calls

1. DECIDESPUP(CR, 〈U1,U2〉, 〈Ui-1,Ui〉, and
2. DECIDESPUP(C ′R, 〈U1,U2〉, 〈Ui-1,Ui〉,

both with the same unassigned neighbors V (of U1 and Ui).

First assume that we have different remaining connected components CR and C ′R on the same set of vertices. This immediately leads to a contradiction.

Next assume that there is a vertex v0 ∈ CR that is not in C ′R, and hence not in V . This v0 cannot be part of the current bag B = U1 ∪ Ui-1 ∪ Ui as this is the same in the calls 1) and 2). Hence assume that, in the run leading to the call 2), v0 is assigned to Uj where j < (i - 1). We know that there is a path v0, v1, . . . , vn in CR leading from v0 to some vn ∈ V such that none of the vi, 0 ≤ i ≤ n is in B. Hence, in the run leading to the call 2), for one of the pairs vi, vi+1 the test nb(vi) ⊆ (Uk-1 ∪ Uk ∪ Uk+1) (k < i) must have failed.

As there are only polynomially many possible pairs of current bags and unassigned neighbors, and each of them is constructed at most once, the overall runtime of our implementation of the DECIDESPUP algorithm is polynomial, too.

In order to detect no-good branches in the search tree early we implemented a form of two-step forward-checking: We check whether there is enough space for the open neighbours of the current unit on the current plus the next unit (step one), and do the same for the open neighbours of these open neighbours (step two).

Finally observe that for the backtracking search we have to store the choices made, and hence answer extraction is easy.

4 Evaluation

As already stated in the introduction, in addition to the methods previously used in industry we have also developed encodings of the PUOP in SAT and CSP solving, as well as answer set and integer programming. We then proceeded to adapt these encodings to the SPUOP, combining the key insights from the DECIDESPUP algorithm with advanced solving techniques from the respective areas; these encodings, together with an evaluation of their performance, are described in [Aschinger et al., 2011].

We have used these encodings, both adapted and not, to compare our implementation of the DECIDESPUP algorithm against; the evaluation was done using a set of instances that we received from our partners in industry. A small excerpt from our experimental results is shown in Table 1, where each line is a representative result for a different class of problem instances. We imposed a ten minute time limit, a "*" indicates a timeout, and runtimes are in seconds. The number of units needed in optimal solutions is denoted by "Cost". CSP denotes a PUOP encoding in ECLiPSe Prolog, and CSP DECIDESPUP the adaption thereof to the SPUOP. It can

be seen that our prototype implementation of DECIDESPUP

can find optimal solutions much faster than the (non-adapted) encoding as a CSP. But encodings of the SPUOP in general purpose AI frameworks such as SAT or CSP in general perform much better than our prototype implementation if they are adapted to exploit the key insights of the DECIDESPUP algorithm [Aschinger et al., 2011].

On the one hand, none of the adapted encodings provably runs in polynomial time; on the other hand, these encodings seem to be much better at detecting no-good branches in the search tree early than our implementation that tries to do so using the two-step look-ahead scheme described above.

5 Related and FutureWork

In this work we have shown how the Special Partner Units Configuration Problem can directly be tackled by computing a path decomposition of the input graph. More typically, structural problem decomposition methods such as path, tree, and hypertree decompositions are used to identify classes of problem instances that can be solved in polynomial time; for an example of this usage in a logic-based formalism for configuration problems see [Gottlob et al., 2007].

While our results clearly advance the state-of-the art of the PUP, there are a number of questions that deserve further research efforts. One important direction is the study of search heuristics so as to achieve a further speedup of the runtime. On the more theoretical side, it may be worthwhile studying two problems of currently unknown complexity: (i) the PUP and PUOP in case InterUnitCap is fixed but greater than 2, and (ii) the case of SPUOP where there are more than O(log n) connected components in the input graph.

Acknowledgments

We greatly acknowledge the constructive criticism we received from the reviewers.