As I pointed out to Sean in my comment, I don't know if an ILP tool can work here, but I might be wrong in that respect.
One simple question that can be asked is how close can you get, if overlap and shape considerations are ignored? That is, can we write 46*46 = 2116 as the sum of three numbers, 29*20, 21*5, 10*4? At the very least, this will tell us something.
Using my partitions tool as found on the file exchange, it tells me that you cannot write 2216 as such a sum.
partitions(46*46,[10*4,21*5,29*20])
ans =
Empty matrix: 0-by-3
However, if we back off a bit, we see there are 5 ways we can decompose 2115 into such a sum, and two of those decompositions used at least one rect of each size.
partitions(46*46-1,[10*4,21*5,29*20])
ans =
45 3 0
24 11 0
3 19 0
20 7 1
16 3 2
So we can have 2 of the large rects, 3 of the medium sized ones, and 16 of the small ones. Of course, this is purely an areal computation, with no issue of overlap and fitting them all within the boundaries. This is the best you can possibly do.
We can get the same solution from intlinprog of course, but only one of the possible solutions will drop out, not both of the solutions posed by partitions.
rectcounts = intlinprog(-[40 105 580],[1 2 3],[40 105 580],2116,[],[],[1 1 1])
LP: Optimal objective value is -2116.000000.
Cut Generation: Applied 1 strong CG cut,
and 1 Gomory cut.
Lower bound is -2115.000000.
Heuristics: Found 1 solution using rounding.
Upper bound is -2085.000000.
Relative gap is 1.44%.
Branch and Bound:
nodes total num int integer relative
explored time (s) solution fval gap (%)
7 0.02 2 -2.105000e+03 4.748338e-01
11 0.02 3 -2.110000e+03 2.368546e-01
30 0.03 4 -2.115000e+03 0.000000e+00
Optimal solution found.
Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0 (the default value). The intcon
variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).
rectcounts =
16
3
2
And since I don't know from the question if the rects may be rotated, I really can go no further at all. If you were to push me harder, I would suggest the use of a genetic algorithm to place the rects, constraining the rects to fall at integer locations, minimizing the overlap. The location of any given rect would be determined by the location of its upper left hand corner perhaps, and would be constrained to lie at integer locations.
By the way, simple logic and some graph paper will let you do a pretty decent job here to get a reasonably dense packing. For example, IF we assume there are two of the large rects, they must lie in the same orientation, else there will be overlap. With only one large rect, assume if fits into one of the corners of the square, then proceed from there.
