Translation¶

In this section we describe the two-step translation from COOM to ASP. This translation consists of a first conversion from COOM to a serialized fact format which closely resembles the COOM language. Subsequently, this gets processed into a refined fact format used for solving.

We use a simplified version of the Travel Bike example for demonstration.

For more information on the two fact formats head to the Encodings section.

COOM modelSerializationRefined facts

model.coom

product {
    num .#/l      0-200   totalVolume
    num .#/l      0-200   requestedVolume
    Carrier               carrier
    Frame                 frame
}

structure Carrier {
    0..3 Bag            bag
}

structure Frame {
    0..2 Bag            bag
}

enumeration Bag {
    attribute num/l volume

    B20  = ( 20,  250)
    B50  = ( 50,  600)
    B100 = (100, 1200)
}

behavior {
    explanation "The bike can have a maximum of 4 bags."
    require count(carrier.bag) + count(frame.bag) <= 4

    explanation "The total volume of the bags should be equal to the sum of the volumes of all bags on the carrier and the frame."
    require totalVolume = sum(carrier.bag.volume) + sum(frame.bag.volume)

    explanation "The total volume must be greater than or equal to the requested volume."
    require totalVolume >= requestedVolume
}

The first step of the translation to ASP closely resembles the COOM language.

model-serialized.lp

coom_structure("product").
coom_feature("product","totalVolume","num",1,1).
coom_range("product","totalVolume",0,200).
coom_feature("product","requestedVolume","num",1,1).
coom_range("product","requestedVolume",0,200).
coom_feature("product","carrier","Carrier",1,1).
coom_feature("product","frame","Frame",1,1).

coom_structure("Carrier").
coom_feature("Carrier","bag","Bag",0,3).

coom_structure("Frame").
coom_feature("Frame","bag","Bag",0,2).

coom_enumeration("Bag").
coom_attribute("Bag","volume","num").
coom_option("Bag", "B20").
coom_attribute_value("Bag","B20","volume",20).
coom_option("Bag", "B50").
coom_attribute_value("Bag","B50","volume",50).
coom_option("Bag", "B100").
coom_attribute_value("Bag","B100","volume",100).

coom_behavior(0).
coom_context(0,"product").
coom_require(0,"count(carrier.bag)+count(frame.bag)<=4").
coom_binary("count(carrier.bag)+count(frame.bag)<=4","count(carrier.bag)+count(frame.bag)","<=","4").
coom_binary("count(carrier.bag)+count(frame.bag)","count(carrier.bag)","+","count(frame.bag)").
coom_function("product","count(carrier.bag)","count","carrier.bag").
coom_path("carrier.bag",0,"carrier").
coom_path("carrier.bag",1,"bag").
coom_function("product","count(frame.bag)","count","frame.bag").
coom_path("frame.bag",0,"frame").
coom_path("frame.bag",1,"bag").
coom_number("4",4).

coom_behavior(1).
coom_context(1,"product").
coom_require(1,"totalVolume=sum(carrier.bag.volume)+sum(frame.bag.volume)").
coom_binary("totalVolume=sum(carrier.bag.volume)+sum(frame.bag.volume)","totalVolume","=","sum(carrier.bag.volume)+sum(frame.bag.volume)").
coom_path("totalVolume",0,"totalVolume").
coom_binary("sum(carrier.bag.volume)+sum(frame.bag.volume)","sum(carrier.bag.volume)","+","sum(frame.bag.volume)").
coom_function("product","sum(carrier.bag.volume)","sum","carrier.bag.volume").
coom_path("carrier.bag.volume",0,"carrier").
coom_path("carrier.bag.volume",1,"bag").
coom_path("carrier.bag.volume",2,"volume").
coom_function("product","sum(frame.bag.volume)","sum","frame.bag.volume").
coom_path("frame.bag.volume",0,"frame").
coom_path("frame.bag.volume",1,"bag").
coom_path("frame.bag.volume",2,"volume").

coom_behavior(2).
coom_context(2,"product").
coom_require(2,"totalVolume>=requestedVolume").
coom_binary("totalVolume>=requestedVolume","totalVolume",">=","requestedVolume").
coom_path("totalVolume",0,"totalVolume").
coom_path("requestedVolume",0,"requestedVolume").

The refined facts capture the original configuration problem but are independent of COOM. The resulting structure is that of a tree where every variable of the model is explicitly mentioned and the root represents the object to be configured. Variables can be either parts or attributes. Moreover, not all variables are necessarily included in the solution and an excluded variable renders all variables in its subtree excluded as well.

Configuration tree

