英文:
Using AMPL find the largest rectangle in a circle
问题
这是一个相当简单的问题，给定直径为60单位的圆，找到适合其中的最大矩形。通过一些相当简单的数学知识，我们知道它的面积将是1800单位。
我创建了这个AMPL模型：
param diameter := 60;
param radius := diameter / 2;
var tlX; # 矩形的左上角 x 坐标
var tlY; # 矩形的左上角 y 坐标
subject to tlInside: sqrt(tlX*tlX + tlY*tlY) < radius; # 确保它在圆内
var brX; # 矩形的右下角 x 坐标
var brY; # 矩形的右下角 y 坐标
subject to brInside: sqrt(brX*brX + brY*brY) <= radius; # 确保它在圆内
var xDiff = brX - tlX;
var yDiff = brY - tlY;
maximize Area: xDiff * yDiff;
首先：
option solver gurobi; 可以解决它，但生成面积为0。 哎，怎么回事？
其次：
option solver HiGHS; 可以解决它，但生成面积为12.3873。 更接近了，但仍然不明显接近最优解。
第三：
option solver cbc; 可以解决它，但生成面积为1820.51。 这接近最优解（1800），但它生成了违反约束的变量！
我尝试的所有其他求解器甚至都无法找到解决方案。
那么到底发生了什么呢？看起来这是一个相当简单的问题？
英文:
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?
答案1
得分: 1
你必须意识到，在建模问题时，你正在创建一个凸集上的非凸目标函数。这是相当复杂的优化问题，任何局部最优解都可能被返回为全局最优解。我猜这就是Gurobi和HiGHS出现的情况。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论