Decomposable Global Cost Functions
This page gives a quick look to decomposable global cost function included in ToulBar2.
- What is a Decomposable Global Cost Function ?
- WeightedAmong Global Cost Function
- WeightedRegular Global Cost Function
- WeightedSum Global Cost Function
- WeightedOverlap Global Cost Function
- Toulbar, Decomposition, and Output
- 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
- WeightedRegular
- WeightedSum
- WeightedOverlap
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:
- hard : if gap is greater than zero the cost baseCost is returned
- lin : the cost gap x baseCost is returned
- quad : the cost gap^2 x baseCost is returned
WCSP Format And Example
The following figure presents the WCSP format of WeightedAmong:
nbValueToWatch value_1 ... value_nbValueToWatch
lb ub
The following figure presents an example of WeightedAmong:
3 3 3 3
4 0 1 2 3 -1 wamong hard 1000
2 1 2
1 3
For other examples :
- hard violation measure : wamong_hard.wcsp
- lin violation measure : wamong_lin.wcsp
- quad violation measure : wamong_quad.wcsp
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:
- Constructing a WeightedAmong
- WeightedAmong(unsigned int _arity, int* _scope);
- 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);
- add the cost function to the cost function network
- void addToCostFunctionNetwork(WCSP* wcsp);
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:
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)":
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
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:
- Constructing a WFA structure (TO BE CHANGED)
- WFA(int _nbStates);
- Constructing a WeightedRegular
- WeightedRegular(unsigned int _arity, int* _scope);
- Using accessors to add the informations (semantics, cost, ...)
- void setWFA(WFA* _automaton);
- add the cost function to the cost function network
- void addToCostFunctionNetwork(WCSP* wcsp);
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:
- if <> is == : gap = abs(K - Sum)
- if <> is <= : gap = max(0,Sum - K);
- if <> is < : gap = max(0,Sum - K - 1);
- if <> is != : gap = 1 if Sum != K and gap = 0 otherwise
- if <> is > : gap = max(0,K - Sum + 1);
- if <> is >= : gap = max(0,K - Sum);
- hard : if gap is greater than zero the cost baseCost is returned
- lin : the cost gap x baseCost is returned
- quad : the cost gap^2 x baseCost is returned
WCSP Format And Example
The following figure presents the WCSP format of WeightedSum:
<> K
The following figure presents an example of WeightedAmong:
3 3 3 3
4 0 1 2 3 -1 wsum hard 1000
== 4
For other examples :
- hard violation measure : wsum_hard.wcsp
- lin violation measure : wsum_lin.wcsp
- quad violation measure : wsum_quad.wcsp
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:
- Constructing a WeightedSum
- WeightedSum(unsigned int _arity, int* _scope);
- Using accessors to add the informations (semantics, cost, ...)
- void setSemantics(string _semantics);
- void setBaseCost(Cost _baseCost);
- void setComparator(string _comparator);
- void setRightRes(int _rightRes);
- add the cost function to the cost function network
- void addToCostFunctionNetwork(WCSP* wcsp);
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 :
- hard : if gap is greater than zero the cost baseCost is returned
- lin : the cost gap x baseCost is returned
- quad : the cost gap^2 x baseCost is returned
WCSP Format And Example
The following figure presents the WCSP format of WeightedOverlap:
<> 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:
3 3 3 3
4 0 1 2 3 -1 woverlap hard 1000
< 1
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:
- Constructing a WeightedOverlap
- WeightedOverlap(unsigned int _arity, int* _scope);
- Using accessors to add the informations (semantics, cost, ...)
- void setSemantics(string _semantics);
- void setBaseCost(Cost _baseCost);
- void setComparator(string _comparator);
- void setRightRes(int _rightRes);
- add the cost function to the cost function network
- void addToCostFunctionNetwork(WCSP* wcsp);
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).
./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
- The Global Constraint Catalog : http://www.emn.fr/z-info/sdemasse/gccat/
- The Toulbar's forge : http://mulcyber.toulouse.inra.fr/projects/toolbar/