06 circle packing

This is a static, read-only snapshot — sliders and other controls will not respond. Back to notebook list · Run it yourself

%23%20%2F%2F%2F%20script%0A%23%20%5Btool.marimo.opengraph%5D%0A%23%20title%20%3D%20%22Circle%20Packing%22%0A%23%20description%20%3D%20%22Uses%20Xpress%20Global%20(Nonlinear)%22%0A%23%20image%20%3D%20%22__marimo__%2Fthumbnail-circlepacking.svg%22%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Place%20%24N%24%20disjoint%20circles%20in%20the%20unit%20square%20to%20maximize%20the%20sum%20of%20their%20radii.%20Circle%20packing%20problems%20of%20this%20kind%20have%20recently%20gained%20renewed%20visibility%20as%20a%20benchmark%20for%20AI-driven%20algorithm%20design%2C%20for%20example%20in%20Google%20DeepMind's%20AlphaEvolve%20project%20-%20see%20this%20%5BFICO%20blog%20post%5D(https%3A%2F%2Fmarketplace.fico.com%2Fblogs%2Fbest-global-optimization-solver)%20for%20how%20FICO%20Xpress%20compares%20against%20AlphaEvolve%20on%20this%20very%20problem.%0A%0A%20%20%20%20%26copy%3B%20Copyright%202025-2026%20Fair%20Isaac%20Corporation.%20The%20use%20of%20this%20example%20is%20subject%20to%20%5Blegal%20and%20license%20requirements%5D(https%3A%2F%2Fgithub.com%2Ffico-xpress%2Fpython-notebooks%23legal-and-license-requirements).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20Install%20the%20necessary%20packages%0A%20%20%20%20%23%20'%25pip%20install%20-q%20xpress%20matplotlib'%20command%20supported%20automatically%20in%20marimo%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%20description%20and%20formulation%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20In%20this%20example%2C%20we%20aim%20at%20packing%20%24N%24%20circles%20inside%20the%20unit%20square%20to%20maximize%20the%20sum%20of%20their%20radii.%20The%20circles%20must%20not%20overlap%20with%20each%20other%20and%20must%20be%20fully%20contained%20inside%20the%20unit%20square.%20Let%20%24CIRCLES%24%20be%20the%20set%20%24%5C%7B1%2C...%2CN%5C%7D%24.%0A%0A%20%20%20%20The%20continuous%20decision%20variables%20%24x_i%24%20and%20%24y_i%24%20represent%20the%20vector%20of%20%24(x%2Cy)%24%20coordinates%20of%20the%20center%20point%20of%20each%20circle%20%24i%20%5Cin%20CIRCLES%24%2C%20and%20variables%20%24r_i%24%20the%20corresponding%20radius.%0A%0A%20%20%20%20The%20goal%20is%20to%20maximize%20the%20area%20inside%20the%20unit%20square%20occupied%20by%20circles%2C%20that%20is%2C%20the%20sum%20of%20the%20radii%20of%20all%20circles%3A%0A%0A%20%20%20%20%24%24%5Cmax%20%5Csum_%7Bi%20%5Cin%20CIRCLES%7D%20r_%7Bi%7D%24%24%0A%0A%20%20%20%20The%20circles%20must%20not%20overlap%2C%20that%20is%2C%20the%20Euclidean%20distance%20between%20the%20center%20of%20any%20two%20circles%20must%20not%20be%20shorter%20than%20the%20sum%20of%20their%20radii.%20This%20can%20be%20represented%20by%20the%20following%20set%20of%20quadratic%20constraints%3A%0A%0A%20%20%20%20%24%24%20(x_i%20-%20x_j)%5E2%20%2B%20(y_i%20-%20y_j)%5E2%20%20%5Cgeq%20(r_i%20%2B%20r_j)%5E2%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%20CIRCLES%2C%20%5Cforall%20j%20%5Cin%20i%2B1%2C...%2CN%24%24%0A%0A%20%20%20%20Moreover%2C%20we%20need%20each%20circle%20to%20be%20fully%20contained%20within%20the%20unit%20square.%20Therefore%2C%20both%20the%20%24x_i%24%20and%20%24y_i%24%20coordinates%20of%20each%20circle%20must%20not%20be%20lower%20than%20its%20radius%20(similarly%2C%20they%20must%20not%20be%20greater%20than%20(1%20-%20%24r_i%24)).%20This%20can%20be%20represented%20by%20the%20following%20linking%20constraints%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bllll%7D%0A%20%20%20%20%26%20%5Cqquad%20%20x_i%20%5Cgeq%20r_i%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%20CIRCLES%20%5C%5C%0A%20%20%20%20%26%20%5Cqquad%20%20x_i%20%5Cleq%201%20-%20r_i%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%20CIRCLES%20%5C%5C%0A%20%20%20%20%26%20%5Cqquad%20%20y_i%20%5Cgeq%20r_i%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%20CIRCLES%20%5C%5C%0A%20%20%20%20%26%20%5Cqquad%20%20y_i%20%5Cleq%201%20-%20r_i%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%20CIRCLES%20%5C%5C%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Additionally%2C%20the%20radius%20of%20each%20circle%20has%20a%20trivial%20upper%20bound%20equal%20to%200.5%2C%20since%20the%20diameter%20of%20any%20circle%20can%20never%20be%20greater%20than%201%3A%0A%0A%20%20%20%20%24%240%20%5Cleq%20r_i%20%5Cleq%200.5%2C%20%5Cqquad%20%5Cforall%20i%20%5Cin%201..N%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Model%20implementation%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20model%20described%20above%20is%20implemented%20below%20with%20the%20Xpress%20Python%20API.%20Note%20that%20the%20upper%20bound%20is%20defined%20on%20variable%20creation%20with%20%5Bp.addVariables%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addVariables.html)%2C%20which%20creates%20a%20*NumPy*%20array%20of%20%24N%24%20variables%20when%20an%20integer%20is%20passed%20as%20the%20first%20argument.%0A%0A%20%20%20%20Use%20the%20slider%20below%20to%20change%20the%20number%20of%20circles%20%24N%24%20and%20re-run%20the%20model.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20xpress%20as%20xp%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%0A%20%20%20%20return%20plt%2C%20xp%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_slider%20%3D%20mo.ui.slider(2%2C%2014%2C%20value%3D6%2C%20label%3D%22Number%20of%20circles%20N%22%2C%20show_value%3DTrue)%0A%20%20%20%20n_slider%0A%20%20%20%20return%20(n_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20n_slider%2C%20xp)%3A%0A%20%20%20%20N%20%3D%20n_slider.value%20%20%20%23%20Number%20of%20circles%20to%20place.%0A%20%20%20%20CIRCLES%20%3D%20range(N)%0A%0A%20%20%20%20%23%20Create%20a%20problem%20instance.%0A%20%20%20%20p%20%3D%20xp.problem()%0A%0A%20%20%20%20%23%20Decision%20variables.%0A%20%20%20%20x%20%3D%20p.addVariables(N%2C%20name%3D%22x%22)%20%20%20%20%20%20%20%20%20%23%20x-coordinate%20of%20center%20points.%0A%20%20%20%20y%20%3D%20p.addVariables(N%2C%20name%3D%22y%22)%20%20%20%20%20%20%20%20%20%23%20y-coordinate%20of%20center%20points.%0A%20%20%20%20r%20%3D%20p.addVariables(N%2C%20name%3D%22r%22%2C%20ub%3D0.5)%20%23%20Radii%20of%20circles%2C%20upper%20bound%20is%200.5%20to%20fit%20in%20unit%20square.%0A%0A%20%20%20%20%23%20Non-overlap%20constraints.%0A%20%20%20%20p.addConstraint((x%5Bi%5D%20-%20x%5Bj%5D)**2%20%2B%20(y%5Bi%5D%20-%20y%5Bj%5D)**2%20%3E%3D%20(r%5Bi%5D%20%2B%20r%5Bj%5D)**2%20for%20i%20in%20CIRCLES%20for%20j%20in%20range(i%20%2B%201%2C%20N))%0A%0A%20%20%20%20%23%20Ensure%20that%20each%20circle%20is%20contained%20in%20the%20unit%20square.%0A%20%20%20%20p.addConstraint(x%5Bi%5D%20%3E%3D%20r%5Bi%5D%20for%20i%20in%20CIRCLES)%0A%20%20%20%20p.addConstraint(x%5Bi%5D%20%3C%3D%201%20-%20r%5Bi%5D%20for%20i%20in%20CIRCLES)%0A%20%20%20%20p.addConstraint(y%5Bi%5D%20%3E%3D%20r%5Bi%5D%20for%20i%20in%20CIRCLES)%0A%20%20%20%20p.addConstraint(y%5Bi%5D%20%3C%3D%201%20-%20r%5Bi%5D%20for%20i%20in%20CIRCLES)%0A%0A%20%20%20%20%23%20Objective%20function.%0A%20%20%20%20p.setObjective(xp.Sum(r)%2C%20sense%3Dxp.ObjSense.MAXIMIZE)%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20CIRCLES%2C%20N%2C%20p%2C%20r%2C%20x%2C%20y%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Before%20triggering%20the%20optimization%2C%20a%20number%20of%20optimizer%20controls%20are%20set.%20For%20exact%20arithmetic%2C%20the%20feasibility%20tolerance%20is%20lowered%20to%20a%20very%20small%20value%20with%20%5BFEASTOL%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2FHTML%2FFEASTOL.html).%0A%0A%20%20%20%20Moreover%2C%20we%20set%20a%20time%20limit%20of%203%20seconds%20before%20defining%20the%20global%20solver%20(default)%20to%20solve%20the%20problem.%0A%0A%20%20%20%20The%20code%20below%20defines%20these%20control%20parameters%20and%20optimizes%20the%20problem%20before%20printing%20the%20solution%20and%20objective%20values.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(CIRCLES%2C%20N%2C%20mo%2C%20p%2C%20r%2C%20x%2C%20xp%2C%20y)%3A%0A%20%20%20%20%23%20Control%20parameters.%0A%20%20%20%20p.controls.feastol%20%3D%201e-9%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Set%20the%20feasibility%20tolerance%20to%20a%20very%20small%20value.%0A%20%20%20%20p.controls.timelimit%20%3D%203%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Set%20a%20time%20limit%20in%20seconds.%0A%20%20%20%20p.controls.nlpsolver%20%3D%20xp.constants.NLPSOLVER_GLOBAL%20%20%20%20%20%20%20%20%23%20Set%20the%20NLP%20solver%20to%20global.%0A%0A%20%20%20%20%23%20Solve%20the%20problem.%0A%20%20%20%20p.optimize()%0A%0A%20%20%20%20%23%20Print%20a%20solution%20summary.%0A%20%20%20%20xsol%20%3D%20p.getSolution(x)%0A%20%20%20%20ysol%20%3D%20p.getSolution(y)%0A%20%20%20%20rsol%20%3D%20p.getSolution(r)%0A%20%20%20%20with%20mo.capture_stdout()%20as%20_buffer%3A%0A%20%20%20%20%20%20%20%20print(f%22Sum%20of%20radii%20for%20N%20%3D%20%7BN%7D%20is%20%7Bp.attributes.objval%7D%22)%0A%20%20%20%20%20%20%20%20for%20i%20in%20CIRCLES%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(f%22%7Bi%7D%3A%20x%20%3D%20%7Bxsol%5Bi%5D%7D%2C%20y%20%3D%20%7Bysol%5Bi%5D%7D%2C%20r%20%3D%20%7Brsol%5Bi%5D%7D%22)%0A%20%20%20%20mo.show_code(mo.plain_text(_buffer.getvalue())%2C%20position%3D%22above%22)%0A%20%20%20%20return%20rsol%2C%20xsol%2C%20ysol%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Visualization%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20plot%20below%20shows%20the%20circles%20defined%20by%20the%20solution%20inside%20the%20unit%20square%2C%20with%20a%20blue%20line%20and%20label%20indicating%20the%20radius%20of%20each%20circle.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(plt%2C%20rsol%2C%20xsol%2C%20ysol)%3A%0A%20%20%20%20%23%20Create%20a%20plot%0A%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots()%0A%0A%20%20%20%20%23%20Plot%20each%20circle%0A%20%20%20%20for%20(_x%2C%20_y%2C%20_r)%20in%20zip(xsol%2C%20ysol%2C%20rsol)%3A%0A%20%20%20%20%20%20%20%20%23%20Draw%20the%20circle%20with%20red%20edge%0A%20%20%20%20%20%20%20%20circle%20%3D%20plt.Circle((_x%2C%20_y)%2C%20_r%2C%20edgecolor%3D'red'%2C%20facecolor%3D'none')%0A%20%20%20%20%20%20%20%20ax.add_patch(circle)%0A%0A%20%20%20%20%20%20%20%20%23%20Draw%20the%20radius%20line%20in%20blue%0A%20%20%20%20%20%20%20%20ax.plot(%5B_x%2C%20_x%20%2B%20_r%5D%2C%20%5B_y%2C%20_y%5D%2C%20color%3D'blue')%0A%0A%20%20%20%20%20%20%20%20%23%20Add%20the%20radius%20length%20as%20label%0A%20%20%20%20%20%20%20%20ax.text(_x%20%2B%20_r%20%2F%202%2C%20_y%2C%20f'R%3D%7B_r%3A.2f%7D'%2C%20color%3D'blue'%2C%20fontsize%3D8%2C%20ha%3D'center'%2C%20va%3D'bottom')%0A%0A%20%20%20%20%23%20Set%20the%20limits%20and%20aspect%20ratio%0A%20%20%20%20ax.set_xlim(0%2C%201)%0A%20%20%20%20ax.set_ylim(0%2C%201)%0A%20%20%20%20ax.set_aspect('equal'%2C%20'box')%0A%20%20%20%20ax.grid(True)%0A%20%20%20%20fig%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A