如何区分二维切割材料问题的正确和错误解决方案？

Question

我有一个基于Python中的GitHub repo（使用OR工具的线性编程）解决二维切削库存问题的算法。

我的绘图功能代码可以在这里找到

基本上算法分为：

1- StockCutter 函数：该函数解决了使用 or-tools 的问题。

2-getSingleSolution：该函数返回每个项目的坐标。

3-drawRectsFromCoords：该函数可视化解决方案。

有时算法会给出正确的解决方案，如下所示： 第一个和第二个数字是点 1 的坐标，第三个和第四个数字是第二个点的坐标。

[[0, 0, 15, 15], [0, 15, 15, 30], [0, 30, 15, 45], [0, 45, 15, 60], [0, 60, 15, 75], [0, 75, 15, 90], [0, 90, 15, 105], [0, 105, 15, 120], [0, 120, 15, 135], [0, 135, 15, 150], [15, 0, 30, 15], [15, 15, 30, 30], [15, 30, 30, 45], [15, 45, 30, 60], [15, 60, 30, 75], [30, 0, 45, 15]]

图片：

有时它会给出错误的解决方案：

[[21, 7, 36, 22], [8, 22, 23, 37], [23, 37, 38, 52], [7, 51, 22, 66], [8, 67, 23, 82], [7, 83, 22, 98], [17, 98, 32, 113], [7, 113, 22, 128], [23, 135, 38, 150], [39, 64, 54, 79], [47, 135, 62, 150], [40, 91, 55, 106], [22, 52, 37, 67], [23, 113, 38, 128], [1, 98, 16, 113], [1, 0, 16, 15]]

图片：

有没有办法判断Python中的解决方案是否有效？

Answer 1

在您的代码中，您在此处设置目标：

for rect_id in range(len(child_rects)):
        model.Minimize(all_vars[rect_id].x1 + all_vars[rect_id].y1)
        model.Minimize(all_vars[rect_id].x2 + all_vars[rect_id].y2)
        model.Minimize(all_vars[rect_id].x1)
        model.Minimize(all_vars[rect_id].x2)
        model.Minimize(all_vars[rect_id].y1)
        model.Minimize(all_vars[rect_id].y2)

您的每一次

Minimize

通话都会重置目标。

这可以在这个简单的例子中看到：

from ortools.sat.python import cp_model
model = cp_model.CpModel()
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')
model.Maximize(2 * x + 3 * y)
model.Maximize(y) # this is wrong
model.Add(2 * x + y <= 8)
model.Add(x + 2 * y <= 10)
solver = cp_model.CpSolver()
status = solver.Solve(model)
print(f'x ={solver.Value(x)}')
print(f'y ={solver.Value(y)}')
print(f'Objective Value ={ solver.ObjectiveValue()}')

输出：

Optimal Solution:
x =0
y =5
Objective Value =5.0 # Notice how the first objective isn't computed

此外，您需要确保您永远不会想象非最佳解决方案：

assert status == cp_model.OPTIMAL, 'Problem not solved optimally'

output = {
        "statusName": solver.StatusName(status),
        "numSolutions": '1',
        "numUniqueSolutions": '1',
        "solutions": int_solutions # unique solutions
    }

Answer 2

结合 rectpack 和 bin 打包包来解决您的解决方案，它完全适合您的场景，参考 https://github.com/secnot/rectpack