Decomposable Global Cost Functions

This page gives a quick look to decomposable global cost function included in ToulBar2.

  1. What is a Decomposable Global Cost Function ?
  2. WeightedAmong Global Cost Function
  3. WeightedRegular Global Cost Function
  4. WeightedSum Global Cost Function
  5. WeightedOverlap Global Cost Function
  6. Toulbar, Decomposition, and Output
  7. References and others stuffs


What is a Decomposable Global Cost Function ?

The Decomposable global cost functions are global cost functions that can be decomposed into an equivalent cost function network. Actually, only some Berge-Acyclic Global Cost Functions have been added into Toulbar2 :


WeightedAmong Global Cost Function

WeightedAmong and Violation Measure

The Among global constraint restrains the number of variables of its scope to take a bounded number of times a value from a given set. The global cost function associated to Among is WeightedAmong. This global cost function can be decomposed into a set of ternary constraints with an additionnal set of variables. This decomposition uses the new variables as counters and does a cumulative sum all along the set of ternary cost functions.

Let us note gap as the distance to the bounds, and baseCost as the cost associated to the global cost function. The WeightedAmong can be, currently, associated with three violation measure:

  1. hard : if gap is greater than zero the cost baseCost is returned
  2. lin : the cost gap x baseCost is returned
  3. quad : the cost gap^2 x baseCost is returned

WCSP Format And Example

The following figure presents the WCSP format of WeightedAmong:

arity variable_1 ... variable_arity -1 wamong semantics basecost
nbValueToWatch value_1 ... value_nbValueToWatch
lb ub

The following figure presents an example of WeightedAmong:

WAMONG_hard 4 3 1 1000
3 3 3 3

4 0 1 2 3 -1 wamong hard 1000
2 1 2
1 3
The previous example represents a WCSP with 4 variables. These variables are in the scope of a WeightedAmong which limits the number of times they take the values 1 and 2 to be bounded between 1 and 3. In this case, the semantics is hard and the associated cost is 1000 (i.e. in these case the WeightedAmong is a hard constraint).

For other examples :

Adding a WeightedAmong into Toulbar2's code

To add a WeightedAmong global cost function into Toulbar2's code, you have to use the following procedure:

  1. Constructing a WeightedAmong
    • WeightedAmong(unsigned int _arity, int* _scope);
  2. Using accessors to add the informations (semantics, cost, ...)
    • void addValue(int _value);
    • void setSemantics(string _semantics);
    • void setBaseCost(Cost _baseCost);
    • void setBounds(unsigned int _lb, unsigned int _ub);
  3. add the cost function to the cost function network
    • void addToCostFunctionNetwork(WCSP* wcsp);
Then, the previous example can be added as following:
int* scope = new int[4];
for (int i = 0 ; i < 4 ; i++) scope[i] = i;
WeightedAmong among(4,scope);
among.setSemantics("hard");
among.setBaseCost(1000);
among.addValue(1);
among.addValue(2);
among.setBounds(1,3);
among.addToCostFunctionNetwork(wcsp);


WeightedRegular Global Cost Function

WeightedRegular and Violation Measure

The Regular global constraint restrains a sequence of variables to form a word recognized by a Finite Automaton. The global cost function associated to Regular is WeightedRegular. This global cost function can be decomposed into a set of ternary cost functions which are the table of transitions.

The automaton associated to WeightedRegular is a Weighted Finite Automaton and this automaton holds the violation measure through the cost of its transitions and states (and can encode many violation measures like hamming-based or levenshtien-based).

WCSP Format And Example

The following figure presents the WCSP format of WeightedRegular:

arity variable_1 ... variable_arity -1 wregular
nbStates
nbInitialStates
initialStates_1 cost_start_initialStates_1
...
initialStates_nbInitialStates cost_start_initialStates_nbInitialStates
nbAcceptingStates
acceptingStates_1 cost_end_acceptingStates_1
...
acceptingStates_nbAcceptingStates cost_end_acceptingStates_nbAcceptingStates
nbTransitions
start_t_1 symbol_t_1 end_t_1 cost_t_1
...
start_t_nbTransitions symbol_t_nbTransitions end_t_nbTransitions cost_t_nbTransitions

