optimization - Not a knapsack or bin algorithm -

i need find combination of rectangles maximize use of area of circle. difference between situation , classic problems have set of rectangles can use, , subset of rectangles must use.

by way of analogy: think of end of log , list of board sizes. can cut 2x4s, 2x6s , 2x8s , 2x10 log must cut @ least 2 2x4s , 1 2x8.

as understand it, particular variation mildly different other packing optimizations. in advance insight on how might adapt existing algorithms solve problem.

ncdiesel

this pretty hard problem, squares instead of rectangles.

here's idea. approach knapsack-integer-program, can give insights solution. (by definition won't give optimal solution.)

ip formulation heuristic

say have total of n rectangles, r1, r2, r3, ..., rn let area of each rectangle a1, a2, a3, ..., let area of large circle given *a* 

decision variable

xi = 1 if rectangle selected. 0 otherwise. 

objective

 minimize [a - sum_over_i (ai * xi)] 

subject to:

 sum_over_i (ai x xi) <= # area_limit constraint  xk = 1 each rectangle k has selected 

you can solve using solver.

now, reason heuristic solution totally ignores arrangement of rectangles inside circle. ends "cutting" rectangles smaller pieces fit inside circle. (that why area_limit constraint weak bound.)

relevant reference

this math se question addresses "classic" version of it. , you can @ link provided comments in there, several clever solutions involving squares of same size packed inside circle.