Actually in posting http://permalink.gmane.org/gmane.comp.lang.r.general/183891 there is a little example in R. The graph looks like:
The MINLP/Baron solution for this data set is a little bit better in terms of total area:
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
It is better to multiply by b to get rid of the division, so actually I added:
0.5 ≤ a/b ≤ 2
0.5b ≤ a ≤ 2b
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.