Минимизируйте AbsEquality, а не применяйте его в OrTools

Я пытаюсь решить следующее с помощью инструментов ИЛИ:

Даны следующие пакеты с шариками разного цвета:

сумка красный синий зеленый черный А 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= [
[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)

возвращает действительные веса:

82 2 70 78 5 79

Если я изменю настройку на что-то вроде

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

Я предполагаю, что модель становится невозможной из-за того, что нет весов, удовлетворяющих AbsEquality для каждого цвета.

Как я могу изменить это, чтобы получить решение, наиболее близкое к равномерному распределению, даже если идеальное решение невозможно?

Вы имеете в виду «четное количество» или «равное количество» шаров каждого цвета?

Christopher Hamkins 03.02.2023 12:10

Если вы стремитесь получить максимально равное количество шаров каждого цвета, вы можете создать переменную, которая представляет собой разницу между максимальным количеством шаров любого цвета и минимальным количеством шаров любого цвета, а затем добавить в качестве цели минимизировать эту переменную.

Christopher Hamkins 03.02.2023 15:11

Что касается пресса, вы можете посмотреть github.com/google/or-tools/blob/stable/examples/python/…

Laurent Perron 03.02.2023 15:35

Спасибо @ChristopherHamkins! Поправлю и формулировку вопроса.

Chris 04.02.2023 03:14

Только этот последний не очень серьезный комментарий: если бы вы также допустили ноль в качестве количества мешков, вы всегда могли бы получить точное решение, а именно 0 шаров каждого цвета ;-)

Christopher Hamkins 06.02.2023 10:43
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
5
80
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Предложение Кристофера Хэмкинса отлично сработало:

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)

Другие вопросы по теме

Как в or-tools, VRPTW, включить ограничение, согласно которому некоторые остановки должны посещаться только одним подмножеством транспортных средств?
Использование Google OR-Tools для решения задачи маршрутизации транспортных средств (VRP) для БПЛА
Решите проблему стабильных браков с помощью программирования ограничений - объект BoundedLinearExpression не является итерируемым
Программирование ограничений, как сложить x[i] <= (max(x[:i]) + 1)
Как использовать решатель CP-SAT или другие инструменты для поиска трехмерных массивов с ограничениями на строки, столбцы и трубки (представляющие школьные классы, термины и дни)?
Можем ли мы распечатать только первую стратегию решения, а не решение локального поиска в Google ИЛИ Tools?
Преобразовать строку в выражение
Установка OR-Tools в Visual Studio 2022
Как использовать XPRESS в качестве решателя в Google ИЛИ Tools?
Распределение назначений смен в решателе ограничений (ortools)