Python 2 + PySCIPOpt, 267 bytes
from pyscipopt import*
R=input()
m=Model()
V,C=m.addVar,m.addCons
a,b,c=V(),V(),V()
m.setObjective(c)
C(a*b<=c)
P=[]
for r in R:
x,y=V(),V();C(r<=x);C(x<=a-r);C(r<=y);C(y<=b-r)
for u,v,s in P:C((x-u)**2+(y-v)**2>=(r+s)**2)
P+=(x,y,r),
m.optimize()
m.printBestSol()
How it works
We write the problem as follows: minimize c over variables a, b, c, x1, y1, …, xn, yn, where
- ab ≤ c;
- ri ≤ xi ≤ a − ri and ri ≤ yi ≤ b − yi, for 1 ≤ i ≤ n;
- (xi − xj)2 + (yi − yj)2 ≥ (ri + rj)2, for 1 ≤ j < i ≤ n.
Obviously, we’re using an external optimization library on these constraints, but you can’t just feed them to any old optimizer—even Mathematica’s NMinimize gets stuck at local minima for these tiny test cases. If you stare closely at the constraints, you’ll see that they constitute a quadratically-constrained quadratic program, and finding the global optimum for a non-convex QCQP is NP-hard. So we need some incredibly high-powered magic. I chose the industrial-strength solver SCIP, which is the only global QCQP solver I could find with so much as a free license for academic use. Happily, it has some very nice Python bindings.
Input and output
Pass the radius list on stdin, like [5,3,1.5]. The output shows objective value: rectangle area, x1, x2 rectangle dimensions, x3 rectangle area again, x4, x5 first circle center coordinates, x6, x7 second circle center coordinates, etc.
Test cases
[5,3,1.5] ↦ 157.459666673757
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.04
Solving Nodes : 187
Primal Bound : +1.57459666673757e+02 (9 solutions)
Dual Bound : +1.57459666673757e+02
Gap : 0.00 %
objective value: 157.459666673757
x1 10 (obj:0)
x2 15.7459666673757 (obj:0)
x3 157.459666673757 (obj:1)
x4 5 (obj:0)
x5 5 (obj:0)
x6 7 (obj:0)
x7 12.7459666673757 (obj:0)
x8 1.5 (obj:0)
x9 10.4972522849871 (obj:0)
[9,4,8,2] ↦ 709.061485909243
This is better than the OP’s solution. The exact dimensions are 18 by 29 + 6√3.
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 1.07
Solving Nodes : 4650
Primal Bound : +7.09061485909243e+02 (6 solutions)
Dual Bound : +7.09061485909243e+02
Gap : 0.00 %
objective value: 709.061485909243
x1 18 (obj:0)
x2 39.3923047727357 (obj:0)
x3 709.061485909243 (obj:1)
x4 9 (obj:0)
x5 30.3923047727357 (obj:0)
x6 14 (obj:0)
x7 18.3923048064677 (obj:0)
x8 8 (obj:0)
x9 8 (obj:0)
x10 2 (obj:0)
x11 19.6154311552252 (obj:0)
[18,3,1] ↦ 1295.999999999
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes : 13
Primal Bound : +1.29599999999900e+03 (4 solutions)
Dual Bound : +1.29599999999900e+03
Gap : 0.00 %
objective value: 1295.999999999
x1 35.9999999999722 (obj:0)
x2 36 (obj:0)
x3 1295.999999999 (obj:1)
x4 17.9999999999722 (obj:0)
x5 18 (obj:0)
x6 32.8552571627738 (obj:0)
x7 3 (obj:0)
x8 1 (obj:0)
x9 1 (obj:0)
Bonus cases
[1,2,3,4,5] ↦ 230.244214912998
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 401.31
Solving Nodes : 1400341
Primal Bound : +2.30244214912998e+02 (16 solutions)
Dual Bound : +2.30244214912998e+02
Gap : 0.00 %
objective value: 230.244214912998
x1 13.9282031800476 (obj:0)
x2 16.530790960676 (obj:0)
x3 230.244214912998 (obj:1)
x4 1 (obj:0)
x5 9.60188492354373 (obj:0)
x6 11.757778088743 (obj:0)
x7 3.17450418828415 (obj:0)
x8 3 (obj:0)
x9 13.530790960676 (obj:0)
x10 9.92820318004764 (obj:0)
x11 12.530790960676 (obj:0)
x12 5 (obj:0)
x13 5 (obj:0)
[3,4,5,6,7] ↦ 553.918025310597
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 90.28
Solving Nodes : 248281
Primal Bound : +5.53918025310597e+02 (18 solutions)
Dual Bound : +5.53918025310597e+02
Gap : 0.00 %
objective value: 553.918025310597
x1 21.9544511351279 (obj:0)
x2 25.2303290086403 (obj:0)
x3 553.918025310597 (obj:1)
x4 3 (obj:0)
x5 14.4852813557912 (obj:0)
x6 4.87198593295855 (obj:0)
x7 21.2303290086403 (obj:0)
x8 16.9544511351279 (obj:0)
x9 5 (obj:0)
x10 6 (obj:0)
x11 6 (obj:0)
x12 14.9544511351279 (obj:0)
x13 16.8321595389753 (obj:0)
[3,4,5,6,7,8] ↦ 777.87455544487
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 218.29
Solving Nodes : 551316
Primal Bound : +7.77874555444870e+02 (29 solutions)
Dual Bound : +7.77874555444870e+02
Gap : 0.00 %
objective value: 777.87455544487
x1 29.9626413867546 (obj:0)
x2 25.9614813640722 (obj:0)
x3 777.87455544487 (obj:1)
x4 13.7325948669477 (obj:0)
x5 15.3563780595534 (obj:0)
x6 16.0504838821134 (obj:0)
x7 21.9614813640722 (obj:0)
x8 24.9626413867546 (obj:0)
x9 20.7071098175984 (obj:0)
x10 6 (obj:0)
x11 19.9614813640722 (obj:0)
x12 7 (obj:0)
x13 7 (obj:0)
x14 21.9626413867546 (obj:0)
x15 8.05799919177801 (obj:0)
Related – James – 2016-08-30T01:44:47.497
1i don't see an objective winning criterion – Maltysen – 2016-08-30T01:50:36.540
that's one of our most central rules – Maltysen – 2016-08-30T01:52:36.260
2@Tim Most are code golf, with the goal of coding it in the fewest bytes. I think this would make a good code golf challenge, as it has an exact spec. – xnor – 2016-08-30T01:56:08.573
I recommend getting rid of the "rounded not truncated" condition because it's peripheral to the task, and some languages can just do it while others need extra coding to make it happen. I'm not sure if you intend it to be OK to output more than 3 decimal places, but I'd suggest allowing that too. – xnor – 2016-08-30T01:58:46.643
@xnor I've gone for code golf, although I'm a little worried it's too tricky to get exact answers. And yes, updated the 3dp thing. Do you think "Into your program, try the three test cases. Your score is the absolute difference between the sum of the three test cases your code outputs, and the correct sum - 2186.891. This means you are aiming for a score of 0." would be suitable / better? – Tim – 2016-08-30T01:59:49.333
@Tim It's on the harder side for a golf challenge, but I think that's fine. I expect many answers to try to brute force all packings to get the optimum and be really inefficient in run-time. Some larger test cases would be nice if you can generate them, in particular the upper limit of 6. – xnor – 2016-08-30T02:03:39.220
@xnor I would love to, but I'm making these by hand. I'll attempt a 6 one, but each circle added makes my wolfram alpha time increase dramatically. – Tim – 2016-08-30T04:39:36.420
@xnor More test cases! :-)
– Anders Kaseorg – 2017-07-27T10:24:30.747