%%% Combined Configuration Problem (CCP) %%%

%%%%%%%%%%%%%%%%%%%
PROBLEM DESCRIPTION
%%%%%%%%%%%%%%%%%%%
This problem is an abstract problem derived from a combination of several SIEMENS product configuration 
problems encountered in practice (railway interlocking systems, automation systems, etc.).

Input: 
(1) a directed acyclic graph (DAG) specified by a set of its edges, where an edge corresponds to an ordered pair of vertices; 
(2) type and size of each vertex, 
(3) sets of vertices defining specific paths in the input DAG, 
(4) a number of available colors,
(5) a number of available bins and their capacity, 
(6) a set of areas,
(7) sets of DAG vertices defining possible border elements of each area and
(8) a maximal number of border elements per area.

The problem is a combination of 5 sub problems, which usually can be required to be solved separately or in combinations.
We submit the CCP as one problem, because we have empirically discovered that the inclusion of all parts 
of the problem drastically deteriorates the solving process with respect to the runtime.

%%% P1 Coloring
"Every vertex must have exactly one color."
Origin: In the railway domain the given DAG represents the track layout of
a railway line. A coloring can then be thought as an assignment of resources 
(e.g. computer) to the elements of the railway line. This requirement is frequently 
used in configuration problems similar to the the Rack Configuration Problem [1] and 
the House configuration problem [2] (e.g. during the assignment of things to cabinets, 
cabinets to rooms, etc.).

%%% P2 Bin-Packing 
"For every color a bin-packing problem must be solved. Every
vertex must be assigned to exactly one bin of its color and for every bin it
holds that the sum of sizes must be smaller or equal to the bin capacity."
Origin: In real-world scenarios different infrastructure elements may require
different amount of a resource. This may be hardware requirements, e.g.
a signal requiring a certain number of hardware parts, or software requirements, 
e.g. an infrastructural element requiring a specific processing
time. These requirements are appearing in configuration problems similar
to the the Rack Configuration Problem [1] and 
the House configuration problem [2].

%%% P3 Disjoint Paths 
"Vertices of different paths cannot be colored in the same color"
Origin: In the real-world scenarios this constraint increases availability, i.e. in
the case that one resource fails, it should still be possible to get from a source
vertex of a path to a target vertex of a path. The source and target vertices of the paths are 
vertices that do not have incoming/outcoming edges respectively. 

%%% P4 Matching 
"Each border element must be assigned to exactly one area such
that the number of selected border elements of an area does not exceed the
maximal number of border elements and all selected border elements of an
area have the same color."
Origin: This problem stems from detecting which elements of the graph are
occupied. The border elements function as detectors for object leaving or
entering an area. The PUP problem [3,4] is the more elaborated example
of this problem.

%%% P5 Connectedness 
"Two vertices with the same color must be connected via
a path, that contains only vertices of that color."
Origin: Usually communication between elements controlled by different resources is more costly, therefore, 
neighboring elements should be assigned to the same resource whenever possible. This problem is a specific version
of the PUP problem [3,4].

[1] Mayer, Bettex, Stumptner and Falkner: 
On solving complex rack configuration problems using CSP methods. 
Proceedings of the IJCAI Workshop on Configuration, 2009.

[2] Friedrich, Ryabokon, Falkner, Haselboeck, Schenner and Schreiner:
(Re)configuration based on model generation. 
Proceedings of the International Workshop on Logics for Component Configuration, 2011.

[3] Aschinger, Drescher, Gottlob, Jeavons and Thorstensen: 
Tackling the Partner Units Configuration Problem. 
Proceedings of the International Joint Conference on Artificial Intelligence, 2011.

[4] Aschinger, Drescher, Friedrich, Gottlob, Jeavons, Ryabokon and Thorstensen: 
Optimization Methods for the Partner Units Problem. 
Proceedings of the CPAIOR, 2011. 

%%%%%%%%%%
PREDICATES
%%%%%%%%%%
Input: nrofcolors/1, nrofbins/1, maxbinsize/1, maxborder/1, edge/2, type/2, size/2, path1/1, path2/1, edge_matching/2
Output: vertex_color/2, vertex_bin/2, bin/3, edge_matching_selected/2, usedcolor/1, usedbin/1

%%%%%%%%%%%%
Input format
%%%%%%%%%%%%
nrofcolors(Color) number of colors
nrofbins(Bin) number of bins
maxbinsize(Capacity) capacity of a bin
maxborder(C) maximal number of selected border elements
edge(Vertex1,Vertex2) edge between Vertex1 and Vertex2 in the DAG 
type(Vertex,Type) type of a vertex
size(Vertex,Size) size of a vertex
pathN(Vertex) a vertex belongs to pathN
edge_matching(Area,Vertex) border elements for an area

%%%%%%%%%%%%%
Output format
%%%%%%%%%%%%%
vertex_color(Vertex,Color) a color of a vertex
vertex_bin(Vertex,Bin) a vertex in a bin
bin(Color,Bin,Vertex) a bin for a colored vertex
edge_matching_selected(Area,Vertex) a selected area for border element
usedcolor(Color) a color used in a solution
usedbin(Bin) a bin used in a solution

%%%%%%%
EXAMPLE
%%%%%%%
%%% Input:
nrofcolors(4). 
nrofbins(3).
maxbinsize(5).
maxborder(3).

edge("b1","s1").
edge("s1","p1").
edge("p1","b2").
edge("b2","p2").
edge("p2","b3").
edge("b3","p3").
edge("p3","s2").
edge("s2","b4").
edge("p1","b5").
edge("b5","e1").
edge("e1","b6").
edge("b6","p3").
edge("b7","s3").
edge("s3","p4").
edge("p4","b8").
edge("b8","p5").
edge("p5","b9").
edge("b9","p6").
edge("p6","s4").
edge("s4","b10").
edge("p4","b11").
edge("b11","e2").
edge("e2","b12").
edge("b12","p6").
edge("p2","p5").

