Pulp Python устанавливает ограничения при суммировании значений в столбце

Привет, это мой первый вопрос здесь, так что полегче со мной, если я неправильно форматирую.

Я пытаюсь смоделировать таблицу, в которой каждое значение равно 1 или 0. Я хотел бы определить, равна ли сумма столбца 0 или нет, а затем проверить, сколько столбцов > 0. Основная проблема, которую я пытаюсь решить, — это планирование встреч, где каждый столбец представляет одну встречу. Я упростил это здесь, так как в оригинале я использую фрейм данных, чтобы сопоставить компетенции врача с потребностями пациента (каждая строка — это потребность пациента). Моя проблема началась, когда я попытался убедиться, что все переменные могут быть равны только 1, если в одном, если они были в одном из 2 столбцов, поэтому мой упрощенный код здесь, чтобы попытаться понять, где я ошибаюсь.

Я создал словарь переменных целлюлозы с ключами ROWS и COLS и значением == 0 или 1.

В определении проблемы я пытаюсь присвоить значение 1 сумме столбца, если сумма значений строки в столбце >= 1 и 0 в противном случае, а затем суммировать итог. Это должно позволить мне установить общее количество столбцов, сумма которых равна >= 1, например, только 2 столбца представлены ненулевыми переменными.

В приведенном ниже коде моя цель состоит в том, чтобы свести к минимуму общую сумму всех переменных, НО должно быть 2 столбца, которые содержат переменную 1, т.е. сумма 2 столбцов равна >=1.

Заранее спасибо.

import pulp as Pulp
ROWS = range(1, 6)
COLS = range(1,5)

prob = Pulp.LpProblem("Fewestcolumns", Pulp.LpMinimize)
choices = Pulp.LpVariable.dicts("Choice", (ROWS, COLS), cat = "Integer", lowBound=0, upBound=1)
prob += Pulp.lpSum([choices[row][col] for row in ROWS for col in COLS])
prob += Pulp.lpSum([1 if Pulp.lpSum([choices[row][col] for row in ROWS]) >= 1 else 0 for col in COLS]) == 2



prob.solve()

