或者-工具Python - AddNoOverlap2D不工作-股票切割问题

Question

试图从一个大的矩形中切割给定的一组矩形。程序运行良好，但不遵守AddNoOverlap2D约束。

程序输出

0, 0 -> 2, 2
0, 0 -> 1, 3
0, 0 -> 4, 3

所有程序输出的矩形坐标都以(0,0)为第一点，因此是重叠的。我想要得到不重叠的矩形

我使用的是model.AddNoOverlap2D约束，我设定的目标是最小化大矩形的未使用面积。完整守则：

from __future__ import print_function
import collections
from ortools.sat.python import cp_model

def StockCutter():
    """Cutting Stock problem."""
    # Create the model
    model = cp_model.CpModel()

    # rect = [width, height]
    rects_data = [
        [2, 2],
        [1, 3],
        [4, 3]
    ]

    rect_ids = range(len(rects_data))

    # parent rect (to cut from)
    horizon = [6, 6]
    print("Horizon: ", horizon)

    # Named tuple to store information about created variables
    rect_type = collections.namedtuple('rect_type', 'x1 y1 x2 y2 x_interval y_interval')

    all_vars = {}

    # to save area of all small rects, to cut from parent rect
    total_area = 0 

    # x_intervals holds the widths of each rect
    x_intervals = collections.defaultdict(list)
    # y_intervals holds the lengths of each rect
    y_intervals = collections.defaultdict(list)

    for rect_id, rect in enumerate(rects_data):
        width = rect[0]
        height = rect[1]
        area = width * height
        total_area += area
        print(f"Rect: {width}x{height}, Area: {area}")

        suffix = '_%i_%i' % (width, height)

        # interval to represent width
        x1_var = model.NewIntVar(0, horizon[0], 'x1' + suffix)
        x2_var = model.NewIntVar(0, horizon[0], 'x2' + suffix)
        x_interval_var = model.NewIntervalVar(x1_var, width, x2_var, 'x_interval' + suffix)

        # interval to represent height
        y1_var = model.NewIntVar(0, horizon[1], 'y1' + suffix)
        y2_var = model.NewIntVar(0, horizon[1], 'y2' + suffix)
        y_interval_var = model.NewIntervalVar(y1_var, height, y2_var, 'y_interval' + suffix)

        all_vars[rect_id] = rect_type(
            x1=x1_var, 
            y1=y1_var, 
            x2=x2_var, 
            y2=y2_var, 
            x_interval=x_interval_var,
            y_interval=y_interval_var
        )

        x_intervals[rect_id].append(x_interval_var)
        y_intervals[rect_id].append(y_interval_var)


    # NOT WORKING???
    for rect_id in rect_ids:
        model.AddNoOverlap2D(x_intervals[rect_id], y_intervals[rect_id])

    # objective: Area of parent (horizon) is max that the sum of all the rectangles' areas can have
    obj_var = model.NewIntVar(0, horizon[0]*horizon[1], 'area')

    # minimize the area not used
    model.Minimize(obj_var - total_area)

    # Solve model
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:

        # print coords
        for rect_id, rect in enumerate(rects_data):
            x1=solver.Value(all_vars[rect_id].x1)
            y1=solver.Value(all_vars[rect_id].y1)
            x2=solver.Value(all_vars[rect_id].x2)
            y2=solver.Value(all_vars[rect_id].y2)
            print(f"{x1}, {y1} -> {x2}, {y2}")

StockCutter()

Answer 1

您应该只使用AddNoOverlap2D和y_intervals的列表调用一次：

# x_intervals holds the widths of each rect
x_intervals = []
# y_intervals holds the lengths of each rect
y_intervals = []

for rect_id, rect in enumerate(rects_data):
    ...
    x_intervals.append(x_interval_var)
    y_intervals.append(y_interval_var)

model.AddNoOverlap2D(x_intervals, y_intervals)