7 ms·

Based on my knowledge of operations research, there is likely no AI involved in solving any of these problems. This is just a pure math problem, one that someon

by pg_bot 8y ago

Based on my knowledge of operations research, there is likely no AI involved in solving any of these problems. This is just a pure math problem, one that someone who knows excel really well could solve. While you may not understand the math involved, that doesn't mean that this is a black box. This type of work has been put into practice for longer than the author has been alive. I don't think we need to reflect upon the changes it will bring to society since it's already old hat. I will admit that "What the Boston School Bus Schedule Can Teach us About Junior year Undergraduate Mathematics" doesn't have the same ring to it.

imh 8y ago
I do machine learning and stats for a living. You could describe practically all of what's called AI by the popular press in the same way. Mostly "complex algorithms that classify/predict/optimize/decide between things." The lesson is still there and is still applicable to those things.
ska 8y ago
Scheduling with constraints is a significantly more difficult problem than you suggest - well beyond junior year and the really general stuff holds open research problems. You are right about the popular (and, increasingly, technical also) mis-use of the term "AI" but that ship sailed a long time ago.
- pg_bot 8y ago
  I am speaking from personal experience. Bus scheduling with constraints was literally the textbook problem I was solving in my Operations Research class during my Junior year in undergrad. I would not classify myself as a genius, did not go to an Ivy league school, and I could do it then. It was on the harder end of the spectrum for my classes, but approachable to any undergrad studying mathematics. If you can pass a linear algebra class, you can learn how to solve these types of problems.
  - gbear605 8y ago
    Only for certain types of constraints, however.
  - ska 8y ago
    I am also speaking from experience. It's not my area of mathematics but I have a passing familiarity. There are simplified problems that can be presented to undergrads, sure - just like most areas. Intro courses often use a toy version of this to show integer programming and the like. But there is as reason these are "toy" version - some of the general variants are NP-hard and have connections to interesting and open problems. Many real world variants are not trivial to undertake. On a general note - if you hear someone who is even slightly plausibly qualified say "Problem X is hard" and you think "Huh, I solved problem X in undergrad" - the overwhelmingly most likely reason is that you aren't, in fact, talking about the same "problem X". This can of course be due to the method of communication (e.g. science journalism)
    - pg_bot 8y ago
      I agree, solving for the optimal solution is generally an NP hard problem when dealing with real world constraints. The real world is not a word problem in a math textbook. In practice you can often get away with improving an existing system instead of finding the "best" solution to the problem. This is what pragmatic people do, and it is often a lot easier than we think it is. If you frame the problem as "finding the best possible solution to the bus routing problem factoring in all the needs of the populace", I would agree that's a very hard problem. If you frame the problem as "can we improve the existing Boston bus routing system", it will likely be a lot easier. Always remember that perfect is the enemy of done.
      - ska 8y ago
        You, like the other poster, seem to be assuming that nobody has tried "can we improve the existing ..." using the obvious tools. I find this attitude both puzzling and patronizing of the people involved. Without specific knowledge, is seems far more likely the obvious things have been tried by reasonably intelligent people. As you say, it's what pragmatic people do (and it's usually still more complicated than the intro textbook versions) Now I have no specific knowledge of this particular problem, but the article does suggest it is something that has been tried before (rescheduling) and failed for various reasons. I'll give them the benefit of the doubt, why won't you? Really I'm objecting to the idea that "if only we could have found a math undergrad, this would have been improved years ago". That's a particularly naive view.