The following figures present example of WeightedRegular recognizing "a symbol 1 cannot follow another symbol 1 (cost 100)":

WREGULAR 4 2 1 1000
2 2 2 2

4 0 1 2 3 -1 wregular
2
1
0 0
2
0 0
1 1
4
0 0 0 0
0 1 1 0
1 0 0 0
1 1 1 100
The wcsp file can be found here : wregular.wcsp.

Adding a WeightedRegular into Toulbar2's code

To add a WeightedRegular global cost function into Toulbar2's code, you have to use the following procedure:

  1. Constructing a WFA structure (TO BE CHANGED)
    • WFA(int _nbStates);
  2. Constructing a WeightedRegular
    • WeightedRegular(unsigned int _arity, int* _scope);
  3. Using accessors to add the informations (semantics, cost, ...)
    • void setWFA(WFA* _automaton);
  4. add the cost function to the cost function network
    • void addToCostFunctionNetwork(WCSP* wcsp);
Then, the previous example can be added as following:
WFA* automaton=new WFA(2);
automaton->initialStates.push_back(make_pair(0,0));
automaton->acceptingStates.push_back(make_pair(0,0));
automaton->acceptingStates.push_back(make_pair(1,0));
automaton->transitions.push_back(new WTransition(0,0,0,0));
automaton->transitions.push_back(new WTransition(0,1,1,0));
automaton->transitions.push_back(new WTransition(1,0,0,0));
automaton->transitions.push_back(new WTransition(1,1,1,100));

int* scope = new int[4];
for (int i = 0 ; i < 4 ; i++) scope[i] = i;
WeightedRegular regular(4,scope);
regular.setWFA(automaton);
regular.addToCostFunctionNetwork(wcsp);


WeightedSum Global Cost Function

WeightedSum and Violation Measure

The Sum global constraint tests if the sum of a set of variables match with an comparator (for example = 5). The global cost function associated to Sum is WeightedSum. This global cost function can be decomposed into a set of ternary constraints with an additionnal set of variables. This decomposition uses the new variables as counter and does a cumulative sum all along the set of ternary cost functions. Finally, an unary cost function ensures the comparator.

Note : This decomposition can use an exponential size (domains of counter variables).

Let us note <> the comparator, K the value associated to the comparator, and Sum the result of the sum over the variables. For each comparator, the gap is defined according to the distance as follows:

According to gap, there are 3 violation semantics :
  1. hard : if gap is greater than zero the cost baseCost is returned
  2. lin : the cost gap x baseCost is returned
  3. quad : the cost gap^2 x baseCost is returned

WCSP Format And Example

The following figure presents the WCSP format of WeightedSum:

arity variable_1 ... variable_arity -1 wsum semantics basecost
<> K

The following figure presents an example of WeightedAmong:

WSUM_hard 4 3 1 1000
3 3 3 3

4 0 1 2 3 -1 wsum hard 1000
== 4
The previous example represents a WCSP with 4 variables. These variables are in the scope of a WeightedSum with == 4. In this case the semantics is hard and the associated cost is 1000 (i.e. in these case the WeightedSum is a hard constraint).

For other examples :

Adding a WeightedSum into Toulbar2's code

To add a WeightedSum global cost function into Toulbar2's code, you have to use the following procedure:

  1. Constructing a WeightedSum
    • WeightedSum(unsigned int _arity, int* _scope);
  2. Using accessors to add the informations (semantics, cost, ...)
    • void setSemantics(string _semantics);
    • void setBaseCost(Cost _baseCost);
    • void setComparator(string _comparator);
    • void setRightRes(int _rightRes);
  3. add the cost function to the cost function network
    • void addToCostFunctionNetwork(WCSP* wcsp);
