welcome: please sign in
location: FinalProblemDescriptions / PartnerUnits

Partner Units general

Problem Description

A given people counting system includes three types of components, namely door sensor, zone, and communication unit. The problem requirements are:

  1. Each zone as well as each door sensor must be connected to exactly one unit;
  2. Each unit can control at most two door sensors and at most two zones;
  3. If a unit controls a door sensor that contributes to a zone controlled by another unit, then the two units must be connected directly, i.e. one unit becomes a partner unit of the other and vice versa;
  4. Each unit can have at most maxPU (>2) partner units.

The solution of the Partner Units problem is defined as follows: Given a consistent configuration of door sensors and zones (encoded in the binary predicate zone2sensor/2), a set of available units (comUnit/1), and a maximum number of allowed partnerunits (maxPU/1), find a valid assignment of units that satisfies all requirements.

Reference: Falkner A, Haselböck A, Schenner G. Modeling Technical Product Configuration Problems. In: Hotz L, Haselböck A, eds. Workshop on Configuration, ECAI2010. Lisbon, Portugal; 2010:40-46.

Predicates

Input format

The predicates comUnit/1 and maxPU/1 define available units and the number of allowed partner units respectively. The fact that a door sensor belongs to a zone is given by means of zone2sensor/2 predicate, e.g. zone2sensor(1,1) means that doorSensor(1) belongs to zone(1).

Output format

A solution to the problem is an assignment of each zone and each sensor to a unit, e.g. unit2sensor(2,1), unit2zone(2,1) means that zone(1) and doorSensor(1) are assigned to the second unit comUnit(2). Connections between partner units are given by the partnerunits/2 predicate, e.g. partnerunits(2,1) indicates a connection between comUnit(2) and comUnit(1).

Example(s)

INPUT

maxPU(3).

comUnit(1). comUnit(2). comUnit(3). comUnit(4). comUnit(5).

% relation between zones and door sensors
zone2sensor(1,1). zone2sensor(1,2). zone2sensor(2,2). zone2sensor(3,2).
zone2sensor(3,5). zone2sensor(3,7). zone2sensor(3,9). zone2sensor(4,2).
zone2sensor(4,3). zone2sensor(4,5). zone2sensor(4,6). zone2sensor(4,8).
zone2sensor(5,5). zone2sensor(5,7). zone2sensor(6,3). zone2sensor(6,5).
zone2sensor(6,6). zone2sensor(6,8). zone2sensor(7,3). zone2sensor(7,6).
zone2sensor(7,7). zone2sensor(7,8). zone2sensor(8,2). zone2sensor(8,3).
zone2sensor(8,4). zone2sensor(8,5). zone2sensor(8,6).

OUTPUT

unit2sensor(1,1). unit2sensor(2,4). unit2sensor(2,8). unit2sensor(3,2). 
unit2sensor(3,3). unit2sensor(4,6). unit2sensor(4,9). unit2sensor(5,5).
unit2sensor(5,7). unit2zone(1,1). unit2zone(1,2). unit2zone(3,3). 
unit2zone(3,5). unit2zone(4,4). unit2zone(4,6). unit2zone(5,7). unit2zone(5,8). 
partnerunits(1,3).partnerunits(2,5).partnerunits(2,4).
partnerunits(3,4).partnerunits(3,5). partnerunits(3,1).
partnerunits(4,5).partnerunits(4,3). partnerunits(4,2).
partnerunits(5,2). partnerunits(5,3). partnerunits(5,4).  

Notes and updates

This is the general version of the twin problem Partner Units (polynomial).

Author(s)

ASP Competition 2011: FinalProblemDescriptions/PartnerUnits (last edited 2011-02-03 15:46:35 by MarioAlviano)