joe_the_user 8y ago
Sure, an inclusive headline is "What the Boston School Bus Schedule Can Teach us About letting algorithms decide". Because AI or upper division math, the decision was consigned to a process that is opaque to the average parent. And the opaqueness more or less conceals basic tradeoffs. The school has figured out that starting HS late-ish and letting all student out before dark provides the best situation for students. But if all school levels start at the same time, the district has would have to have a bunch of school buses and drivers that wouldn't be used other times. To avoid all this "waste", the district has to decide which schools to shove into some other, worse schedule. They thus came up with a algorithm to minimize the amount of bad-scheduling but which maintains the existence of bad-schedules. And when it sent an entirely different group than before into the bad-scheduled situation, naturally that group complained - it didn't help these were wealthier, whiter groups with influence. Sure, you thus have more affluent people saying they didn't want to be the one sacrificed here. But you also ask, why sacrifice anyone? Why not bite the bullet and have a good, standard schedule for all schools? You'd offending the modern god of efficiency but you'd actually be aiming for a greater good. The article talks about Trolley Car Problems a bit and how people relate to algorithms "solving" these. The thing is instead of saying "that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed."
- pg_bot 8y ago
  "that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed." Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes. Every decision comes at a cost, we don't have unlimited resources so we should reach for tools that attempt to maximize what we are willing to spend. If you believe that no one needs to sacrifice in order to solve society's problems, you are living in a fantasy.
  - joe_the_user 8y ago
    Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes. Basic income is system that would approximately guarantee all people's basic needs are met yet there is certainly opposition to it.
est 8y ago
I am extremely interested how to solve routing problem with Excel. Can you share few links or articles?
- yorak 8y ago
  Bus routing is just a variant of the vehicle routing problem (VRP), which itself is a generalization of traveling salesman problem (TSP) but with multiple salespersons doing the traveling. There is an Excel sheet for solving such problems, and if one wishes to go further, the basic heuristic and metaheuristic algorithms are not that hard to implement either. http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-solver/ http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-sol... With these keywords you are welcome to fall into this rabbit hole as deep as you wish. I promise to greet you on my way up (currently finishing my PhD on the topic).
  - est 8y ago
    Thanks!
yorak 8y ago
It is true that such problems /can/ be solved via mathematical linear programming (for those coming outside math circles, please note that the term programming here has nothing to do with coding) and this is how they are usually presented in academia. However, in practice, it is not something one would be advised to do. Usually, the complexities of the real world routing and scheduling make it impossible to solve these models of practical size. Therefore, numerous heuristic and metaheuristic algorithms have been proposed and are usually used in practical applications. These usually are sound familiar to those that have some experience with "old" AI: genetic algorithms, ant colony systems, simulated annealing, and even neural networks have been succesfully applied to provide "good enough" solutions to these problems.

by pg_bot 8y ago

imh 8y ago

I do machine learning and stats for a living. You could describe practically all of what's called AI by the popular press in the same way. Mostly "complex algorithms that classify/predict/optimize/decide between things." The lesson is still there and is still applicable to those things.

ska 8y ago

Scheduling with constraints is a significantly more difficult problem than you suggest - well beyond junior year and the really general stuff holds open research problems. You are right about the popular (and, increasingly, technical also) mis-use of the term "AI" but that ship sailed a long time ago.

pg_bot 8y ago
I am speaking from personal experience. Bus scheduling with constraints was literally the textbook problem I was solving in my Operations Research class during my Junior year in undergrad. I would not classify myself as a genius, did not go to an Ivy league school, and I could do it then. It was on the harder end of the spectrum for my classes, but approachable to any undergrad studying mathematics. If you can pass a linear algebra class, you can learn how to solve these types of problems.
- gbear605 8y ago
  Only for certain types of constraints, however.
