Блог

Я использую решатель ограничений or-tools для поиска рабочих положений предметов в комнате. Я использую решатель CP вместо решателя рюкзака, потому что мне нужно добавить дополнительные ограничения.

Я представляю каждый элемент как интервал x и интервал y и добавляю ограничение, подобное этому:

model.AddNoOverlap2D(x_intervals, y_intervals)

Это помогает размещать объекты таким образом, чтобы они не перекрывались, но мне нужно добавить еще одно ограничение, чтобы обеспечить некоторое расстояние между объектами. Это должно быть базовое расстояние 2D между объектами, но для этой формулы требуются функции sqrt и pow, которые, по-видимому, не могут использоваться элементами IntVar.

Я рассматривал возможность использования другого «объекта-разделителя», который центрируется на каждом основном объекте, и добавления другого NoOverlap2D ограничения, но это привело бы к блокировке целого квадрата пространства, когда формула расстояния будет более точным расстоянием, которое не тратит столько места в комнате.

Редактировать — Приведенный ниже код теперь работает для установки ограничения расстояния на элементы.

После предложения Лорана я попытался создать множество промежуточных переменных для обработки этого, но застрял на умножении или делении переменных, определяющих интервалы расположения фигур:

 # Now lets make all possible combinations and make a distance between them
combos = list(combinations(range(len(rects_data)), 2))

print(combos) 

currentDistanceId = 0

distanceVariables = []

for listSet in combos:
    leftItem = all_vars[listSet[0]]
    rightItem = all_vars[listSet[1]]

    if leftItem.holderType == HolderType.Person and rightItem.holderType == HolderType.Person:
        print(f"Adding distances between {listSet[0]} and {listSet[1]} because both are people")
        
        currentDistanceId = currentDistanceId   1

        # Add an intermediate variable to store the sum of x for the center of left object
        leftCenterXSum = model.NewIntVar(0, horizon.x*2, f"leftCenterXSum{currentDistanceId}")
        # Add constraint to it
        model.Add(leftCenterXSum == leftItem.x2   leftItem.x1)
        # Add an intermediate variable to store the center of x of the left object
        leftCenterX = model.NewIntVar(0, horizon.x, f"leftCenterX{currentDistanceId}")
        # Add a constraint to divide it by 2 to make it te center
        model.AddDivisionEquality(leftCenterX, leftCenterXSum, 2)

        ## Repeat for x and y for left and right objects
        leftCenterYSum = model.NewIntVar(0, horizon.y*2, f"leftCenterYSum{currentDistanceId}")
        model.Add(leftCenterYSum == leftItem.y2   leftItem.y1)
        leftCenterY = model.NewIntVar(0, horizon.y, f"leftCenterY{currentDistanceId}")
        model.AddDivisionEquality(leftCenterY, leftCenterYSum, 2)

        rightCenterXSum = model.NewIntVar(0, horizon.x*2, f"rightCenterXSum{currentDistanceId}")
        model.Add(rightCenterXSum == rightItem.x2   rightItem.x1)
        rightCenterX = model.NewIntVar(0, horizon.x, f"rightCenterX{currentDistanceId}")
        model.AddDivisionEquality(rightCenterX, rightCenterXSum, 2)

        rightCenterYSum = model.NewIntVar(0, horizon.y*2, f"rightCenterYSum{currentDistanceId}")
        model.Add(rightCenterYSum == rightItem.y2   rightItem.y1)
        rightCenterY = model.NewIntVar(0, horizon.y, f"rightCenterY{currentDistanceId}")
        model.AddDivisionEquality(rightCenterY, rightCenterYSum, 2)

        # Create variable for difference of x
        xDiff = model.NewIntVar(-horizon.x, horizon.x, f"xDiff{currentDistanceId}")

        # Create constraint for difference of x
        model.Add(xDiff == rightCenterX - leftCenterX)

        # Create variable for difference of y
        yDiff = model.NewIntVar(-horizon.y, horizon.y, f"yDiff{currentDistanceId}")

        # Create constraint for difference for y
        model.Add(yDiff == rightCenterY - leftCenterY)

        # Create variables for x and y squared
        xDiffSquared = model.NewIntVar(0, horizon.x**2, f"xDiffSquared{currentDistanceId}")
        yDiffSquared = model.NewIntVar(0, horizon.y**2, f"yDiffSquared{currentDistanceId}")

        # Add constraint to multiply them
        model.AddMultiplicationEquality(xDiffSquared, [xDiff, xDiff])
        model.AddMultiplicationEquality(yDiffSquared, [yDiff, yDiff])

        totalDistance = model.NewIntVar(0, horizon.x**2   horizon.y**2, f"totalDistance{currentDistanceId}")

        model.Add(totalDistance == xDiffSquared   yDiffSquared)

        distanceVariables.append(totalDistance)

        model.Add( totalDistance >= distanceSquared )
    else:
        print(f"Skipping distances between {listSet[0]} and {listSet[1]} because one is furniture")
 

Вместо того , чтобы

 Sqrt((x1-x2)^2   (y1-y2)^2) >= d
 

Почему ты не пишешь

 (x1-x2)^2   (y1-y2)^2 >= d^2
 

Который поддерживается. Вам нужно будет написать (в псевдокоде)

 IntVar t_x
Add(t_x == x1 - x2)
IntVar t_sx
AddMultiplicationEquality(t_sx, [t_x, t_x])

IntVar t_y
Add(t_y == y1 - y2)
IntVar t_sy
AddMultiplicationEquality(t_sy, [t_y, t_y])

Add(t_sx   t_sy >= d * d)