1
$\begingroup$

I am trying to solve an assignment problem where all the variables are continuous. I have a set of sources S, and another set of destinations D. Each source and destination have capacity/demand expressed as continuous variables. There is a distance associated with each source-destination. I need to find the ideal allocation while minimizing the total distance in the network. A source can supply to multiple destinations, and the reverse holds true as well. The caveat is that the allocation has to be split among multiple sources for every destination. For example, we have 3 sources S1, S2, S3 with capacities 1081.52, 3810.48, 950.64 respectively. There are 2 destinations D1, D2 with demands 1759.38, and 3993.21. My final assignment looks like this:

Destinations Sources Supply Total Demand at Destination
D1 S1 153.67 1759.38
D1 S2 745.12 1759.38
D1 S3 860.59 1759.38
D2 S1 927.85 3993.21
D2 S2 3065.36 3993.21

What type of algorithm should I be looking at for such problems? I also want to place constraints on how many times a source can be used.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ transportation problem $\endgroup$
    – RobPratt
    Aug 26, 2022 at 15:23
  • $\begingroup$ I used the pulp package from Python and set this up as as a transportation problem, but I'm not completely sure if my constraints are correct. The supply constraint says the sum of supplies should equal the total sum, and similar for the demand constraints at the destination but pulp returns that it's infeasible. $\endgroup$
    – PrashanthVajjhala
    Aug 26, 2022 at 17:06
  • 3
    $\begingroup$ Your total supply exceeds your total demand. If you want equality constraints everywhere, introduce a dummy demand node to absorb the excess. Otherwise, use <= for supply constraints and >= for demand constraints. $\endgroup$
    – RobPratt
    Aug 26, 2022 at 17:30
  • $\begingroup$ A constraint on how many times a source can be used will require an integer programming model. By "the allocation has to be split", do you mean that no destination can be served by a single source? $\endgroup$
    – prubin ♦
    Aug 26, 2022 at 17:33
  • $\begingroup$ Correct, I require every destination to be served by multiple sources. $\endgroup$
    – PrashanthVajjhala
    Aug 26, 2022 at 18:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.