How to express that 2 binary variable are different in MIP solver

Question

I have an assignment problem where I want to allocate a number of balls to different containers. Every ball has a certain size - small, medium and large. I want to add a constraint that balls with 2 different colours should be in different containers.

I am using google-OR-tools linear solver. And apparently, I cannot express != constraint in the modelling construct.

I was able to get started like below :

from ortools.linear_solver import pywraplp
import itertools

s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

balls_size = ["s", "m", "s", "m", "l", "s", "m"]
balls_id_size = {i: j for i, j in zip(range(len(balls_size)), balls_size)}

bins = ["a", "b", "c"]

dv = {(i, j): s.BoolVar("") for i, j in itertools.product(balls_id_size, bins)}

what I want all bins should be homogenous in terms of what sizes of the ball it keeps

Answer 1

Per Laurent's suggestion, below is my attempt with CP-SAT solver. Certainly with AddAllDifferent constraint, code becomes more simpler and easy to read and understand.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

balls_size = ["s", "m", "s", "m", "l", "s", "m"]
balls_id_size = {i: j for i, j in zip(range(len(balls_size)), balls_size)}

bins = [1, 2, 3]

dv = {i: model.NewIntVar(1, 3, "") for i in balls_id_size}

s_balls = [i for i, j in balls_id_size.items() if j == "s"]
m_balls = [i for i, j in balls_id_size.items() if j == "m"]
l_balls = [i for i, j in balls_id_size.items() if j == "l"]

# combinations of small, medium and large balls
# all of these combinations should belong to different bins
all_diffs = itertools.product(s_balls, m_balls, l_balls)

for i, j, k in all_diffs:
    model.AddAllDifferent(dv[i], dv[j], dv[k])

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

# investigate the solution
for i in dv:
    print(
        "ball_id = "
        + str(i)
        + " , "
        + "size = "
        + str(balls_id_size[i])
        + " --> "
        + "bin_id = "
        + str(solver.Value(dv[i]))
    )