# PVS-Types

MiniBrass revolves around the central concept of *partial valuation structures* (also called *preference valuation structures*, PVS).
A PVS instance represents a coherent set of soft constraints (or preferences) that all map a solution to the *element type* of the underlying PVS-type.
The element type must also offer a (partial) ordering and a *combination operation* to aggregate several individual valuations.

But let’s first consider an example implemented in the MiniBrass standard library.

*Weighted constraints* assign a weight `w[c]`

to every soft constraint `c`

that acts as a penalty if violated. The overall violation is found
by *summing up* all penalties.

To see it in action, consider the following example

```
include "defs.mbr";
PVS: user1Prefs = new WeightedCsp("user1Prefs") {
soft-constraint c1: 'x > y' :: weights('3');
soft-constraint c2: 'x = y + 2' :: weights('1');
};
output '["x = \(x), y = \(y)"]';
solve user1Prefs;
```

based on a simplistic constraint model

```
include "soft_constraints/minibrass.mzn";
include "pvsTypes_o.mzn";
var 0..3: x;
var 0..3: y;
solve search miniBrass();
```

It can be interpreted as “it’s pivotal that `x`

is greater than `y`

” and it would be even better if the difference were exactly 2.

Our output shows the results to this model

```
Intermediate solution:x = 0, y = 0
Valuations: mbr_overall_user1Prefs = 4
----------
Intermediate solution:x = 2, y = 0
Valuations: mbr_overall_user1Prefs = 0
----------
==========
```

The first found solution (`x = 0, y = 0`

) violates both `x > y`

with penalty 3 and `x = y + 2`

with penalty 1. Hence the score 4.

The second solution (`x = 2, y = 0’) satisfies both soft constraints, thus resulting an overall score of 0.

But how is the type `WeightedCsp`

actually defined?

## Inspecting an existing type

To see this, we take a look at its definition in `defs.mbr`

, found in the `mbr_std`

folder in the `mbr2mzn.jar`

directory (see here).

```
type WeightedCsp = PVSType<bool, int> =
params {
int: k :: default('1000');
array[1..nScs] of int: weights :: default('1');
} in
instantiates with "soft_constraints/mbr_types/weighted_type.mzn" {
times -> weighted_sum;
is_worse -> is_worse_weighted;
top -> 0;
}
offers {
heuristics -> getSearchHeuristicWeighted;
};
```

`WeightedCsp`

shows all important characteristics :

- An
*element type*(the scale, weight, etc. by which we want to order solutions) which here corresponds to`int`

- A
*specification type*which refers to the data type of the soft constraint expressions. Most often, this is`bool`

but sometimes we want something like a cost function that directly maps to`int`

- A combination operation
`weighted_sum`

, which means that we build a some of all violated soft constraints, weighted by their importance - An ordering relation
`is_worse_weighted`

which orders the elements of the element type and a top element (here 0)

The actual implementations of `weighted_sum`

and `is_worse_weighted`

are a MiniZinc function and a MiniZinc predicate, respectively, which are defined in `mbr_types/weighted_type.mzn`

(see here).

```
function var int: weighted_sum(array[int] of var bool: b,
par int: nScs, par int: k, array[int] of par int: weights) =
sum(i in index_set(b)) ( (1 - bool2int(b[i])) * weights[i]);
predicate is_worse_weighted(var int: x, var int: y,
par int: nScs, par int: k, array[int] of par int: weights) =
x > y;
```

These ingredients are all encoded in the PVS type and thus reusable for, e.g., many `WeightedCsp`

instances but also compatible with other PVS types.

## Common PVS types

The following table highlights the commonalities of PVS types. By convention, we always read a predicate `a is_worse_than b`

from left to right.
Hence, for weighted CSP, `a is_worse_than b`

if and only if `a > b`

(since there is a higher violation).

PVS-Type | Spec. / Element type | times | is_worse | top |
---|---|---|---|---|

Weighted CSP | bool / int | weighted_sum | is_greater_than | k (max violation) |

Cost Function Networks | int | sum | is_greater_than | k |

Set-Based Max CSP | bool / set of int | set_union | superset | {} |

Fuzzy CSP | [0.0 1.0] | min | is_less_than | 1.0 |

All standard types can be found here.

- Previous
- Next