from ortools.sat.python import cp_model
SHIPS = 5
SHIP_CAP = 100
FREE_CAP = 20
shipments = [(20, 6), (15, 6), (30, 4), (45, 3)]
model = cp_model.CpModel()
# n[k, s] = number of shipments of size k in ship s
n = {}
for (size, count) in shipments:
for s in range(SHIPS):
n[size, s] = model.NewIntVar(0, count, f'size {size} shipment on ship {s}')
# Each shipment is on exactly one ship
for (size, count) in shipments:
model.Add(
sum(n[size, s] for s in range(SHIPS)) == count
)
# Respect capacity constraints
for s in range(SHIPS):
model.Add(
sum(size * n[size, s] for (size, _) in shipments) <= SHIP_CAP
)
# Want to maximize number of ships with 20 free capacity
# ship_free[s] = True iff ship s has >= 20 free capacity
ship_free = {}
for s in range(SHIPS):
ship_free[s] = model.NewBoolVar(f'ship {s} has enough free capacity')
ship_load = sum(size * n[size, s] for (size, _) in shipments)
model.Add(ship_load <= SHIP_CAP - FREE_CAP).OnlyEnforceIf(ship_free[s])
model.Add(ship_load > SHIP_CAP - FREE_CAP).OnlyEnforceIf(ship_free[s].Not())
model.Maximize(sum(ship_free.values()))
solver = cp_model.CpSolver()
if solver.Solve(model) == cp_model.OPTIMAL:
print([f'{solver.Value(v)} {v}' for v in n.values() if solver.Value(v)])
print(solver.ResponseStats())