linear-programmingor-toolsmixed-integer-programmingcp-sat

how to implement alldifferent constraint except 0 in ortools


I am using ortools, CP-SAT solver, and I am struggling to write a constraint that will allow for a solution which can have multiple zero's but the remaining decision variable values have to be unique. So alldifferent but I can have multiple zeros. Below is the started code:

from ortools.sat.python import cp_model as cp
x = [model.NewIntVar(lb=0, ub=10, name = "") for _ in range(5)]
# so if I constrain x[0], x[1] to zero, and maximise the sum of x
# then the objective function value should be = 27 [0, 0, 8, 9, 10]

Above is a very simplified version but the anvswer to above will help me in my larger program.


Solution

  • It can be achieved through below:

    from ortools.sat.python import cp_model as cp
    
    model = cp.CpModel()
    x = [model.NewIntVar(lb=0, ub=10, name = "") for _ in range(5)]
    
    n = len(x)
    
    # list of bin_var corresponding to x's. 
    # if bin_var[i] == 1 then x[i] > 0
    # if bin_var[i] == 0 then x[i] == 0
    bin_var = [model.NewBoolVar("") for i in range(n)]
    for i in range(n):
        model.Add(x[i] != 0).OnlyEnforceIf(bin_var[i])
        model.Add(x[i] == 0).OnlyEnforceIf(bin_var[i].Not())
    
    
    # comparing x[i]'s amongst each other
    for i in range(n):
        for j in range(i):
            # we want if bin_var[i] and bin_var[j] are both true
            # then x[i] != x[j]
            bv = model.NewBoolVar("")
            model.AddBoolAnd([bin_var[i], bin_var[j]]).OnlyEnforceIf(bv)
            model.AddBoolOr([bin_var[i].Not(), bin_var[j].Not()]).OnlyEnforceIf(bv.Not())
            model.Add(x[i] != x[j]).OnlyEnforceIf(bv)  
    
    # first 2 x's are 0
    model.Add(x[0] + x[1] == 0)
    
    model.Maximize(sum(x))
    solver = cp.CpSolver()
    status = solver.solve(model)
    
    # investigate solution
    print(f"Optimal value = {solver.ObjectiveValue()}") 
    # optimal value = 27
    
    print([solver.value(x[i]) for i in range(5)])
    # [0, 0, 10, 9, 8]
    # position of 8,9,10 are not restricted through any constraints