Алгоритм Форда-Фулкерсона с «взвешенными» ребрами и минимальной / максимальной производительностью вершины - PullRequest
Новая
       25

Алгоритм Форда-Фулкерсона с «взвешенными» ребрами и минимальной / максимальной производительностью вершины

0 голосов
/ 02 ноября 2018

Мой вопрос похож на этот:

Алгоритм Форда-Фулкерсона с "взвешенными" ребрами

Однако я включаю минимальные и максимальные возможности для заданий. Мало того, что у ребер есть вес («тренировка»), и что каждый студент должен быть назначен, но и то, что в некоторых заданиях не будет назначено ни одного ученика, а в некоторых заданиях будет максимальная вместимость учеников, в то время как все остальные будут по крайней мере быть на минимуме. 

proc optmodel;
set Students = {'S1', 'S2', 'S3', 'S4', 'S5', 'S6'}; 
set Projects = {'P1', 'P2', 'P3'};   

number projMinCapacity{Projects} = [2, 2, 2];
number projMaxCapacity{Projects} = [3, 3, 3];

number ranking{Students, Projects} = [ 
1 2 0
2 1 0
0 1 2
2 1 0
1 0 2
2 0 1
];

var flow{Students, Projects} binary;

maximize z = sum{s in Students, p in Projects}(flow[s, p]*(ranking[s, p]));

con sumPerStudent{s in Students} : sum{ p in Projects}flow[s,p] = 1;
con maxFlow{p in Projects} : sum{s in Students}flow[s,p] <= projMaxCapacity[p];
con minFlow{p in Projects} : sum{s in Students}flow[s,p] >= projMinCapacity[p];

solve;
print z flow;
quit;

^ Я включил сюда свою рабочую реализацию в SAS Studio как PoC, но для моего проекта мне нужно что-то, что может быть включено в веб-приложение.

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

Спасибо!

...