variable elimination and bucket elimination

remove a variable from a problem

remove all but one ⇒ easy to solve

remove a variable

S = all solutions of the problem
solution = evaluation of all variables

some variable x may not be of interest
remove x from all solutions in S

that easy?
only after obtaining all solutions!

removing a variable from the problem

removing a variable from the solution is easy
(given the solutions)

remove the variable from the problem =
obtain the same solutions modifying the problem itself

how:

modify the problem

aim:

same solutions, but without x

variable elimination: how?

always possible
often: problem increases in size

easy (and wrong solution):
remove x from all constraints that contain it

why not?

just remove?…

removing a variable x looks easy:
just remove the variable!

what about the constraints the containts that contain x?

remove the constraint?
remove the variable from the constraint?

remove constraints?

C = ⟨⟨x,y⟩, {⟨2,3⟩, ⟨4,6⟩, ⟨1,5⟩}⟩
D = ⟨⟨y,z⟩, {⟨3,1⟩, ⟨2,6⟩}⟩

C contains x ⇒ remove it

only other constraint D

y=2, z=3 allowed as a solution
only solution of original problem: x=2, y=3, z=6

remove variables from constraints, then?

(this is a different problem)

C = ⟨⟨x,y⟩, {⟨2,3⟩, ⟨4,6⟩, ⟨1,5⟩}⟩
D = ⟨⟨x,z⟩, {⟨3,1⟩, ⟨2,6⟩, ⟨1,1⟩}⟩

try: remove x from the table
also the column of value!

cut tables

C = ⟨⟨y⟩, {⟨3⟩, ⟨6⟩, ⟨5⟩}⟩
D = ⟨⟨z⟩, {⟨1⟩, ⟨6⟩, ⟨1⟩}⟩

admits solution y=6, z=1
only solutions of the original problem:
{x=2, y=3, z=6} and {x=1, y=5, z=1}
(go back to the original problem and check!)

(formally, 1 and 1 are merged)

the problem with removed variables

cannot remove the constraints with x
they also constraint other variables

cannot remove x from the constraint
it links the values of the other variables

still: remove variables by expanding its effects

in the example:
original solutions: {x=2, y=3, z=6} and {x=1, y=5, z=1}
new solutions: {y=3, z=6} and {y=5, z=1}
none else!

effects of a removed variable

x limits the values of the other variables
formalize as a constraint

C(X\{x},R) on all other variables
R contains all tuples that can be extended to x to form a solution of the original problem

simplification

no need to involve all variables
only those in a constraint with x

example: constraint is only on y and z
not no w, k, …

N = ⟨ ⟨y,z⟩, { ⟨3,6⟩, ⟨5,1⟩ } ⟩

alternative view

combine all constraints on x in a single constraint
tuples: values allowed by all of them
in the example: constraint on x, y, z

remove x from that constraint

can be done if exactly one constraint contain x

constraint combination

combine C and D
variables x,y,z
values that satisfy both C and D at the same time

C = ⟨⟨x,y⟩, {⟨2,3⟩, ⟨4,6⟩, ⟨1,5⟩}⟩
D = ⟨⟨x,z⟩, {⟨3,1⟩, ⟨2,6⟩, ⟨1,1⟩}⟩

C+D = ⟨⟨x,y,z⟩, {⟨2,3,6⟩, ⟨1,5,1⟩}⟩

why:
⟨2,3⟩ satisfies C, ⟨2,6⟩ satisfies D ⇒ ⟨2,3,6⟩ satisfies C+D
⟨1,5⟩ satisfies C, ⟨1,1⟩ satisfies D ⇒ ⟨1,5,1⟩ satisfies C+D

now remove x!

bucket elimination

a way for removing one variable at time

only one variable left ⇒ problem is easy to solve

bucket elimination: how

variables are sorted: x₁ < … < x_n

constraints are partitioned in n classes:
class i: all constraints where x_i is the maximal variable

class n

all constraints that contain x_n

class n-1

all constraints that contain x_n-1 and do not contain x_n

class n-2

all constraints that contain x_n-2 and do not contain x_n-1 and x_n

…

class 1:

constraints that only contain x₁

simplifies the elimination mechanism

removal of a single bucket

first bucket removed is n
all constraints that contain x_n

how: merge in a single constraint
remove x_n

resulting constraints goes in the appropriate bucket
if it contains x_n-1, goes in bucket n-1
if it contains x_n-2, goes in bucket n-2
…

lather, rinse, repeat

after removing variable x_n:
buckets 1, …, n-1 left

repeat on bucket n-1

when on bucket 1:
all constraints on variable x₁
common values: solution

why it works

bucket elimination = remove a variable

same solutions!
apart from the removed variable

why other algorithms?

why not?

why using other algorithms if bucket elimination works?

removing a variable may produce a large constraint
removing one of its variables may produce an even larger one, etc.

example:

merge and remove x: