使用Google OR-Tools Sat求解矩形布局时X、Y恒为0的问题求助

你遇到的所有小矩形坐标全为0的问题，根源在于变量范围设置错误和IntervalVar构造逻辑错误，导致重叠约束未生效，求解器直接返回了最无意义的 trivial 解。以下是具体修复步骤和完整代码：

关键错误点 #

1. X/Y坐标范围限制错误：
   原代码中x1[i]的上限设为小矩形自身宽度，意味着小矩形的X坐标最大只能到自身宽度，根本无法在大矩形内移动，只能停在0位置。正确上限应为大矩形宽度 - 小矩形宽度，Y坐标同理。

2. IntervalVar构造逻辑错误：
   OrTools的NewIntervalVar(start, size, end)要求end = start + size必须成立。原代码中size用了未绑定的width[i]，但end硬编码为x1[i] + 小矩形宽度，导致IntervalVar约束自相矛盾，重叠检测完全失效。

3. 宽高变量未绑定：
   原代码中width[i]和height[i]是自由变量，未绑定到小矩形实际宽高，求解器可随意赋值，导致重叠约束失去意义。

4. 大矩形面积约束缺失：
   原代码的BigRectArea未关联大矩形实际面积，目标函数Minimize(BigRectArea - TotalPieceArea)等价于最小化无约束变量，完全起不到优化作用。

修复后的完整代码 #

using Google.OrTools.Sat;
using System;
using System.Collections.Generic;
using System.Windows.Forms;

class YourClass
{
    public void YourMethod(List<YourRectangleClass> smallRectangles, YourRectangleClass BigRect)
    {
        int numRectangles = smallRectangles.Count;
        CpModel model = new CpModel();
        IntVar[] x1 = new IntVar[numRectangles];
        IntVar[] y1 = new IntVar[numRectangles];
        int bigWidth = BigRect.UWidth();
        int bigHeight = BigRect.UHeight();
        uint TotalPieceArea = 0;

        for (int i = 0; i < numRectangles; i++)
        {
            int rectWidth = smallRectangles[i].UWidth();
            int rectHeight = smallRectangles[i].UHeight();
            TotalPieceArea += (uint)(rectWidth * rectHeight);

            // 修正X/Y坐标范围：确保小矩形完全在大矩形内
            x1[i] = model.NewIntVar(0, bigWidth - rectWidth, $"X_{i}");
            y1[i] = model.NewIntVar(0, bigHeight - rectHeight, $"Y_{i}");

            // 构造正确的IntervalVar：start=x1[i], size=rectWidth, end=x1[i]+rectWidth
            IntervalVar rectX = model.NewIntervalVar(x1[i], rectWidth, x1[i] + rectWidth, $"RectX_{i}");
            IntervalVar rectY = model.NewIntervalVar(y1[i], rectHeight, y1[i] + rectHeight, $"RectY_{i}");

            // 添加2D不重叠约束
            model.AddNoOverlap2D().AddRectangle(rectX, rectY);
        }

        // 优化目标：最小化所有矩形的包围盒面积，实现紧凑布局
        IntVar maxX = model.NewIntVar(0, bigWidth, "maxX");
        IntVar maxY = model.NewIntVar(0, bigHeight, "maxY");
        for (int i = 0; i < numRectangles; i++)
        {
            model.AddMaxEquality(maxX, new IntVar[] { x1[i] + smallRectangles[i].UWidth() });
            model.AddMaxEquality(maxY, new IntVar[] { y1[i] + smallRectangles[i].UHeight() });
        }
        model.Minimize(maxX * maxY);

        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            for (int j = 0; j < numRectangles; j++)
            {
                smallRectangles[j].X = Convert.ToDouble(solver.Value(x1[j]));
                smallRectangles[j].Y = Convert.ToDouble(solver.Value(y1[j]));
            }
        }
        else
        {
            MessageBox.Show("No feasible solution found.");
        }
    }
}

// 补充矩形类示例（供参考）
public class YourRectangleClass
{
    public double X { get; set; }
    public double Y { get; set; }
    public int UWidth() => (int)Width;
    public int UHeight() => (int)Height;
    public double Width { get; set; }
    public double Height { get; set; }
}

额外说明 #

• 如果需要支持矩形旋转（宽高互换），可添加布尔变量控制旋转状态，约束宽高取值并调整IntervalVar的size参数，按需扩展即可。
• 修复后的目标函数改为最小化包围盒面积，更贴合矩形布局的紧凑性需求；若只需验证能否放入大矩形，可直接求解可行性问题。
• 求解状态判断新增Feasible，覆盖存在可行解但无最优解的场景。

内容的提问来源于stack exchange，提问作者Murat Cam