- i-bounded variable elimination eliminates all variables with a degree less than or equal to i. It can be done with arbitrary i-bound in preprocessing only and iff all their cost functions are in extension.
- i-bounded variable elimination with i-bound less than or equal to two can be done during the search.
- functional variable elimination eliminates all variables which have a bijective or functional binary hard constraint (ie ensuring a one-to-one or several-to-one value mapping) and iff all their cost functions are in extension. It can be done without limit on their degree, in preprocessing only.
- Note
- Variable elimination order used in preprocessing is either lexicographic or given by an external file *.order (see toulbar2 options)
-
2-bounded variable elimination during search is optimal in the sense that any elimination order should result in the same final graph
- Warning
- It is not possible to display/save solutions when bounded variable elimination is applied in preprocessing
-
toulbar2 maintains a list of current cost functions for each variable. It uses the size of these lists as an approximation of variable degrees. During the search, if variable x has three cost functions xy, xz, xyz, its true degree is two but its approximate degree is three. In toulbar2 options, it is the approximate degree which is given by the user for variable elimination during the search (thus, a value at most three). But it is the true degree which is given by the user for variable elimination in preprocessing.