linear-programmingor-toolsmixed-integer-programming

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


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


Solution

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