The configuration tree of the simplified travel bike is displayed in the figure above. Nodes belonging to parts are highlighted in yellow and those belonging to attributes in green. The third bag of the carrier and the second bag of the frame are highlighted in a lighter color, meaning that these variables are undefined and not included in the solution. This automatically renders their subnodes undefined as well. Note that for the sake of readability variable names are abbreviated. Cardinalities of features are treated by grouping variables belonging to the same feature and with the same parent variable in sets (represented by dashed circles in the diagram).

model-refined.lp

part("product").
part("Carrier").
part("Frame").

integer("product.totalVolume").
range("product.totalVolume",0,200).

integer("product.requestedVolume").
range("product.requestedVolume",200,200).

discrete("Bag").
domain("Bag","B20").
domain("Bag","B50").
domain("Bag","B100").

discrete("Bag.volume").
domain("Bag.volume",20).
domain("Bag.volume",50).
domain("Bag.volume",100).

type("root","product").
type("root.totalVolume[0]","product.totalVolume").
type("root.requestedVolume[0]","product.requestedVolume").
type("root.carrier[0]","Carrier").
type("root.frame[0]","Frame").
type("root.frame[0].bag[0]","Bag").
type("root.frame[0].bag[1]","Bag").
type("root.carrier[0].bag[0]","Bag").
type("root.carrier[0].bag[1]","Bag").
type("root.carrier[0].bag[2]","Bag").
type("root.frame[0].bag[0].volume[0]","Bag.volume").
type("root.frame[0].bag[1].volume[0]","Bag.volume").
type("root.carrier[0].bag[0].volume[0]","Bag.volume").
type("root.carrier[0].bag[1].volume[0]","Bag.volume").
type("root.carrier[0].bag[2].volume[0]","Bag.volume").

index("root.totalVolume[0]",0).
index("root.requestedVolume[0]",0).
index("root.carrier[0]",0).
index("root.frame[0]",0).
index("root.frame[0].bag[0]",0).
index("root.frame[0].bag[1]",1).
index("root.carrier[0].bag[0]",0).
index("root.carrier[0].bag[1]",1).
index("root.carrier[0].bag[2]",2).
index("root.carrier[0].bag[2].volume[0]",0).
index("root.carrier[0].bag[1].volume[0]",0).
index("root.carrier[0].bag[0].volume[0]",0).
index("root.frame[0].bag[1].volume[0]",0).
index("root.frame[0].bag[0].volume[0]",0).

parent("root.totalVolume[0]","root").
parent("root.requestedVolume[0]","root").
parent("root.carrier[0]","root").
parent("root.frame[0]","root").
parent("root.frame[0].bag[0]","root.frame[0]").
parent("root.frame[0].bag[1]","root.frame[0]").
parent("root.carrier[0].bag[0]","root.carrier[0]").
parent("root.carrier[0].bag[1]","root.carrier[0]").
parent("root.carrier[0].bag[2]","root.carrier[0]").
parent("root.carrier[0].bag[2].volume[0]","root.carrier[0].bag[2]").
parent("root.carrier[0].bag[1].volume[0]","root.carrier[0].bag[1]").
parent("root.carrier[0].bag[0].volume[0]","root.carrier[0].bag[0]").
parent("root.frame[0].bag[1].volume[0]","root.frame[0].bag[1]").
parent("root.frame[0].bag[0].volume[0]","root.frame[0].bag[0]").

explanation(0,"The bike can have a maximum of 4 bags.").
constraint((0,"count(root.carrier.bag)+count(root.frame.bag)<=4"),"boolean").
binary("count(root.carrier.bag)+count(root.frame.bag)<=4","count(root.carrier.bag)+count(root.frame.bag)","<=","4").
binary("count(root.carrier.bag)+count(root.frame.bag)","count(root.carrier.bag)","+","count(root.frame.bag)").
function("count(root.carrier.bag)","count","root.carrier.bag").
set("root.carrier[0].bag[0]","root.carrier.bag").
set("root.carrier[0].bag[1]","root.carrier.bag").
set("root.carrier[0].bag[2]","root.carrier.bag").
function("count(root.frame.bag)","count","root.frame.bag").
set("root.frame[0].bag[0]","root.frame.bag").
set("root.frame[0].bag[1]","root.frame.bag").
number("4",4).