print("Status:", Pulp.LpStatus[prob.status])
for v in prob.variables():
    print(v.name, " = ", v.varValue)`

Мои результаты:

C:\Users\xxxComputing\LinearProgramming\Scripts\python.exe C:/Users/xxx/Computing/LinearProgramming/LinearProgTest.py
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - C:\Users\xxxx\Computing\LinearProgramming\lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe C:\Users\simon\AppData\Local\Temp\4f8ff67726844bde8abe98316b6338c4-pulp.mps timeMode elapsed branch printingOptions all solution C:\Users\simon\AppData\Local\Temp\4f8ff67726844bde8abe98316b6338c4-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 6 COLUMNS
At line 67 RHS
At line 69 BOUNDS
At line 90 ENDATA
Problem MODEL has 1 rows, 20 columns and 0 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Problem is infeasible - 0.00 seconds
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

Status: Infeasible
Choice_1_1 = 0.0
Choice_1_2 = 0.0
Choice_1_3 = 0.0
Choice_1_4 = 0.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 0.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 0.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 0.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 0.0

Process finished with exit code 0

Я ожидал примерно такого списка переменных с возможным решением:

Status: Optimal
Choice_1_1 = 1.0
Choice_1_2 = 1.0
Choice_1_3 = 0.0
Choice_1_4 = 0.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 0.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 0.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 0.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 0.0

Редактирует: Большое спасибо AirSquid за то, что указали мне правильное направление. Я все еще борюсь с большими ограничениями M.

Я пробовал это:

import pulp as Pulp
ROWS = range(1, 6)
COLS = range(1,5)

prob = Pulp.LpProblem("Fewestcolumns", Pulp.LpMaximize)
choices = Pulp.LpVariable.dicts("Choice", (ROWS, COLS), cat = "Integer", lowBound=0, upBound=1)
used = Pulp.LpVariable.dicts("used", COLS, cat = "Binary")
b = Pulp.LpVariable.dicts("b", COLS, cat = "Binary")

prob += Pulp.lpSum([choices[row][col] for row in ROWS for col in COLS])
for rows, items in choices.items():
    prob += Pulp.lpSum(cols for cols in items.values()) == 1

M = 20
for col in COLS:
    prob += b[col] >= (Pulp.lpSum([choices[row][col] for row in ROWS]) - 1) / M
    prob += used[col] >= M * (b[col] - 1)

prob += Pulp.lpSum([used[col] for col in COLS]) == 2
prob.solve()

print("Status:", Pulp.LpStatus[prob.status])
for v in prob.variables():
    print(v.name, " = ", v.varValue)

Я получил следующие результаты:

 Result - Optimal solution found

Objective value:                5.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.02

Status: Optimal
Choice_1_1 = 0.0
Choice_1_2 = 0.0
Choice_1_3 = 0.0
Choice_1_4 = 1.0
Choice_2_1 = 0.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 1.0
Choice_3_1 = 0.0
Choice_3_2 = 0.0
Choice_3_3 = 0.0
Choice_3_4 = 1.0
Choice_4_1 = 0.0
Choice_4_2 = 0.0
Choice_4_3 = 0.0
Choice_4_4 = 1.0
Choice_5_1 = 0.0
Choice_5_2 = 0.0
Choice_5_3 = 0.0
Choice_5_4 = 1.0
b_1 = 1.0
b_2 = 1.0
b_3 = 1.0
b_4 = 1.0
used_1 = 1.0
used_2 = 1.0
used_3 = 0.0
used_4 = 0.0

Process finished with exit code 0

Не уверен, что я сделал неправильно - я надеялся на некоторые 1,0 в столбцах, которые не являются столбцом 4. Есть еще подсказки, пожалуйста?

Почему в 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 может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
0
95
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

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

Ваш вопрос ясен, но настройка вашего LP не совсем ясна. Мы можем вернуться к этому.

Вы получаете сообщение об ошибке, потому что использовали утверждение if в своем суммировании. Это незаконно. Когда pulp заставляет математическую модель решать, значения переменных неизвестны, поэтому мы не можем использовать операторы if в формулировке. Похоже, вы хотите использовать здесь ограничение «большой M», чтобы увидеть, было ли что-то выбрано в столбце. (Погуглите или посмотрите на этом сайте, это фундаментальная концепция LP, и я опубликовал несколько ответов с ней). Вам нужно будет ввести еще одну двоичную переменную, индексированную по столбцу, а затем минимизировать ее... В псевдокоде:

used[col] a binary variable, indexed by Col
M = some suitably large variable (a max).  In your case the number of rows would be appropriate.

Затем:

sum(choices[row, col] for row in rows) <= used[col] * M    

При желании вы можете минимизировать переменную used, чтобы минимизировать используемые столбцы.

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

ZachCope 24.11.2022 20:58

У меня были проблемы с >, вызывающим ошибки; но >= не заставляет used_ variable быть либо 1, либо 0.

В итоге я добавил в формулу очень небольшое число, чтобы гарантировать, что если моя переменная решения b_ == 1, то мой used_variable определенно будет равен 1:

for col in COLS:
    prob += b[col] >= 0.001 + ((Pulp.lpSum([choices[row][col] for row in ROWS]) - 1) / M)
    prob += used[col] >= (M * (b[col] - 1)) + 0.001
    prob += Pulp.lpSum([used[col] for col in COLS]) == 2

Это дало следующий результат:

Status: Optimal
Choice_1_1 = 0.0
Choice_1_2 = 1.0
Choice_1_3 = 0.0
Choice_1_4 = 0.0
Choice_2_1 = 1.0
Choice_2_2 = 0.0
Choice_2_3 = 0.0
Choice_2_4 = 0.0
Choice_3_1 = 0.0
Choice_3_2 = 1.0
Choice_3_3 = 0.0
Choice_3_4 = 0.0
Choice_4_1 = 0.0
Choice_4_2 = 1.0
Choice_4_3 = 0.0
Choice_4_4 = 0.0
Choice_5_1 = 0.0
Choice_5_2 = 1.0
Choice_5_3 = 0.0
Choice_5_4 = 0.0
b_1 = 1.0
b_2 = 1.0
b_3 = 0.0
b_4 = 0.0
used_1 = 1.0
used_2 = 1.0
used_3 = 0.0
used_4 = 0.0

Кажется, это работает с разным количеством столбцов, чтобы дать приемлемые ответы.

Я не уверен, насколько хакерским является это решение, поэтому, если есть более элегантный способ, не стесняйтесь отвечать!

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