Optimization Methods for the Partner Units Problem
In this work we present the Partner Units Problem as a novel challenge for optimization methods. It captures a certain type of configuration problem that frequently occurs in industry. Unfortunately, it can be shown that in the most general case an optimi
- PDF / 311,371 Bytes
- 16 Pages / 429.442 x 659.895 pts Page_size
- 83 Downloads / 232 Views
2
Computing Laboratory, University of Oxford Institut f¨ ur Angewandte Informatik, Alpen-Adria-Universit¨ at Klagenfurt
Abstract. In this work we present the Partner Units Problem as a novel challenge for optimization methods. It captures a certain type of configuration problem that frequently occurs in industry. Unfortunately, it can be shown that in the most general case an optimization version of the problem is intractable. We present and evaluate encodings of the problem in the frameworks of answer set programming, propositional satisfiability testing, constraint solving, and integer programming. We also show how to adapt these encodings to a class of problem instances that we have recently shown to be tractable.
1
Introduction
The Partner Units Problem (Pup) has recently been proposed as a new challenge in automated configuration [8]. It captures the essence of a specific type of configuration problem that frequently occurs in industry. 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, where each control unit can be connected to the same 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, for example, a museum where we want to keep track of the number of visitors that populate certain parts (zones) of the building. The doors leading from one zone to another are equipped with 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 units can be kept simple. 1
Work funded by FFG FIT-IT Grant 825071 (Klagenfurt) and EPSRC Grant EP/G055114/1 (Oxford). For ease of presentation and without loss of generality we assume that UnitCap is the same for zones and sensors.
T. Achterberg and J.C. Beck (Eds.): CPAIOR 2011, LNCS 6697, pp. 4–19, 2011. c Springer-Verlag Berlin Heidelberg 2011
Optimization Methods for the Partner Units Problem
5
Let us emphasize 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 should be kept simple. Typical applications include intelligent traffic management, or surveillance and security applications. The Pup has been introduced as a novel benchmark instance at this year’s answer set programming competition [2]. Figure 1 shows a Pup instance and a solution for the case UnitCap = InterUnitCap = 2. In this example six sensors (left) and six zones (right), which are completely inter-connected, are partitioned into
Data Loading...