type("b1","b").
type("b2","b").
type("b3","b").
type("b4","b").
type("b5","b").
type("b6","b").
type("b7","b").
type("b8","b").
type("b9","b").
type("b10","b").
type("b11","b").
type("b12","b").
type("e1","e").
type("e2","e").
type("s1","s").
type("s2","s").
type("s3","s").
type("s4","s").
type("p1","p").
type("p2","p").
type("p3","p").
type("p4","p").
type("p5","p").
type("p6","p").

size("b1",1).
size("b2",1).
size("b3",1).
size("b4",1).
size("b5",1).
size("b6",1).
size("b7",1).
size("b8",1).
size("b9",1).
size("b10",1).
size("b11",1).
size("b12",1).
size("e1",2).
size("e2",2).
size("s1",3).
size("s2",3).
size("s3",3).
size("s4",3).
size("p1",4).
size("p2",4).
size("p3",4).
size("p4",4).
size("p5",4).
size("p6",4).

path1("b1").
path1("s1").
path1("p1").
path1("b2").
path1("p2").
path1("b3").
path1("p3").
path1("s2").
path1("b4").
path2("b7").
path2("s3").
path2("p4").
path2("b8").
path2("p5").
path2("b9").
path2("p6").
path2("s4").
path2("b10").

edge_matching("a1","b1").
edge_matching("a1","b2").
edge_matching("a1","b5").
edge_matching("a2","b5").
edge_matching("a2","b6").
edge_matching("a3","b3").
edge_matching("a3","b6").
edge_matching("a3","b4").
edge_matching("a4","b2").
edge_matching("a4","b3").
edge_matching("a4","b8").
edge_matching("a4","b9").
edge_matching("a5","b7").
edge_matching("a5","b8").
edge_matching("a5","b11").
edge_matching("a6","b9").
edge_matching("a6","b12").
edge_matching("a6","b10").
edge_matching("a7","b11").
edge_matching("a7","b12").

%%% Solution:
vertex_color("b1",1).
vertex_color("b10",4).
vertex_color("b11",4).
vertex_color("b12",4).
vertex_color("b2",3).
vertex_color("b3",3).
vertex_color("b4",3).
vertex_color("b5",1).
vertex_color("b6",1).
vertex_color("b7",2).
vertex_color("b8",2).
vertex_color("b9",4).
vertex_color("e1",1).
vertex_color("e2",4).
vertex_color("p1",1).
vertex_color("p2",3).
vertex_color("p3",3).
vertex_color("p4",2).
vertex_color("p5",2).
vertex_color("p6",4).
vertex_color("s1",1).
vertex_color("s2",3).
vertex_color("s3",2).
vertex_color("s4",4).

vertex_bin("b1",2).
vertex_bin("b10",3).
vertex_bin("b11",1).
vertex_bin("b12",3).
vertex_bin("b2",1).
vertex_bin("b3",2).
vertex_bin("b4",3).
vertex_bin("b5",3).
vertex_bin("b6",2).
vertex_bin("b7",3).
vertex_bin("b8",2).
vertex_bin("b9",3).
vertex_bin("e1",1).
vertex_bin("e2",3).
vertex_bin("p1",3).
vertex_bin("p2",2).
vertex_bin("p3",3).
vertex_bin("p4",1).
vertex_bin("p5",3).
vertex_bin("p6",2).
vertex_bin("s1",1).
vertex_bin("s2",1).
vertex_bin("s3",2).
vertex_bin("s4",1).

bin(1,1,"e1").
bin(1,1,"s1").
bin(1,2,"b1").
bin(1,2,"b6").
bin(1,3,"b5").
bin(1,3,"p1").
bin(2,1,"p4").
bin(2,2,"b8").
bin(2,2,"s3").
bin(2,3,"b7").
bin(2,3,"p5").
bin(3,1,"b2").
bin(3,1,"s2").
bin(3,2,"b3").
bin(3,2,"p2").
bin(3,3,"b4").
bin(3,3,"p3").
bin(4,1,"b11").
bin(4,1,"s4").
bin(4,2,"p6").
bin(4,3,"b10").
bin(4,3,"b12").
bin(4,3,"b9").
bin(4,3,"e2").

edge_matching_selected("a1","b1").
edge_matching_selected("a2","b5").
edge_matching_selected("a2","b6").
edge_matching_selected("a3","b4").
edge_matching_selected("a4","b2").
edge_matching_selected("a4","b3").
edge_matching_selected("a5","b7").
edge_matching_selected("a5","b8").
edge_matching_selected("a6","b10").
edge_matching_selected("a6","b9").
edge_matching_selected("a7","b11").
edge_matching_selected("a7","b12").

usedcolor(1).
usedcolor(2).
usedcolor(3).
usedcolor(4).

usedbin(1).
usedbin(2).
usedbin(3).

%%%%%%%%%
Instances
%%%%%%%%%
We divided all instances into 3 sets: simple, moderate and hard. The hard instances were not solved within 
900 seconds using a combination of gringo (version 4.4.0) and clasp (version 3.0.5) on a system with 
Intel i7-3930K CPU (3.20GHz), 64 GB of RAM and running Ubuntu). The moderate instances require more than 30 seconds to find a solution using the same solver/system.

%%%%%%%
AUTHORS
%%%%%%%
Anna Ryabokon, Alpen-Adria-Universität Klagenfurt, Austria
Gottfried Schenner, Siemens AG Österreich, Austria