Main

Thanks to Frank Kampas for providing source code and animations for this challenge problem. Frank holds a Ph.D. in physics from Stanford University and can be reached at frank@physicistatlarge.com.

----

!!!! Download Sample MATLAB Code

MATLAB source code writes an APM optimization file and sends it to the APMonitor server for solution. After the script executes, a figure appears that shows the best and worst configurations.

* [[Attach:CirclePacking_MATLAB.zip|MATLAB Example Source Code]]

[[Attach:CirclePacking_MATLAB.zip|Attach:CirclePacking_MATLAB.png]]

----

* [[http://apmonitor.com/online/view_pass.php?f=circlepack4.apm|Solve 4 Circle Packing Problem]]

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="550" height="700" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

!!!! Background

Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together (often inside a container), as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues. In a packing problem, you are given:

* 'containers' - in this case a circle that circuscribes all of the other circles

* 'goods' (usually a single type of shape), some or all of which must be packed into this container

Usually the packing must be without overlaps between goods and other goods or the container walls. The aim is to find the configuration with the maximal density. In some variants the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimized.

## Circle Packing Challenge Activity

## Main.CircleChallenge History

Hide minor edits - Show changes to output

Added lines 69-70:

Thanks to Frank Kampas for providing source code and animations for this challenge problem. Frank holds a Ph.D. in physics from Stanford University and can be reached at frank@physicistatlarge.com.

Changed line 68 from:

Attach:10_circle_packing_anim.gif

to:

-> Attach:10_circle_packing_anim.gif

Changed line 68 from:

Attach:10_circle_packing_~~anim1~~.gif

to:

Attach:10_circle_packing_anim.gif

Changed line 68 from:

Attach:10_circle_packing_~~anim~~.gif

to:

Attach:10_circle_packing_anim1.gif

Added lines 18-26:

----

!!!! Download Sample MATLAB Code

MATLAB source code writes an APM optimization file and sends it to the APMonitor server for solution. After the script executes, a figure appears that shows the best and worst configurations.

* [[Attach:CirclePacking_MATLAB.zip|MATLAB Example Source Code]]

[[Attach:CirclePacking_MATLAB.zip|Attach:CirclePacking_MATLAB.png]]

Changed lines 34-35 from:

* [[http://apmonitor.com/online/view_pass.php?f=circlepack4.apm|Solve 4 Circle Packing Problem]]

to:

* [[http://apmonitor.com/online/view_pass.php?f=circlepack4.apm|Solve 4 Circle Packing Problem Online]]

Changed lines 55-59 from:

* [[http://apmonitor.com/online/view_pass.php?f=circlepack10.apm|Solve 10 Circle Packing Problem]]

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles10.htm" width="500" height="1500" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles10.htm" width="500" height="1500" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

to:

* [[http://apmonitor.com/online/view_pass.php?f=circlepack10.apm|Solve 10 Circle Packing Problem Online]]

Changed lines 46-47 from:

* [[Attach:CirclePacking_v2.zip|Python Example Source Code for ~~10 Circles~~]]

[[Attach:CirclePacking_v2.zip|Attach:~~CirclePacking10~~.png]]

[[Attach:CirclePacking_v2.zip|Attach:

to:

* [[Attach:CirclePacking_v2.zip|Python Example Source Code for Multi-Start]]

[[Attach:CirclePacking_v2.zip|Attach:CirclePacking_multi.png]]

[[Attach:CirclePacking_v2.zip|Attach:CirclePacking_multi.png]]

Changed lines 21-22 from:

!!!! Download Sample Python Code

to:

!!!! Download Sample Python Code - Version 1

Added lines 38-58:

(:htmlend:)

----

!!!! Download Sample Python Code - Version 2

A second version solves multiple circle packing optimization problems with the same model using multi-dimensional arrays. Python source code re-writes the optimization file and sends it to the APM server for solution. After the script executes, a figure appears that shows the configuration that was produced.

* [[Attach:CirclePacking_v2.zip|Python Example Source Code for 10 Circles]]

[[Attach:CirclePacking_v2.zip|Attach:CirclePacking10.png]]

----

!!!! Example Solution for 10 Circles

Attach:10_circle_packing.png

* [[http://apmonitor.com/online/view_pass.php?f=circlepack10.apm|Solve 10 Circle Packing Problem]]

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles10.htm" width="500" height="1500" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

----

!!!! Download Sample Python Code - Version 2

A second version solves multiple circle packing optimization problems with the same model using multi-dimensional arrays. Python source code re-writes the optimization file and sends it to the APM server for solution. After the script executes, a figure appears that shows the configuration that was produced.

* [[Attach:CirclePacking_v2.zip|Python Example Source Code for 10 Circles]]

[[Attach:CirclePacking_v2.zip|Attach:CirclePacking10.png]]

----

!!!! Example Solution for 10 Circles

Attach:10_circle_packing.png

* [[http://apmonitor.com/online/view_pass.php?f=circlepack10.apm|Solve 10 Circle Packing Problem]]

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles10.htm" width="500" height="1500" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

Added lines 9-10:

----

Added lines 19-20:

----

Added lines 28-29:

----

Added lines 39-40:

----

Changed line 12 from:

* 'containers' - in this case a circle that ~~circuscribes~~ all of the other circles

to:

* 'containers' - in this case a circle that circumscribes all of the other circles

Added lines 19-20:

Python source code re-writes the optimization file and sends it to the APM server for solution. After the script executes, a figure appears that shows the configuration that was produced.

Added lines 27-28:

* [[http://apmonitor.com/online/view_pass.php?f=circlepack4.apm|Solve 4 Circle Packing Problem]]

Changed line 27 from:

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="~~450~~" height="600" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

to:

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="500" height="600" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

Changed line 27 from:

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="~~550~~" height="~~700~~" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

to:

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="450" height="600" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

Changed line 33 from:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="~~400~~" height="~~600~~" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

to:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="550" height="900" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

Changed line 33 from:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="~~500~~" height="~~800~~" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

to:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="400" height="600" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

Changed line 33 from:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="~~550~~" height="~~1000~~" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

to:

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="500" height="800" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

Added lines 25-28:

(:html:)

<iframe src="http://apmonitor.com/me575/uploads/Main/packcircles.htm" width="550" height="700" frameborder="1" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

Added lines 8-16:

!!!! Background

Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together (often inside a container), as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues. In a packing problem, you are given:

* 'containers' - in this case a circle that circuscribes all of the other circles

* 'goods' (usually a single type of shape), some or all of which must be packed into this container

Usually the packing must be without overlaps between goods and other goods or the container walls. The aim is to find the configuration with the maximal density. In some variants the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimized.

Added lines 14-16:

!!!! Example Solution for 4 Circles

Attach:4_circle_packing.png

Attach:4_circle_packing.png

Added lines 11-12:

* [[Attach:CirclePacking.zip|Python Example Source Code]]

[[Attach:CirclePacking.zip|Attach:CirclePacking.png]]

[[Attach:CirclePacking.zip|Attach:CirclePacking.png]]

Added lines 1-37:

(:title Circle Packing Challenge Activity:)

(:keywords project, nonlinear, optimization, engineering optimization, engineering design, interior point, active set, circle packing, packing optimization, python, matlab:)

(:description A challenge problem to determine the minimum circumscribing radius for n circles with radius i^(-0.5) for i=1..n.:)

!!!! Challenge Problem in Global Optimization

Determine the minimum circumscribing radius for n circles with radius i^(-0.5) for i=1..n.

!!!! Download Sample Python Code

!!!! Record Your Best Answer

(:html:)

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="550" height="1000" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)

(:keywords project, nonlinear, optimization, engineering optimization, engineering design, interior point, active set, circle packing, packing optimization, python, matlab:)

(:description A challenge problem to determine the minimum circumscribing radius for n circles with radius i^(-0.5) for i=1..n.:)

!!!! Challenge Problem in Global Optimization

Determine the minimum circumscribing radius for n circles with radius i^(-0.5) for i=1..n.

!!!! Download Sample Python Code

!!!! Record Your Best Answer

(:html:)

<iframe src="https://docs.google.com/a/apmonitor.com/spreadsheet/embeddedform?formkey=dGp4bExwUU1wOVhOT3M1T2otY1g3LXc6MQ" width="550" height="1000" frameborder="0" marginheight="0" marginwidth="0">Loading...</iframe>

(:htmlend:)

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)