Then, the previous example can be added as following:
int* scope = new int[4];
for (int i = 0 ; i < 4 ; i++) scope[i] = i;
WeightedSum sum(4,scope);
sum.setSemantics("hard");
sum.setBaseCost(1000);
sum.setComparator("==");
sum.setRightRes(4);
sum.addToCostFunctionNetwork(wcsp);


WeightedOverlap Global Cost Function

WeightedOverlap and Violation Measure

The Overlap global constraint limits the overlaps between two sequence of variables X, Y (i.e. set the fact that Xi and Yi take the same value (not equal to zero)). The global cost function associated to Overlap is WeightedOverlap. This global cost function can be decomposed into a set of ternary constraints with an additionnal set of variables. This decomposition uses two sets of new variables : the first as an overlap flag and a second one as a cumulative sum. Finally, an unary cost function ensures that the overlap respects a given value.

As WeightedSum, the control of the overlap can be done thanks to a comparator and a right hand member. Let us note gap, the gap between the effective overlap and the right hand member. Accordingly to gap, there are 3 violation semantics :

  1. hard : if gap is greater than zero the cost baseCost is returned
  2. lin : the cost gap x baseCost is returned
  3. quad : the cost gap^2 x baseCost is returned

WCSP Format And Example

The following figure presents the WCSP format of WeightedOverlap:

arity variable_1 ... variable_arity -1 woverlap semantics basecost
<> K

Note : The first half of the scope corresponds to the first sequence of variable X, and the second half to Y

The following figure presents an example of WeightedOverlap:

WOVERLAP_hard 4 3 1 1000
3 3 3 3

4 0 1 2 3 -1 woverlap hard 1000
< 1
The previous example represents a WCSP with 4 variables : X = { 0, 1 }, Y = { 2, 3 }. And, the overlap between X and Y must less than 1. In this case the semantics is hard and the associated cost is 1000 (i.e. in these case the WeightedOverlap is a hard constraint).

Adding a WeightedOverlap into Toulbar2's code

To add a WeightedOverlap global cost function into Toulbar2's code, you have to use the following procedure:

  1. Constructing a WeightedOverlap
    • WeightedOverlap(unsigned int _arity, int* _scope);
  2. Using accessors to add the informations (semantics, cost, ...)
    • void setSemantics(string _semantics);
    • void setBaseCost(Cost _baseCost);
    • void setComparator(string _comparator);
    • void setRightRes(int _rightRes);
  3. add the cost function to the cost function network
    • void addToCostFunctionNetwork(WCSP* wcsp);
Then, the previous example can be added as following:
int* scope = new int[4];
for (int i = 0 ; i < 4 ; i++) scope[i] = i;
WeightedOverlap over(4,scope);
over.setSemantics("hard");
over.setBaseCost(1000);
over.setComparator("<");
over.setRightRes(1);
over.addToCostFunctionNetwork(wcsp);


Toulbar, Decomposition, and Output

When the solution of a problem is displayed or writen, all variables are used (even the new counter variables).

me@computer$ ./toulbar wsum_quad.wcsp -s
./bin/Linux/toulbar2 version : 0.9.4.0, copyright (c) INRA 2012
loading wcsp file: /export/home/metivier/web/www/decomposable/instance/wsum_quad.wcsp
Read 4 variables, with 3 values at most, and 5 cost functions, with maximum arity 4.
Cost function decomposition time : 0 seconds.
Preprocessing Time : 0.01 seconds.
0 unassigned variables, 0 values in all current domains (med. size:0) and 0 non-unary cost functions (med. degree:0)
Initial lower and upper bounds: [40,1000[
New solution: 40 (0 backtracks, 0 nodes, depth 1)
1 1 1 1 0 1 2 3 4
Optimum: 40 in 0 backtracks and 0 nodes and 0.01 seconds.
end.

The 4 first variables (in green) are the variables from the initial model and the 5 lasts (in red) are the new counter variables.


References and others stuffs