Monday, March 22, 2010

Looks difficult to me (3)

Actually in posting http://permalink.gmane.org/gmane.comp.lang.r.general/183891 there is a little example in R. The graph looks like:

image

The MINLP/Baron solution for this data set is a little bit better in terms of total area:

image

I am surprised how difficult this is to predict just by looking at the picture. Note that implementing the suggested side constraints would be trivial. Initially I thought it may even improve the performance but this is not the case: the problem becomes a little bit harder. For the 100 point problem above I added the constraint

0.5 ≤ a/b ≤ 2

It is better to multiply by b to get rid of the division, so actually I added:

0.5b ≤ a ≤ 2b

This gives:

image

The rectangle is shifted a little bit to achieve a slightly larger area. Of course adding upper bounds of 0.5 to a and b will speed up things a lot.

(See also http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult-to-me-2.html)