基于CP-SAT的2D下料C#实现：Y值始终为0求助

问题描述 #

将已验证可行的Python 2D下料代码转换为C#后，运行结果中X1值正常，但所有矩形的Y值始终为0，查看日志无法定位问题。

问题代码 #

List<advRectangle> smallRectangles = new() { };

smallRectangles.Add(new advRectangle(500, 750, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 1000, 0, 0, "1"));
smallRectangles.Add(new advRectangle(2000, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 752, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 2000, 0, 0, "1"));
smallRectangles.Add(new advRectangle(500, 750, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1250, 250, 0, 0, "1"));
smallRectangles.Add(new advRectangle(250, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(500, 750, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 1000, 0, 0, "1"));
smallRectangles.Add(new advRectangle(2000, 500, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 750, 0, 0, "1"));
smallRectangles.Add(new advRectangle(1000, 2000, 0, 0, "1"));

advRectangle BigRect = new advRectangle(2000, 3000, 0, 0, "1");

// Create a CP model
CpModel model = new CpModel();

// Data
int H = Convert.ToInt32(BigRect.UHeight());  // Bin height
int W = Convert.ToInt32(BigRect.UWidth());  // Bin width

List<int> h = smallRectangles.Select(sr => Convert.ToInt32(sr.UHeight())).ToList();
List<int> w = smallRectangles.Select(sr => Convert.ToInt32(sr.UWidth())).ToList();

int n = h.Count; // Number of items
int m = 10;     // Max number of bins

// Variables
IntVar[] x1 = new IntVar[n];
IntVar[] x2 = new IntVar[n];
IntVar[] y1 = new IntVar[n];
IntVar[] y2 = new IntVar[n];

// Constraints
long[][] x1Intervals = new long[n][];
long[][] x2Intervals = new long[n][];

for (int i = 0; i < n; i++)
{
    List<long[]> tempx1 = new List<long[]>();
    for (int j = 0; j < m; j++)
    {
        tempx1.Add(new long[] { j * W, (j+1)*W - w[i] });                   
    }
    x1Intervals = tempx1.ToArray();
    x1[i] = model.NewIntVarFromDomain(Google.OrTools.Util.Domain.FromIntervals(x1Intervals), $"x1[{i}]");
}

for (int i = 0; i < n; i++)
{
    List<long[]> tempx2 = new List<long[]>();           
    for (int j = 0; j < m; j++)
    {
        tempx2.Add(new long[] { j * W + w[i], (j + 1) * W });
    }
    x2Intervals = tempx2.ToArray();
    x2[i] = model.NewIntVarFromDomain(Google.OrTools.Util.Domain.FromIntervals(x2Intervals), $"x2[{i}]");
}

for (int i = 0; i < n; i++)
{
    y1[i] = model.NewIntVar(0, H - h[i], $"y1[{i}]");
}

for (int i = 0; i < n; i++)
{                
    y2[i] = model.NewIntVar(h[i], H, $"y2[{i}]");
}

// Define literals for bin assignment
BoolVar[][] lit = new BoolVar[n][];
for (int i = 0; i < n; i++)
{
    lit[i] = new BoolVar[m];
    for (int j = 0; j < m; j++)
    {
        lit[i][j] = model.NewBoolVar($"lit[{i}][{j}]");
    }
}

// Now we assert that every rectangle belongs to exactly one bin.Also we must refine left and right boundaries of every rectangle:
var bv1 = new List<BoolVar>();
var lv1 = new List<long>();
var bv2 = new List<BoolVar>();
var lv2 = new List<long>();

var bvy1 = new List<BoolVar>();
var lvy1 = new List<long>();
var bvy2 = new List<BoolVar>();
var lvy2 = new List<long>();

for (int i = 0; i < n; i++)
{
    model.Add(Google.OrTools.Sat.LinearExpr.Sum(lit[i]) == 1);
}
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        bv1.Add(lit[i][j]);
        lv1.Add(j * W);
    }
    for (int j = 0; j < m; j++)
    {
        bv2.Add(lit[i][j]);
        lv2.Add((j + 1) * W);
    }
}
for (int i = 0; i < n; i++)
{
    model.Add(Google.OrTools.Sat.LinearExpr.WeightedSum(bv1, lv1) <= x1[i]);
    model.Add(Google.OrTools.Sat.LinearExpr.WeightedSum(bv2, lv2) >= x2[i]);
}

