## anonymous 4 years ago A salesman will visit all the cities in the table below from Cincinnati and returned to Cincinnati. Your help is needed to determine the route to be taken this salesman for a minimum total mileage.

1. anonymous

2. ganeshie8

travelling salesman problem... is this from graph theory ?

3. anonymous

yes this is travelling salesman problem, but i just need the linear programming, not the solution

4. anonymous

the decision variable, objective function and constraints

5. ganeshie8

okay.. . this is heavy for me. i hope someone else would answer this,.. @TuringTest @experimentX @Outkast3r09 @zzr0ck3r

6. anonymous

n = 12 c_ij= distance from city i to city j x_ij = 1, if a tour includes travelling from city i to city j 0, otherwise from here i don't know

7. anonymous

the objective function would be the sum of all the miles for route $O = \sum_{i=1}^{12}\sum_{j=1}^{12} x_{ij} *c_{ij}$ as far as the programming, not sure, it seems there are 11! possible routes so the goal is to use a bunch of loops to assign all 11! combinations to x_ij then evaluate each sum and determine the route that yields the minimum value

8. anonymous

i read the final model for TSP, but in the decision variable there is y_ij=flow from node i to node j, should i use this too?

9. anonymous

yes probably, the decision variable y_ij will tell the program what to assign to x_ij sorry i haven't done too much with linear programming or graph theory

10. anonymous

do you have any references, e-book or ever find the similarly question?

11. anonymous
12. anonymous

thank you

13. TuringTest

I'm sorry but this would take a bit too much detail for me to investigate right now. I am also quite tired (it's almost 3am here) so I afraid I'll have to pass you off @Zarkon @myininaya @Callisto @KingGeorge most of them are online right now, hopefully one comes and helps Good luck!

14. TuringTest

@asnaseer @experimentX @satellite73

15. anonymous

thank you turing