welcome: please sign in
location: WeightedSequenceProblem

Weighted-Sequence Problem

Problem Description

In the weighted-sequence problem we are given a set of leaves (nodes) and an integer m — maximum cost. Each leaf is a pair (weight, cardinality) where weight and cardinality are integers. Every sequence (permutation) of leaves is such that all leaves but the first are assigned a color. A colored sequence is associated with the cost. The task is to find a colored sequence with the cost at most m.

For a set S of leaves and an integer m, we denote the corresponding weighted- sequence problem by [S, m]. We say that an integer m is optimal with respect to a set S of leaves if m is the least integer u such that the weighted-sequence problem [S, u] has a solution.

Let M be a sequence of n leaves l_0, ..., l_{n−1}. For each leaf l_i , 0 ≤ i ≤ n − 1, by w(l_i) and c(l_i) we denote its weight and cardinality, respectively. We color each leaf l_i , 1 ≤ i ≤ n − 1, green, red, or blue; the leaf l_0 is not colored. We define the costs of leaves as follows. For the leaf l_0, we set cost(l_0) = w(l_0).

For every colored leaf l_i , 1 ≤ i ≤ n − 1, we set

The cost of the sequence M is the sum of the costs of its colored leaves: cost(M ) = cost(l_1) + ... + cost(l_{n−1}).


Input format

An input consists of the following parts:

Output format

A solution is represented by means of a constant "exists" if there is a tree T and a specification of T in the following format


Given the input:

leafWeightCardinality(1,45,44). leafWeightCardinality(2,21,3). leafWeightCardinality(3,64,74). leafWeightCardinality(4,29,91). leafWeightCardinality(5,80,48). leafWeightCardinality(6,91,8).
leafWeightCardinality(7,10,64). leafWeightCardinality(8,62,79).

innerNode(1). innerNode(2). innerNode(3). innerNode(4).
innerNode(5). innerNode(6). innerNode(7).

num(8). max_total_weight(495).

The output of the solver should look like:

leafPos(1,7). leafPos(2,4). leafPos(3,6). leafPos(4,5). leafPos(5,2).
leafPos(6,1). leafPos(7,0). leafPos(8,3). 

posColor(7,green). posColor(6,red). posColor(5,red). posColor(4,green). 
posColor(3,red). posColor(2,blue). posColor(1,blue). 

Additional sample instances: download

Problem Peculiarities

Type: Search Competition: Both

Notes and Updates


ASP Competition 2013: WeightedSequenceProblem (last edited 2012-11-20 22:13:23 by PatrikSchneider)