Monday, March 22, 2010

Looks difficult to me (2)

This is a follow up on http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult-to-me.html

I tried a simple minded MINLP formulation, and solved this with Baron:

image

This actually worked! Even for n=100 and n=200. Note that it is important to use a global solver as there are many inferior local solutions. As I solved with OPTCR=0 these are really proven global optimal solutions. I assumed the rectangle can not be rotated and must be aligned with the x and y axes. Here are some results.

image

Here are the corresponding plots of the solutions:

image

image

image

image

Of course faster special purpose algorithms exist for this problem.