Vehicle routing problems in sage

[Chris Kees]

Hi,

Does anyone know of research being done in sage on combinatorial optimization like the traveling salesman and vehicle routing problems?

Thanks,
Chris

[Raniere Gaia Silva]

Chris,

Sage has a class name 'Mixed integer linear programming' for modeling MIPs and class for LP Solver backends like Co-in, CPLEX, GLPK and Gurobi.

At the moment I haven't know any sage class only for vehicle routing problem.

Raniere Gaia Costa da Silva

[Nathann Cohen]

Sage has a class name 'Mixed integer linear programming' for modeling MIPs and class for LP Solver backends like Co-in, CPLEX, GLPK and Gurobi.

At the moment I haven't know any sage class only for vehicle routing problem.

Yep ! There's a short tutorial about its use there : http://steinertriples.fr/ncohen/tut/LP/

And we also have a TSP function implemented :-)

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.traveling_salesman_problem

Nathann

[Vincent Knight]

I didn't know that SAGE could handle MILP (awesome!), I'm just playing around with it now and was wondering if there was a way to remove a constrain from a particular problem or indeed modify it without reseting the whole problem.

For example:

Say I wanted to solve the problem described in the online tutorial, I would input:

sage: p = MixedIntegerLinearProgram(maximization=False) 
sage: w = p.new_variable(integer=True) 
sage: p.add_constraint(w[0] + w[1] + w[2] - 14*w[3] == 0) 
sage: p.add_constraint(w[1] + 2*w[2] - 8*w[3] == 0) 
sage: p.add_constraint(2*w[2] - 3*w[3] == 0) 
sage: p.add_constraint(w[0] - w[1] - w[2] >= 0)
sage: p.add_constraint(w[3] >= 1) 
sage: _ = [ p.set_min(w[i], None) for i in range(1,4) ] 
sage: p.set_objective(w[3]) 
sage: p.show() 

If I wanted to change the last constraint to be w[0]-w[1]-w[2]>=1 can I do this without resetting the whole p?

(Sorry to hijack the original question).

Thanks,

Vince

--
To post to this group, send email to sage-s...@googlegroups.com
To unsubscribe from this group, send email to sage-support...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URL: http://www.sagemath.org

--
Dr Vincent Knight
Cardiff School of Mathematics
Senghennydd Road,
Cardiff
CF24 4AG
(+44) 29 2087 5548

www.vincent-knight.com

@drvinceknight

Skype: drvinceknight

[Nathann Cohen]

If I wanted to change the last constraint to be w[0]-w[1]-w[2]>=1 can I do this without resetting the whole p?

Not for the moment, but this can be added with a small patch. We just need to expose the functions from the solver's API :-)

Nathann

[Chris Kees]

Hi Nathann,

Thanks! I spent some time with the graph and milp support today, and it's exactly what I was looking for.  Do you have an idea of how the current implementations scale with the size of the graph? Any interest in adding support for parallel algorithms?  I'm interested in the underlying data structures for the graphs and how the objective function expressions are being passed to the low level implementations (e.g. Coin)

Chris

[Nathann Cohen]

Hellooooooooooooooooooooooooooooo !!!

> Thanks! I spent some time with the graph and milp support today, and it's
> exactly what I was looking for.  

Glad to hear it ! :-)

> Do you have an idea of how the current
> implementations scale with the size of the graph?

Oh. Well, I do not use LP to solve problems on huge graphs. But I do solve huge LP for small graphs :-)

> Any interest in adding
> support for parallel algorithms?  

Oh. Well, I guess no one -- least of all me -- would mind. Which kind of algorithms would you have in mind ? :-)

> I'm interested in the underlying data
> structures for the graphs and how the objective function expressions are
> being passed to the low level implementations (e.g. Coin)

Well, I hope that I did the job well on this respect. We use all the solvers through their C/C++ Api, and at this level the functions are given as efficiently a the solvers let us do it, that is something like 2 C arrays (the indices of the variables which have a nonzero coefficient, and the list of coefficients), or through methods for sparse vectors (I think only CBC does that). Of course, when you use the LP classes at Python level, we first have to do some Python operations to convert the information you give to the format the solvers expect, but at least we have control on all levels down to C. So we are more or less free to do as we want :-)

One thing to note : when you have to sum MANY variables, pleaaaaaase do not use sum([ x for x in the_variables_i_want_to_add_together]). There is a Sum function made just for that. It is a pity I had to do such things, but otherwise adding n variables together result in a n^2 algorithm, while linear time should be sufficient :-D

This function is available this way :

from sage.numerical.mip impot Sum

And all the LP codes available in Sage use this Sum function instead of the usual "sum" :-)

Anyway, the code you are interestedin is defined in sage/numerical/mip. The sums/comparisons between MILP variables are implemented in the MIPVariable and LinearFunction classes you will find at the bottom of the file, and you will also be interested by the add_constraint method, and the solver-specific add_linear_constraint functions in the sage/numerical/mip/backend_* files.

Nathann

[Chris Kees]

Hi Nathann!

I found that when installing cbc I had to add "#include <cstdlib>" to
CbcEventHandler.cpp, otherwise I got compilation errors about NULL not
being defined. I'm using gcc 4.6.1. The glpk install went smoothly. I
noticed on your tutorial you also mention IBM's CPLEX. Are the sage
wrappers for it open source?

In terms of parallel algorithms, I'm really not sure what would be
appropriate at this point. I thought there might be some genetic
algorithms that could take advantage of parallelism and possibly also
ways to parallelize the objective functions. At the moment I'm mainly
looking into the background on various logistic and transportation
problems.

Chris

[Nathann Cohen]

Helloooooooo Chris !!!

> I found that when installing cbc I had to add "#include <cstdlib>" to
> CbcEventHandler.cpp, otherwise I got compilation errors about NULL not
> being defined.

Arggggg... Well, this interface is being rewritte anyway. I had a lot of things to do during the previous week (job application) but I should find some time to take care of these nasty patches in the next days :-)

http://trac.sagemath.org/sage_trac/ticket/12220

> I'm using gcc 4.6.1.  The glpk install went smoothly. I
> noticed on your tutorial you also mention IBM's CPLEX.  Are the sage
> wrappers for it open source?

They are ! It is actually part of Sage's source code :
http://hg.sagemath.org/sage-main/file/c239be1054e0/sage/numerical/backends

And you will find at the bottom of this page the instructions to use CPLEX with Sage :

http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html

Note that the latest version of CPLEX requires an additional symbolic link. The previous page has not been updated since this ticket is still waiting for review :

http://trac.sagemath.org/sage_trac/ticket/11958

> In terms of parallel algorithms, I'm really not sure what would be
> appropriate at this point. I thought there might be some genetic
> algorithms that could take advantage of parallelism and possibly also
> ways to parallelize the objective functions. At the moment I'm mainly
> looking into the background on various logistic and transportation
> problems.

Hmmm... O_o

Well, I do not understand what you mean by "parallelize the objective functions", but if you try to implement something at some point I guess it will be the kind of stuff that gets me interested immediately :-)

Nathann