Using AMPL find the largest rectangle in a circle

Question

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?

Answer 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.