Transcript 1D Bin Packing (or “CP? Who cares?”)

1D Bin Packing
(or “CP? Who cares?”)
A case study
[SR1] BIN PACKING
INSTANCE: Finite set U of items, a size s(u) in Z+ for each u in U, a
positive integer bin capacity B, and a positive integer K.
QUESTION: Is there a partition of U into disjoint sets U1, U2, …, Uk
such that the sum of the sizes of the items in each Ui is B or less?
Garey & Johnson
“Computers and Intractability: A guide to the theory of NP-Completeness”
An example
data = 42 63 67 57 93 90 38 36 45 42
n
= 10
// 10 numbers
m =5
// 5 bins
c
= 150
// bin capacity of 150
Can we pack the above 10 numbers into 5 bins such that the
sum of the numbers in each bin is less than or equal to 150?
Note: the above 10 numbers sum to a total of 579
579/150 = 3.86
1st stab
scalar(c, v)  c0 .v0  c1.v1    cn 1.vn 1
ci  Z
vi  {0,1}
Typical constraint for one bin
1. Read in the numbers into array called data
2. Associate an array of constrained integer variables v with a bin
3. vi is 1 if and only if the ith number is in that bin
More specifically
data
inBin
inBin
inBin
inBin
inBin
42
0
1
2
3
4
63 67 57 93 90 38 36 45 42
0 / 1 ...
0 /1
0 /1
...
...
...
...
...
...
0 /1
0 /1
...
0 /1
0 /1
inBin i , j  1  data j  bini
n
 data .inBin
j 1
j
i, j
 capacity
eq(load[i] , scalar(dat a, inBin[i]))
load[i]  makeIntVar (" l_"  i,0, c)
The sum of the numbers in a bin is less than or equal to its capacity
42
data
inBin
inBin
inBin
inBin
inBin
0
1
2
3
4
63 67 57 93 90 38 36 45 42
0 / 1 ...
0 /1
0 /1
...
...
...
...
...
0 /1
0 /1
load[i] is the sum of the numbers in the ith bin
where load[i] is a constrained integer variable with domain [0 .. C]
...
...
0 /1
0 /1
Note 1
We have n.m 0/1 constrained integer variables
Question: How big is the potential state space?
Only in one place at any one time!
42
data
inBin
inBin
inBin
inBin
inBin
0
1
2
3
4
63 67 57 93 90 38 36 45 42
0 / 1 ...
0 /1
0 /1
...
...
...
...
0 /1
0 /1
A number data[i] can only be in one bin at any one time!
Therefore, the number of 1’s in any column must be exactly 1
...
...
...
0 /1
0 /1
Is a bin used?
42
data
inBin
inBin
inBin
inBin
inBin
0
1
2
3
4
63 67 57 93 90 38 36 45 42
0 / 1 ...
0 /1
0 /1
...
...
0 /1
0 /1
If there are numbers in a bin then that bin is used.
binUsed[i] = 1 iff and only if load[i] > 0
Where binUsed is 0/1 constrained integer variable
...
...
...
...
...
0 /1
0 /1
How many bins are used?
42
data
inBin
inBin
inBin
inBin
inBin
0
1
2
3
4
63 67 57 93 90 38 36 45 42
0 / 1 ...
0 /1
0 /1
...
...
...
...
0 /1
0 /1
Sum up the number of bins used and ensure that this
is less than or equal to the number of bins that we have
totBinsUsed is a constraint integer variable with domain [0..m]
...
...
...
0 /1
0 /1
Program has the following command line inputs
fname
The name of a file containing 100 or more numbers
c
The (uniform) capacity of each bin
n
The number of numbers to read from file fname
m
The number of bins
Program finds first solution and displays
number of nodes, and the solution
Remember … we will optimise via a sequence of decision problems
Keep reducing the number of bins until no solution
It does nothing!
What is it doing?
What is search doing?
Decisions, decisions 
What are the decision variables?!
It is so slow!
Why is it so slow?
What is search doing?
Value Ordering!
It’s still slow!
Is there a heuristic?
1st fit decreasing
93 90 69 67 57 45 42 42 38 36
sorted
Bin Packing
First fit decreasing algorithm
A
B
C
D
E
F
With the first fit decreasing algorithm we sort the blocks into
descending order first.
5
4
1
2
6
3
2
3
3
Bin Packing
First fit decreasing algorithm
A
B
C
D
E
F
Now we use the first fit algorithm
6
5
4
3
3
3
2
2
1
Bin Packing
First fit decreasing algorithm
6
A
B
C
D
E
F
Now we use the first fit algorithm
5
4
3
3
3
2
2
1
Bin Packing
5
First fit decreasing algorithm
6
5
A
B
C
D
E
F
Now we use the first fit algorithm
4
3
3
3
2
2
1
Bin Packing
4
First
fit4 decreasing algorithm
6
A
5
B
4
C
D
E
F
Now we use the first fit algorithm
3
3
3
2
2
1
Bin Packing
First
fit decreasing algorithm
3
3
6
A
3
5
B
4
C
3
D
E
F
Now we use the first fit algorithm
3
3
2
2
1
Bin Packing
First
fit decreasing algorithm
3
3
6
A
3
5
B
3
4
C
3
D
E
F
Now we use the first fit algorithm
3
2
2
1
Bin Packing
First
fit decreasing
algorithm
3
3
3
6
A
3
5
B
3
4
C
3
D
3
E
F
Now we use the first fit algorithm
2
2
1
Bin Packing
First
fit
decreasing
algorithm
2
2
6
A
2
5
B
3
4
C
3
D
3
E
F
Now we use the first fit algorithm
2
1
Bin Packing
First
fit
decreasing
algorithm
2
2
2
2
6
A
2
5
B
3
4
C
2
3
D
3
E
F
Now we use the first fit algorithm
1
Bin Packing
First fit decreasing algorithm
1
1
6
A
2
5
B
3
4
C
2
3
D
Nowhave
We
we use
packed
the first
themfitinto
algorithm
5 bins.
3
E
F
Slow proving optimality
Don’t have a test that sum of numbers over capacity
is less than or equal to the number of bins available!
Symmetries?
Are there any symmetries that are slowing down search?
Can we remove those symmetries?
What are the symmetries in this problem?
Symmetries?
Why not insist that load[i] >= load[i+1]?
How about “lex” ordering between rows of inBin?
Is there another model?
?
An alternative (and it’s consequences)?
Introduce an array of constrained integer variables
loc[j] with domain [0..m]
loc j  i  inBin i , j  1
Consequences:
1. Array loc is now decision variables
2. No longer need to insist that sums of columns of inBin equal 1
Question: what’s the size of the state space now?
So?
What have we learned?
1.
2.
3.
4.
5.
6.
7.
8.
Identify the decision variables
What is the size of the state space?
What is the size of the model?
What is value ordering doing to the search?
Can we use any heuristics?
Are there symmetries that we can break?
Are there any simple/redundant tests/constraints overlooked?
Is there an alternative model?
And let’s not forget the big question …
9. Why are we using constraint programming?
Answers?