- ska 8y ago
  I am also speaking from experience. It's not my area of mathematics but I have a passing familiarity. There are simplified problems that can be presented to undergrads, sure - just like most areas. Intro courses often use a toy version of this to show integer programming and the like. But there is as reason these are "toy" version - some of the general variants are NP-hard and have connections to interesting and open problems. Many real world variants are not trivial to undertake. On a general note - if you hear someone who is even slightly plausibly qualified say "Problem X is hard" and you think "Huh, I solved problem X in undergrad" - the overwhelmingly most likely reason is that you aren't, in fact, talking about the same "problem X". This can of course be due to the method of communication (e.g. science journalism)
  - pg_bot 8y ago
    I agree, solving for the optimal solution is generally an NP hard problem when dealing with real world constraints. The real world is not a word problem in a math textbook. In practice you can often get away with improving an existing system instead of finding the "best" solution to the problem. This is what pragmatic people do, and it is often a lot easier than we think it is. If you frame the problem as "finding the best possible solution to the bus routing problem factoring in all the needs of the populace", I would agree that's a very hard problem. If you frame the problem as "can we improve the existing Boston bus routing system", it will likely be a lot easier. Always remember that perfect is the enemy of done.
    - ska 8y ago
      You, like the other poster, seem to be assuming that nobody has tried "can we improve the existing ..." using the obvious tools. I find this attitude both puzzling and patronizing of the people involved. Without specific knowledge, is seems far more likely the obvious things have been tried by reasonably intelligent people. As you say, it's what pragmatic people do (and it's usually still more complicated than the intro textbook versions) Now I have no specific knowledge of this particular problem, but the article does suggest it is something that has been tried before (rescheduling) and failed for various reasons. I'll give them the benefit of the doubt, why won't you? Really I'm objecting to the idea that "if only we could have found a math undergrad, this would have been improved years ago". That's a particularly naive view.

joe_the_user 8y ago

Sure, an inclusive headline is "What the Boston School Bus Schedule Can Teach us About letting algorithms decide". Because AI or upper division math, the decision was consigned to a process that is opaque to the average parent. And the opaqueness more or less conceals basic tradeoffs. The school has figured out that starting HS late-ish and letting all student out before dark provides the best situation for students. But if all school levels start at the same time, the district has would have to have a bunch of school buses and drivers that wouldn't be used other times. To avoid all this "waste", the district has to decide which schools to shove into some other, worse schedule. They thus came up with a algorithm to minimize the amount of bad-scheduling but which maintains the existence of bad-schedules. And when it sent an entirely different group than before into the bad-scheduled situation, naturally that group complained - it didn't help these were wealthier, whiter groups with influence. Sure, you thus have more affluent people saying they didn't want to be the one sacrificed here. But you also ask, why sacrifice anyone? Why not bite the bullet and have a good, standard schedule for all schools? You'd offending the modern god of efficiency but you'd actually be aiming for a greater good. The article talks about Trolley Car Problems a bit and how people relate to algorithms "solving" these. The thing is instead of saying "that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed."

pg_bot 8y ago
"that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed." Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes. Every decision comes at a cost, we don't have unlimited resources so we should reach for tools that attempt to maximize what we are willing to spend. If you believe that no one needs to sacrifice in order to solve society's problems, you are living in a fantasy.
- joe_the_user 8y ago
  Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes. Basic income is system that would approximately guarantee all people's basic needs are met yet there is certainly opposition to it.

est 8y ago

I am extremely interested how to solve routing problem with Excel. Can you share few links or articles?

yorak 8y ago
Bus routing is just a variant of the vehicle routing problem (VRP), which itself is a generalization of traveling salesman problem (TSP) but with multiple salespersons doing the traveling. There is an Excel sheet for solving such problems, and if one wishes to go further, the basic heuristic and metaheuristic algorithms are not that hard to implement either. http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-solver/ http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-sol... With these keywords you are welcome to fall into this rabbit hole as deep as you wish. I promise to greet you on my way up (currently finishing my PhD on the topic).
- est 8y ago
  Thanks!

yorak 8y ago

It is true that such problems /can/ be solved via mathematical linear programming (for those coming outside math circles, please note that the term programming here has nothing to do with coding) and this is how they are usually presented in academia. However, in practice, it is not something one would be advised to do. Usually, the complexities of the real world routing and scheduling make it impossible to solve these models of practical size. Therefore, numerous heuristic and metaheuristic algorithms have been proposed and are usually used in practical applications. These usually are sound familiar to those that have some experience with "old" AI: genetic algorithms, ant colony systems, simulated annealing, and even neural networks have been succesfully applied to provide "good enough" solutions to these problems.