// Define interval variables
Google.OrTools.Sat.IntervalVar[] x_interval = new Google.OrTools.Sat.IntervalVar[n];
Google.OrTools.Sat.IntervalVar[] y_interval = new Google.OrTools.Sat.IntervalVar[n];

for (int i = 0; i < n; i++)
{
    x_interval[i] = model.NewIntervalVar(x1[i], w[i], x2[i], "");
    y_interval[i] = model.NewIntervalVar(y1[i], h[i], y2[i], "");
}

//fixed   
NoOverlap2dConstraint NoOverlap2Constraint = new 
NoOverlap2dConstraint(model.Model);
NoOverlap2Constraint.Proto = model.AddNoOverlap2D().Proto;

for (int i = 0; i < n; i++)
{  NoOverlap2Constraint.AddRectangle(x_interval[i], y_interval[i]);}

// Define the objective
IntVar obj = model.NewIntVar(0, m, "obj");
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {               
        model.Add(obj >= (j + 1)).OnlyEnforceIf(lit[i][j]);  
    }
}

model.Minimize(obj);

// Create a CP solver.
CpSolver solver = new CpSolver();
solver.StringParameters = "log_search_progress:true";
solver.SetLogCallback(LogCallback);
// Solve the problem
CpSolverStatus status = solver.Solve(model);

if (status == CpSolverStatus.Optimal)
{
    // Print the bin and position of each item
    for (int i = 0; i < n; i++)
    {
        smallRectangles[i].X = solver.Value(x1[i]);
        smallRectangles[i].Y = solver.Value(y1[i]);
        Console.WriteLine($"Item {i}: Bin {solver.Value(obj)}, X1: {solver.Value(x1[i])}, Y1: {solver.Value(y1[i])}");
    }
}
else
{
    MessageBox.Show("No optimal solution found.");
}

问题原因及修复方案 #

1. NoOverlap2D约束添加方式错误

代码中手动操作NoOverlap2dConstraint的Proto属性是错误的，导致二维不重叠约束并未真正生效。由于没有重叠限制，求解器会选择最容易满足目标的解——将所有矩形放在Y=0的位置，同时分配到不同的X轴区间（bin）。

修复代码：
替换原有的NoOverlap2D约束添加代码：

// 移除原错误的约束添加代码
// NoOverlap2dConstraint NoOverlap2Constraint = new NoOverlap2dConstraint(model.Model);
// NoOverlap2Constraint.Proto = model.AddNoOverlap2D().Proto;
// for (int i = 0; i < n; i++)
// {  NoOverlap2Constraint.AddRectangle(x_interval[i], y_interval[i]);}

// 使用正确的方式添加二维不重叠约束
var noOverlapConstraint = model.AddNoOverlap2D();
for (int i = 0; i < n; i++)
{
    noOverlapConstraint.AddRectangle(x_interval[i], y_interval[i]);
}

2. 可选：补充Y变量与bin的关联约束

原代码中X变量通过加权和约束与bin分配关联，但Y变量没有类似约束。虽然原Python逻辑中每个bin的Y范围都是0到H，此约束非必须，但如果需要确保每个bin内的Y坐标严格不超出bin范围，可添加以下代码：

// 在定义bv1、lv1等变量后添加
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < m; j++)
    {
        bvy1.Add(lit[i][j]);
        lvy1.Add(0); // 每个bin的Y起始都是0
        bvy2.Add(lit[i][j]);
        lvy2.Add(H); // 每个bin的Y结束都是H
    }
}

for (int i = 0; i < n; i++)
{
    model.Add(Google.OrTools.Sat.LinearExpr.WeightedSum(bvy1, lvy1) <= y1[i]);
    model.Add(Google.OrTools.Sat.LinearExpr.WeightedSum(bvy2, lvy2) >= y2[i]);
}

验证修复效果 #

修复后，求解器会因为二维不重叠约束的存在，必须在Y方向上合理排列矩形，Y值将不再全部为0，同时满足bin数量最小化的目标。

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