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]))
    )

Answer 2

Please look at the below code listing. I have added comments so that the code is self-explanatory. Essentially, the approach is for each bin, count the number of small, medium and large sized balls - so for e.g. consider bin a, if sum_dv_["a", "s"] >= 1(number of small balls in bin a), then the indicator variable bin_dv_["a", "s"] == 1. Then since we can have only one sized ball in a bin so : bin_dv_["a", "s"] + bin_dv_["a", "m"] + bin_dv_["a", "l"] <= 1. This is done for all bins.

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)}

# each ball should be assigned to 1 bin
for i in balls_id_size:
    s.Add(sum(dv[i, bn] for bn in bins) == 1)

# placeholder decision variable to store number of small/medium/large sized
# balls in each bin
sum_size_bin = {
    (i, j): s.IntVar(0, 10, "") for i, j in itertools.product(bins, ["s", "m", "l"])
}
# boolean flag. will be turned = 1 if corresponding sum >= 1
# i.e. if number of small balls in bin 'b' is 2 (say), then the corresponding boolean flag = 1
# sum_size_bin[b, "s"] >= 1 ==> bool_size_bin[b, "s"] = 1
# above constraint will be stated later
bool_size_bin = {
    (i, j): s.BoolVar("") for i, j in itertools.product(bins, ["s", "m", "l"])
}

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"]

for b in bins:
    # number of small sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "s"]
        == sum([j for i, j in dv.items() if (i[0] in s_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of small sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "s"] - 100 * bool_size_bin[b, "s"] <= 0)

    # number of medium sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "m"]
        == sum([j for i, j in dv.items() if (i[0] in m_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of medium sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "m"] - 100 * bool_size_bin[b, "m"] <= 0)

    # number of large sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "l"]
        == sum([j for i, j in dv.items() if (i[0] in l_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of large sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "l"] - 100 * bool_size_bin[b, "l"] <= 0)

    # in each bin we can have balls of only 1 size
    s.Add(bool_size_bin[b, "s"] + bool_size_bin[b, "m"] + bool_size_bin[b, "l"] <= 1)

s.Solve()

# investigate the solution
for b in bins:
    item_binMapping = [i for i in dv if ((i[1] == b) and (dv[i].SolutionValue() > 0.1))]
    item_size = [
        j for i, j in balls_id_size.items() if i in [j[0] for j in item_binMapping]
    ]
    print(list(zip(item_binMapping, item_size)))

Above results in:

# (item_id, bin, size)
[((1, 'a'), 'm'), ((3, 'a'), 'm'), ((6, 'a'), 'm')]
[((0, 'b'), 's'), ((2, 'b'), 's'), ((5, 'b'), 's')]
[((4, 'c'), 'l')]

all bins are homogenous in terms of the balls that they have.

We can add symmetry breaking constraints - because now, bin a or bin b both can have either all medium or all small. This can vary from solver to solver or may be within different runs also. We can force, that bin a should always have small balls, so that all runs yields the same output.