explanation(1,"The total volume is equal to the sum of the volumes of all bags on the carrier and the frame.").
constraint((1,"root.totalVolume[0]=sum(root.carrier.bag.volume)+sum(root.frame.bag.volume)"),"boolean").
binary("root.totalVolume[0]=sum(root.carrier.bag.volume)+sum(root.frame.bag.volume)","root.totalVolume[0]","=","sum(root.carrier.bag.volume)+sum(root.frame.bag.volume)").
binary("sum(root.carrier.bag.volume)+sum(root.frame.bag.volume)","sum(root.carrier.bag.volume)","+","sum(root.frame.bag.volume)").
function("sum(root.carrier.bag.volume)","sum","root.carrier.bag.volume").
set("root.carrier[0].bag[2].volume[0]","root.carrier.bag.volume").
set("root.carrier[0].bag[1].volume[0]","root.carrier.bag.volume").
set("root.carrier[0].bag[0].volume[0]","root.carrier.bag.volume").
function("sum(root.frame.bag.volume)","sum","root.frame.bag.volume").
set("root.frame[0].bag[1].volume[0]","root.frame.bag.volume").
set("root.frame[0].bag[0].volume[0]","root.frame.bag.volume").

explanation(2,"The total volume must be greater than or equal to the requested volume.").
constraint((2,"root.totalVolume[0]>=root.requestedVolume[0]"),"boolean").
binary("root.totalVolume[0]>=root.requestedVolume[0]","root.totalVolume[0]",">=","root.requestedVolume[0]").

constraint(("Bag","root.frame[0].bag[0]"),"table").
constraint(("Bag","root.frame[0].bag[1]"),"table").
constraint(("Bag","root.carrier[0].bag[0]"),"table").
constraint(("Bag","root.carrier[0].bag[1]"),"table").
constraint(("Bag","root.carrier[0].bag[2]"),"table").
column(("Bag","root.frame[0].bag[0]"),0,1,"root.frame[0].bag[0].volume[0]").
column(("Bag","root.frame[0].bag[1]"),0,1,"root.frame[0].bag[1].volume[0]").
column(("Bag","root.carrier[0].bag[0]"),0,1,"root.carrier[0].bag[0].volume[0]").
column(("Bag","root.carrier[0].bag[1]"),0,1,"root.carrier[0].bag[1].volume[0]").
column(("Bag","root.carrier[0].bag[2]"),0,1,"root.carrier[0].bag[2].volume[0]").
column(("Bag","root.frame[0].bag[0]"),0,0,"root.frame[0].bag[0]").
column(("Bag","root.frame[0].bag[1]"),0,0,"root.frame[0].bag[1]").
column(("Bag","root.carrier[0].bag[0]"),0,0,"root.carrier[0].bag[0]").
column(("Bag","root.carrier[0].bag[1]"),0,0,"root.carrier[0].bag[1]").
column(("Bag","root.carrier[0].bag[2]"),0,0,"root.carrier[0].bag[2]").
allow("Bag",(0,1),"B20").
allow("Bag",(0,2),"B50").
allow("Bag",(0,0),"B100").
allow("Bag",(1,0),100).
allow("Bag",(1,2),50).
allow("Bag",(1,1),20).

constraint(("root.totalVolume",1),"lowerbound").
constraint(("root.requestedVolume",1),"lowerbound").
constraint(("root.carrier",1),"lowerbound").
constraint(("root.frame",1),"lowerbound").
constraint(("root.carrier[0].bag",0),"lowerbound").
constraint(("root.frame[0].bag",0),"lowerbound").
constraint(("root.frame[0].bag[0].volume",1),"lowerbound").
constraint(("root.frame[0].bag[1].volume",1),"lowerbound").
constraint(("root.carrier[0].bag[0].volume",1),"lowerbound").
constraint(("root.carrier[0].bag[1].volume",1),"lowerbound").
constraint(("root.carrier[0].bag[2].volume",1),"lowerbound").
set("root.totalVolume[0]","root.totalVolume").
set("root.requestedVolume[0]","root.requestedVolume").
set("root.carrier[0]","root.carrier").
set("root.frame[0]","root.frame").
set("root.carrier[0].bag[0]","root.carrier[0].bag").
set("root.carrier[0].bag[1]","root.carrier[0].bag").
set("root.carrier[0].bag[2]","root.carrier[0].bag").
set("root.frame[0].bag[0]","root.frame[0].bag").
set("root.frame[0].bag[1]","root.frame[0].bag").
set("root.frame[0].bag[0].volume[0]","root.frame[0].bag[0].volume").
set("root.frame[0].bag[1].volume[0]","root.frame[0].bag[1].volume").
set("root.carrier[0].bag[0].volume[0]","root.carrier[0].bag[0].volume").
set("root.carrier[0].bag[1].volume[0]","root.carrier[0].bag[1].volume").
set("root.carrier[0].bag[2].volume[0]","root.carrier[0].bag[2].volume").