Minimize AbsEquality rather than enforce in OrTools

Question

I'm trying to solve the following using OR tools:

Given the following bags containing different colors of balls:

bag	red	blue	green	black
A	10	5	85	0
B	25	50	25	0
C	0	100	0	0
D	90	5	5	0
E	2	0	98	0
F	0	0	0	100

How many of each type of bag would I need to have an equal number of each color of ball?

For cases like this where there is an exact answer, the following code:

bags= [
[10,5,85,0],
[25,50,25,0],
[0,100,0,0],
[90,5,5,0],
[2,0,98,0],
[0,0,0,100]
]


bags_n = len(bags)
color_n = len(bags[0])

print(f'Bags: {bags_n}')
print(f'Colors: {color_n}')

color_count= [0] * color_n

for c in range(color_n):
  for b in bags:
    color_count[c]+= b[c]


print(color_count)
print(f'Inital total: {sum(color_count)}')
print(f'Inital equal share: {sum(color_count)//color_n}')

model = cp_model.CpModel()

weights = []

for r in range(bags_n):
  weights.append(model.NewIntVar(1,1000,f'Weight of Bag: {r}'))

total = model.NewIntVar(0, 100000, 'total')

model.Add(
    sum(flatten(
          [[bags[r][c] * weights[r] for r in range(bags_n)] for c in range(color_n)]
        )) == total
)
          
equal = model.NewIntVar(0, 10000, 'equal share')
model.AddDivisionEquality(equal, total, color_n)

for c in range(color_n):
  diff_c = model.NewIntVar(0, 1000, 'diff_'+str(c))
  model.Add(diff_c == sum([bags[r][c] * weights[r] for r in range(bags_n)]) - equal)
  model.AddAbsEquality(0, diff_c)

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

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
    for v in weights:
      print(f'{solver.Value(v)}')
    print(f'total = {solver.Value(total)}')
    print(f'equal share = {solver.Value(equal)}')
else:
    print(status)

gives back valid weights:

82 2 70 78 5 79

If I change the setup to something like

bags= [
[50,40,10],
[30,20,50],
[30,30,40],
[30,25,45],
]

The model becomes infeasible, I assume due to the fact that there are no weights that satisfy the AbsEquality for every color.

How can I change this to get me the solution closest to an even distribution even if a perfect solution is infeasable?

Answer 1

Christopher Hamkins' suggestion worked great:

bags= [
[50,40,10],
[30,20,50],
[30,30,40],
[30,25,45],
]


bags_n = len(bags)
color_n = len(bags[0])

print(f'Bags: {bags_n}')
print(f'Colors: {color_n}')

color_count= [0] * color_n

for c in range(color_n):
  for b in bags:
    color_count[c]+= b[c]



    
print(color_count)
print(["{0:.0%}".format(c/sum(color_count)) for c in color_count])


model = cp_model.CpModel()

weights = []

for r in range(bags_n):
  weights.append(model.NewIntVar(1,500,f'Weight of Bag: {r}'))

max = model.NewIntVar(0,100000000,f'Max')
model.AddMaxEquality(max,
                     [sum([bags[r][c] * weights[r] for r in range(bags_n)]) for c in range(color_n)]
                     )

min = model.NewIntVar(0,100000000,f'Min')
model.AddMinEquality(min,
                     [sum([bags[r][c] * weights[r] for r in range(bags_n)]) for c in range(color_n)]
                     )
diff = model.NewIntVar(0,100000000,f'Diff')
model.Add(max - min == diff)

model.Minimize(diff)


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

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'max = {solver.Value(max)}')
    print(f'min = {solver.Value(min)}')
    print(f'diff = {solver.Value(diff)}')

    bag_weights = [0] * bags_n

    for i,v in enumerate(weights):
      bag_weights[i] = solver.Value(v)
      print(f'{solver.Value(v)}')
    
    color_count = [0] * color_n

    for c in range(color_n):
      for i,b in enumerate(bags):
        color_count[c]+= (b[c] * bag_weights[i])


    
    print(color_count)
    print(["{0:.0%}".format(c/sum(color_count)) for c in color_count])

else:
    print(status)