Решение задачи минимизации над дискретными матрицами с ограничениями

Question

Я пытаюсь решить проблему минимизации заказа с помощью python. Поэтому я распределяю M заказов по N работникам. Каждый работник имеет базовый c уровень энергии X_i, который собирается в векторе X. Кроме того, каждый ордер имеет определенный c уровень энергопотребления E_j, который собирается в E. С учетом сказанного, я пытаюсь решить следующая задача

где Y - некоторый оптимальный уровень энергии, причем норма соответствует 2-норме. Согласно ограничениям, любой столбец может составлять ровно один, поскольку заказ должен быть выполнен и может выполняться только одним работником. Я посмотрел на scipy.optimize, но, насколько я могу судить, он не поддерживает такого рода оптимизацию.

Известны ли какие-либо инструменты в Python для такого рода задач дискретной оптимизации?

Answer 1

Ответ зависит от нормы. Если вы хотите получить 2-норму, это проблема MIQP (Mixed Integer Quadrati c Programming). Он выпуклый, поэтому вокруг немало решателей (например, Cplex, Gurobi, Xpress - это коммерческие решатели). Он также может обрабатываться решателем MINLP, таким как BonMin (с открытым исходным кодом). Некоторыми инструментами моделирования, которые могут помочь, являются Pyomo и CVXPY.

Если вам нужна 1-норма, это можно сформулировать как линейную модель MIP (Mixed Integer Programming). Существует немало решателей MIP, таких как Cplex, Gurobi, Xpress (коммерческий) и CB C, GLPK (с открытым исходным кодом). Некоторыми инструментами моделирования являются Pyomo, CVXPY и PuLP.