Transcript numPart

number partitioning
Like subset sum
Given a bag of numbers, can you partition this
into 2 bags such that the sum of the integers
in each bag is equal?
Recently featured in the Crystal Maze!
(Thanks Zoe!)
Try it!
4532187359
Try that!
Try that?
Try that?
Can you think of a 1st test to
carry out to determine if there is no partition?
Given a bag of numbers, can you partition this
into 2 bags such that the sum of the integers
in each bag is equal?
Garey & Johnson “Computers and Intractability”
[SP12] PARTITION
INSTANCE: Finite set A and a size s(a)  Z+ for each a  A
QUESTION: Is there a subset A’  A such that aA’ s(a)  aA-A’ s(a)
How complex?
Who cares?
Imagine you have 2 machines on the shop floor
You have n activities, of varying durations
Place the activities on the machines to minimise makespan
Why just 2-partition?
Why not m-way partitioning?
Is there an optimisation problem?
A number of constraint encodings
1st stab
variables
wi is weight of i th object/num ber
Li {0, wi }
Ri {0, wi }
Di {0,1}
constraints
Di  0  Li  wi  Ri  0
Questions:
- What are the “decision variables”
- Can we be more efficient
- generate more propagation
- Bound or enumerated variables
- Is there a better model?
- What if it is insoluble?
Di  1  Li  0  Ri  wi
n 1
n 1
L  R
i 0
i
i 0
i
Di  0  Li  wi  Ri  0
Di  1  Li  0  Ri  wi
n 1
n 1
L R
i 0
i
i 0
i
How can I make an IntegerVariable with a domain
that is a set of values, rather than a range?
If I had L[i]  {0,w[i]} and R[i]  {0,w[i]}
could I throw away D[i] and have R[i] ≠ L[i]?
Laura?
Look! No D!
Questions, questions, questions
Decision variables … does it matter?
Heuristics?
Bound versus enumerated variables … anyone?
Symmetries
Size of state space?
Symmetry
If we are using a static variable ordering heuristic and
If we are using the 0/1 decision variables D[i]
Does it make any difference if we have D[0] = 0 or D[0] = 1
That is, can we half the search space?
1st stab
Why use CP for numPart?
Can we think of any “side constraints”?
Actually, an important question: justify use of CP
A 2nd stab
We want to minimise the difference between the sum
of the numbers on the left and the sum of the numbers
on the right
Right!?
A 2nd stab
An optimisation problem
Minimise the difference between left and right
Minimize imbalance
How do we optimise in CP?
A sequence of decision problems
Branch and bound
Demo of Optimize
Why is Optimize so slow?
When can this propagate?
Can we limit the search effort?
3d stab
3d stab
Optimize is a wee
bit “clunky”
Can we do better?
Put ½ the numbers on one side
1st stab
variables
wi is weight of i th object/num ber
constraints
Di {0,1}
n 1
m
w
i
i 0
2
X  {0..m}
n 1
 w .D
i 0
i
i
X
maximise X
Maximize the sum of
Weights on the right
As close to tot/2
n 1
m
w
i
i 0
2
X  {0..m}
n 1
 w .D
i 0
i
i
X
maximise X
Demo of OptimizeV2
Why was version 2 faster?
Could we Optimize without the decision variable D?
I suppose so … could explore this
Replace scalar with sum
So?
1.
2.
3.
4.
Three stabs!
A fair bit to consider
Has this all been easy?
Is there a better way to do numPart?
… and now for something completely different!!!
Assume for sake of argument, we have 3 digit numbers
Will it be easier to partition a bag of 100 numbers or a bag of 10 numbers?
Will we always be able to partition a bag of numbers?
Decision Problem
Random Data
Random Data
Answer these questions
1.
2.
3.
As we increase n does the problem get easier?
As we increase n do more or less instances have partitions?
As we increase d do problems get easier or harder?
Experiment
Experiment
Experiment
Experiment
Experiment 1: d = 3, vary n from 9 to 26 in single steps, sample size 10
Experiment 2: d = 3, vary n from 100 to 500 in steps of 100, sample size 10
Experiment 3: d = 6, vary n from 15 to 26 in single steps, sample size 10
Experiment 4: d = 6, vary n from 100 to 500 in steps of 100, sample size 10
Experiment 5: d = 7, n = 100, sample size 10
Observe % solubility and search effort