TypeError: unsupported operand type(s) for ** or pow(): 'MLinExpr' and 'int'

Question

I am trying to solve a complex bin packing problem using Gurobi.

I have a model for solving the problem but I'm facing an typeError.

My code is:

from gurobipy import GRB, Model
import numpy as np


"""
Create data
"""
items = np.arange(50)
radii = 0.2 * np.ones_like(items)
areas = np.pi * radii ** 2                                          # Areas of items in m2
min_dist = np.add.outer(radii, radii)

pallet_length = 1.2                                                 # x-dimension of pallet in m
pallet_width = 0.8                                                  # y-dimension of pallet in m
pallet_area = pallet_length * pallet_width                          # pallet area in m2


def master(patterns, vtype):
    m = Model()
    x = m.addMVar(patterns.shape[1], lb=0, obj=1, vtype=vtype)
    contraints = m.addConstr(patterns @ x >= 1)

    m.optimize()

    if vtype == GRB.CONTINUOUS:
        return m.objVal, contraints.pi
    else:
        return m.objVal, x.X


def sub(duals):
    m = Model()
    m.setParam("NonConvex", 2)

    x = m.addMVar((len(items)), lb=0, obj=-duals, vtype=GRB.BINARY, name="x")
    cx = m.addMVar((len(items)), lb=radii, ub=pallet_length - radii, name="cx")
    cy = m.addMVar((len(items)), lb=radii, ub=pallet_width - radii, name="cy")

    # Pallet size constraint, the area of packed stacks cannot exceed the pallet area.
    m.addConstr(areas @ x <= pallet_area, name=f"area")

    for i in range(len(radii) - 1):
        for j in range(i + 1, len(radii)):
            lhs = (cx[i] - cx[j])** 2 + (cy[i] - cy[j]) ** 2
            rhs = (x[i] + x[j] - 1) * min_dist[i, j] ** 2
            m.addConstr(lhs >= rhs, name=f"overlap[{i},{j}]")

    def callback(model, where):
        if where == GRB.Callback.MIPNODE:
            if model.cbGet(GRB.Callback.MIPNODE_OBJBST) < -1:
                model.terminate()

    m.optimize(callback)

    return x.X if m.objVal < -1 else None


# Initial pattern: put every item on its own pallet.
patterns = np.eye(len(items))
num_pallets, duals = master(patterns, GRB.CONTINUOUS)

while (new_pattern := sub(duals)) is not None:
    print("Current number of pallets needed (LP):", num_pallets)

    # Check if we already have this pattern. If so, we are done as well.
    if any(np.allclose(new_pattern, column) for column in patterns.T):
        break

    patterns = np.column_stack((patterns, new_pattern))
    num_pallets, duals = master(patterns, GRB.CONTINUOUS)

min_pallets, used_patterns = master(patterns, GRB.BINARY)
unused = set(items)

print("Number of pallets needed (IP):", min_pallets)

for idx, used in enumerate(used_patterns):
    if used:
        on_pallet = items[patterns[:, idx].astype(bool)]
        on_pallet = {item for item in on_pallet if item in unused}
        unused -= on_pallet
        print(f"Put items {on_pallet} on same pallet.")

and the error I am getting is

lhs = (cx[i] - cx[j])** 2 + (cy[i] - cy[j]) ** 2
          ~~~~~~~~~~~~~~^^~~~
TypeError: unsupported operand type(s) for ** or pow(): 'MLinExpr' and 'int'

So I understand that it is not possible to have this substracting of two variables and take their power. How should I go about fixing this problem or chaning my model so that I am able to do the comparison?

I'm using Gurobi v.10.0.1

Answer 1

Instead of

lhs = (cx[i] - cx[j])** 2 + (cy[i] - cy[j]) ** 2

try:

lhs = (cx[i] - cx[j])*(cx[i] - cx[j]) + (cy[i] - cy[j])*(cy[i] - cy[j])

(See the examples in: https://www.gurobi.com/documentation/10.0/refman/py_qex.html)