Single source Multi commodity transportation problem

[Mike Halbheer]

Hi guys,

I am currently working on a project, that I am trying to solve using a transportation problem. Essentially what I need to do is assign students to their schools based on where they live. Since they can study different things I am modeling it as a Multi commodity transportation problem. One of the restrictions that have been imposed on the project is that every student of the same study direction and the same place of living need to be assigned to the same school. This would give the following mathematical model: 

I have managed to implement all constraints except for that last one. My attempt was to do it the following way.

Adding this last constraint causes havoc, including the solver ignoring all other conditions. So apparently what I am trying to do is wrong. So could anyone tell me how I would achieve a single source Multi commodity transportation problem?

[Sean Grogan]

You're talking about constraint 2?  The first one, not the last one

The picture of your code isn't big enough for me to be certain... but it looks like your d_gl parameter inside the sum?  e.g. your code translates to 

latex :   $\sum [x_{gsl} - d_{gl}]  = 0$  

what it should look like is 

Latex : $\sum [x_{gsl}] - d_{gl}  = 0$

I think the code should be something like

for g in G: for l in L:
    mdl.addConstraint(lpconstraint(lpSum(x[g,s,l] for s in S) - lherlinge[g,l],  sense=lpconstraintEQ, rhs=0))

Sean Grogan
sean....@gmail.com

--
New posters to this group are moderated which can take up to 48 hours, so please be patient if your first post takes a while to turn up.
---
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/a462b8cb-1592-43a4-b184-a1da7af44a7bn%40googlegroups.com.

[Mike Halbheer]

Thanks for your answer. I am in fact talking about the last constraint. My problem is with the either-or condition I would need to impose, which I cannot seem to figure out. To make it easier to understand my problem I have gone ahead and uploaded my entire code so far to Github. I have also gone ahead and added comments in the code to mark where I am imposing which constraint, using the numbering of the LaTeX equations.

https://github.com/hamike/gis_schools/blob/master/gis_schools.py

The first three work just fine, just the last one is causing problems.

[Sean Grogan]

Your constraints (5) also are not the same as the code outlined.  Also when you say "Adding this last constraint causes havoc"... this means infeasibility?  or a python/pulp error?  because the code has no error (which I initially assumed)

If you are struggling with infeasibility:

Using the lp.sum() in your code, you've created is equivalent to 

latex : $\sum_{s\in S} [x_{gsl} - d_{gl}] = 0$

You want something more like:

    for g in gemeinden:
        for l in lehren:
            for s in schulen:
                if (g, s, l) in x:
                    model.addConstraint(
                        pulp.LpConstraint(
                            e=(x[g, s, l] - lehrlinge[g, l] if (x[g, s, l] == lehrlinge[g, l]) else x[g, s, l]),
                            sense=pulp.LpConstraintEQ,
                            name='Unique_assignment[{}, {}, {}]'.format(g, s, l),
                            rhs=0
                        ))

But your coded model is still infeasible.  Because you're now saying (in your code) if  x[g, s, l] == lehrlinge[g, l], the solver makes each  x[g, s, l] == lehrlinge[g, l] when you want the x[g, s, l] to be either 0 or  lehrlinge[g, l], correct?  Last I checked that indicator constraints can't be called directly with pulp (vs. cplex or gurobi https://www.gurobi.com/documentation/8.1/refman/py_model_addgenconstrindic.html)

if you want to use pulp still:

loosen the restriction of == to make it <= (i.e. sense=pulp.LpConstraintLE,  or 0 <= x_{gsl} <= g_{gl}) which gives a feasible solution. 

or try and formulate it as M-constraint, like this: 

Sean Grogan
sean....@gmail.com

To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/b13f47e3-8f5c-4b94-9132-611e24373a57n%40googlegroups.com.

[Mike Halbheer]

You are absolutely right, it causes infeasibility.

Now if I understand correctly you suggest loosening the constraint for x_{gsl} to be between 0 and d_{gl}. However, if I am not mistaken this woudl already be satisfied by a combination of (2) and (4). I need all values of x_{gsl} to be either 0 or d_{gl} though, since I am not allowed to allocate students from the same community and same study type to different schools.

Forgive me if I do not quite understand how I would need to implement your suggestion of the M-constraint.

[Sean Grogan]

It's getting late in the day here and I didn't want to leave you hanging overnight.  You're right that my constraint is incorrect.  I can't quite come up with a formula off the top of my head, but what you need to do is come up with (probably several) constraints that, given x_{gs'l} which is in the optimal solution, will force the other x_{gsl} (for all s != s') variables to zero.  That's usually taken care of with Big M constraints (or constraints like Big M, such as the precedence/slope constraints in the open pit mine production scheduling problem).  The thing that got me confused was that your x_{gsl} are integer, not binary.  

There is a way to do it, it's just not coming to me right now.  You might need to introduce an indicator binary variable (say y_{s}) that is 1 when  x_{gsl} is greater than 0.  and then you say that \sum y_s <= 1 so only one x_{gsl} > 0 for any given g, l 

Sean Grogan
sean....@gmail.com

To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/b839a066-4e15-426a-affa-bbce4ed22321n%40googlegroups.com.

[Mike Halbheer]

Thanks so much. It got late for me too so I had to head to bed as well. I have already thought of introducing a y. My problem there is that I cannot figure out how I would set y_{s} based on the value of x_{gsl}. For some reason it appears that checking against the value of x will always yield true.

I will read up on Big M constraints and see if I can come up with a solution that way.

[Mike Halbheer]

I have finally figured it out. Once I will have time I will document my solution and upload it here, so people can use it. Thanks for your help Sean.