Алгоритм минимальной стоимости максимального потока с настраиваемой функцией стоимости

Какие функции стоимости можно использовать в алгоритме минимальной стоимости максимального потока?

Возможна ли функция затрат, подобная:

  • если поток на ребре находится между [1, X], стоимость = FixedCost + C1 + поток * cost_per_flow[C1]
  • если поток на ребре находится между [X + 1, Y], стоимость = FixedCost + C2 + поток * cost_per_flow[C2]
  • и Т. Д.

Это как-то меняет алгоритм?


graph flow algorithm
person Alex D.    schedule 10.07.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете добавить фиксированные затраты и удалить их из уравнения. Затем вы разделяете каждое ребро на 2 ребра, стоимость каждого из которых рассчитана соответствующим образом.

person maniek    schedule 10.07.2012
comment
Не могли бы вы помочь мне понять это на простом примере: допустим, у меня есть ребро с максимальной пропускной способностью 10, и если поток на этом ребре ‹= 5, то стоимость равна количеству_потока * 10, если поток > 5, стоимость равна количеству_потока. * 20. - person Alex D.; 10.07.2012
comment
Обменяйте ребро на 2 параллельных ребра, каждое с пропускной способностью 5. У первого ребра стоимость за единицу равна 10, у второго стоимость за единицу равна 20. Это дает стоимость проталкивания 10 единиц потока, равную 150. Но как @redoubtable заметил, что проблема в целом кажется NP-сложной. - person maniek; 10.07.2012

arrow_upward
1
arrow_downward

Алгоритм максимального потока с минимальной стоимостью - это просто решатель для определенного типа линейной программы.

Что делает линейные программы эффективно разрешимыми, так это выпуклость: в этом случае, если у вас есть два допустимых потока F и G, то для всех t в [0, 1] поток tF + (1-t)G допустим и имеет стоимость ( tF + (1-t)G) t стоимость(F) + (1-t) стоимость(G). Для вашей цели это в основном означает, что FixedCost в [1, X] равен 0, C1 C2, FixedCost в [X + 1, Y] равен (C1 - C2)X 0. Это выглядит примерно так:

6|        .
5|       .
4|      .
3|     .
2|   .
1| .
0.----------
 0 1   X

Вероятно, вам важно, чтобы FixedCost в [1, X] > 0, но это делает задачу NP-сложной. Сокращение от дерева Штейнера в графах состоит в том, чтобы сделать пропускную способность каждого ребра бесконечной и стоить вес, указанный задачей дерева Штейнера для первой единицы и 0 после этого. Сделайте один из k - 1 терминалов Штейнера источником с производительностью k - 1, а остальные стоки с производительностью 1. Запросите самый дешевый поток из k - 1 единиц.

person redoubtable    schedule 10.07.2012