0

So this is a pretty simple problem, given a circle of diameter 60 units, find the largest rectangle that fits in it. Using some pretty simple maths we know it'll have an area of 1800 units.

So I created this AMPL model


param diameter := 60;


param radius := diameter / 2;


var tlX; # top left x of the rectangle
var tlY; # top left y of the rectangle 
subject to tlInside: sqrt(tlX*tlX + tlY*tlY) < radius;  # make sure its inside the circle 


var brX; # bottom right x of the rect
var brY; # bottom right y of the rectangle
subject to brInside: sqrt(brX*brX + brY*brY) <= radius; # make sure its inside the circle 



var xDiff =  brX - tlX;
var yDiff = brY - tlY;

maximize Area: xDiff * yDiff;

First up:

option solver gurobi; solves it, but creates an area of 0. lol, wut?

Second up:

option solver HiGHS; solves it, but creates an area of 12.3873. Closer. But still not clearly near optimal

Third up:

option solver cbc; solves it, but create an area of 1820.51. This is close to the optimal (1800) but it generates the variables that violate the constraints!

All other solvers I tried couldn't even come up with a solution.

So what's going on. Seems like it's a pretty trivial problem?

Rojer Vairs
  • 77
  • 5
  • It might be worth it to actually constrain the top left x and y to be in the top left of the circle (or at least above and to the left of the other point), otherwise the problem has several optima. You can also simplify the constraints by squaring both sides of them. – Noah Feb 13 '23 at 07:24

1 Answers1

1

You have to realize that as you model the problem you are creating a non-convex objective function over a convex set of feasible points. That is far from trivial to optimize, and any locally optimal solution may be returned as optimal. I guess this is what happens with gurobi and HiGHS.

LaszloLadanyi
  • 973
  • 4
  • 12