6 ms·

An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

139 points by a_w 9y ago

deleted 9y ago
[deleted]
justifier 9y ago
I like how this tutorial takes the practicality a step further by suggesting and showing how to use a specific library to avoid having to try to solve the problem yourself But for an understanding of the problem space and a good place to start trying to answer this unsolved problem.. this is still my favorite integer programming explanation: > and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(i) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (ii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction(iii) on our understanding of 0-1 integer programming we can understand all of the other 21 (o) 1972: Richard Karp: Reducibility Among Combinatorial Problems : http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (i) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (ii) http://mat.gsia.cmu.edu/orclass/integer/node4.html http://mat.gsia.cmu.edu/orclass/integer/node4.html (iii) 1971: Stephen A. Cook: The Complexity of Theorem-Proving Procedures: http://4mhz.de/download.php?file=Cook1971_Letter.pdf http://4mhz.de/download.php?file=Cook1971_Letter.pdf
- R_haterade 9y ago
  +1 for Mike Trick. The man is one of the best ambassadors the OR community has right now.
obstinate 9y ago
Google has a very nice suite of optimization tools, including an integer programming solver and a constraint solver, for third party use. Docs here: https://developers.google.com/optimization/ https://developers.google.com/optimization/ I got a chance to use it at work lately and it really is magical how you input a problem description and it outputs a solution. The documentation is hit or miss in some cases. MPSolver is pretty well documented. The more powerful constraint solver . . . well, I have no idea how to use the SA or Tabu search features, and minimal confidence that I'm doing anything correctly, except that it seems to emit correct-ish answers.
- beagle3 9y ago
  SA and Tabu are both heuristic, so you're never going to get anything but correct-ish answers (definitely no guarantee of THE correct answer).
  - hartror 9y ago
    !correct-ish optimal-ish
  - obstinate 9y ago
    I think you mean that they will not necessarily find optimal solutions, at least when the problem size is large. I understand that. What I don't understand is how to verify that they're giving me anything better than local search. I also don't have the background to know what settings to use (initial temperature in the SA case or the similar setting for Tabu search) nor which heuristic better suits my problem.
    - _raoulcousins 9y ago
      I'm not familiar with Google's particular implementation of these, but with the right value of the parameters, they are equivalent to local search. You could test with these parameters and see if the solution changes. In the simplest implementation of Tabu Search, a maximum tabu list length of zero will never reject any candidates. A simple simulated annealing should become a naive local search if the probability of rejecting a candidate solution is zero. As far as which heuristic is better: I'd avoid premature optimization when solving optimization problems. Pick one, and if you're satisfied with the results, then go with it? Academics usually test their heuristics against benchmark problem instances with known optimal solutions (or if no optimal solution is known, best known upper bounds). That would be a bit more thorough.
taylodl 9y ago
When I think of constraint-based problems I think of Prolog. A web search revealed several Prolog solutions to the bus scheduling problem. These solutions were all easier to read and understand than the imperative solution presented in this article. I then got to wondering if anyone had solved this problem using miniKanren. If they have, I couldn't find it or no one has ever posted such a solution.
- zmonx 9y ago
  I second this. Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. There is also significant overlap between constraint programming and integer programming: Many tasks can be easily solved with both approaches or a combination of them, and sometimes one of them is more suitable. Several Prolog systems ship with great implementations of both approaches.
  - JadeNB 9y ago
    > Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. I believe that it can be well suited for such problems—that is, that it is possible to write good solutions to them [0]—but isn't someone diving in without much experience likely just to write solutions that are age-of-universe slow because of combinatorial explosion? [0] I don't know if it's available online anywhere, but Richard O'Keefe's "The craft of Prolog" (well worth reading for anyone interested in problem solving, programmer or not) has a gorgeous explanation of how to solve the problem "find a 9-digit number such that the `n`-digit initial [or maybe final?] segment is divisible by `n` for each `n` from 1 to 9", starting with the most naïve approach and progressing to a much more efficient one. It has a punchline that, for the benefit of anyone who hasn't read it, I won't spoil here.
    - zmonx 9y ago
      The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated as CLP. Constraints automatically prune those parts of the search space that do not contain solutions. This typically leads to extremely significant speedups over naively generating all possibilities. For example, integer constraints are available under the name "constraint logic programming over finite domains", abbreviated as CLP(FD), in all most widely used Prolog implementations. To solve combinatorial optimization tasks with Prolog, I recommend to start with CLP(FD). If necesseary, you can always combine it with other approaches, such as applying the simplex algorithm and also custom methods and heuristics. Please note that constraints have become widely available in Prolog systems only after the book you cite was published, and it does not mention these methods at all. With current systems, you can elegantly and efficiently solve the task using CLP(FD) constraints.
BenDaglish 9y ago
A well-written tutorial, but mildly annoying that it starts off with a basic off-by-one error; 9am to 9pm is 13 trips, not 12, so the total trip number is 52 (which indeed is the number of trips shown in the example, not 48 as stated just above).
- yorwba 9y ago
  I interpreted it as the bus starting at 9am and stopping at 9pm, making for 12 trips of one hour each. So the off-by-one error would be in the code generating the possible trips. In fact, the code as shown only produces 48 trips, instead of the 52 given. I had to actually run it to make sure the Python interpreter in my had wasn't buggy. No idea what code they actually ran to get that result.
Tarrosion 9y ago
I'm always glad to see articles about integer programming as it's an incredibly powerful tool which deserves to be more widely known. However, I'm not sure the example chosen was the right introductory problem. As illustrated, we don't get the certifiably optimal solution because the true optimal solution may involve one of the duties we didn't randomly generate. If we don't get the optimal solution, why not just use a heuristic? Yes, there's a brief allusion to column generation which can address this problem, but surely there's an introductory problem which can be solved without requiring the user to think about column generation or similar?
- contravariant 9y ago
  Yeah, having read it I can't help but feel that a simulated annealing approach might end up generating a better result. If only because the limiting factor for simulated annealing is how quickly you can generate random duties and check some objective function, and not how quickly you can solve some NP complete problem for a large number of variables. Of course having found a couple of good combinations of duties with simulated annealing there's nothing stopping you from trying the integer program on those (+ variations) to try and find a better version.

139 points by a_w 9y ago

deleted 9y ago

[deleted]

I like how this tutorial takes the practicality a step further by suggesting and showing how to use a specific library to avoid having to try to solve the problem yourself But for an understanding of the problem space and a good place to start trying to answer this unsolved problem.. this is still my favorite integer programming explanation: > and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(i) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (ii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction(iii) on our understanding of 0-1 integer programming we can understand all of the other 21 (o) 1972: Richard Karp: Reducibility Among Combinatorial Problems : http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (i) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (ii) http://mat.gsia.cmu.edu/orclass/integer/node4.html http://mat.gsia.cmu.edu/orclass/integer/node4.html (iii) 1971: Stephen A. Cook: The Complexity of Theorem-Proving Procedures: http://4mhz.de/download.php?file=Cook1971_Letter.pdf http://4mhz.de/download.php?file=Cook1971_Letter.pdf

R_haterade 9y ago
+1 for Mike Trick. The man is one of the best ambassadors the OR community has right now.

obstinate 9y ago

Google has a very nice suite of optimization tools, including an integer programming solver and a constraint solver, for third party use. Docs here: https://developers.google.com/optimization/ https://developers.google.com/optimization/ I got a chance to use it at work lately and it really is magical how you input a problem description and it outputs a solution. The documentation is hit or miss in some cases. MPSolver is pretty well documented. The more powerful constraint solver . . . well, I have no idea how to use the SA or Tabu search features, and minimal confidence that I'm doing anything correctly, except that it seems to emit correct-ish answers.

beagle3 9y ago
SA and Tabu are both heuristic, so you're never going to get anything but correct-ish answers (definitely no guarantee of THE correct answer).
- hartror 9y ago
  !correct-ish optimal-ish
- obstinate 9y ago
  I think you mean that they will not necessarily find optimal solutions, at least when the problem size is large. I understand that. What I don't understand is how to verify that they're giving me anything better than local search. I also don't have the background to know what settings to use (initial temperature in the SA case or the similar setting for Tabu search) nor which heuristic better suits my problem.
  - _raoulcousins 9y ago
    I'm not familiar with Google's particular implementation of these, but with the right value of the parameters, they are equivalent to local search. You could test with these parameters and see if the solution changes. In the simplest implementation of Tabu Search, a maximum tabu list length of zero will never reject any candidates. A simple simulated annealing should become a naive local search if the probability of rejecting a candidate solution is zero. As far as which heuristic is better: I'd avoid premature optimization when solving optimization problems. Pick one, and if you're satisfied with the results, then go with it? Academics usually test their heuristics against benchmark problem instances with known optimal solutions (or if no optimal solution is known, best known upper bounds). That would be a bit more thorough.

taylodl 9y ago

When I think of constraint-based problems I think of Prolog. A web search revealed several Prolog solutions to the bus scheduling problem. These solutions were all easier to read and understand than the imperative solution presented in this article. I then got to wondering if anyone had solved this problem using miniKanren. If they have, I couldn't find it or no one has ever posted such a solution.

zmonx 9y ago
I second this. Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. There is also significant overlap between constraint programming and integer programming: Many tasks can be easily solved with both approaches or a combination of them, and sometimes one of them is more suitable. Several Prolog systems ship with great implementations of both approaches.
- JadeNB 9y ago
  > Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. I believe that it can be well suited for such problems—that is, that it is possible to write good solutions to them [0]—but isn't someone diving in without much experience likely just to write solutions that are age-of-universe slow because of combinatorial explosion? [0] I don't know if it's available online anywhere, but Richard O'Keefe's "The craft of Prolog" (well worth reading for anyone interested in problem solving, programmer or not) has a gorgeous explanation of how to solve the problem "find a 9-digit number such that the `n`-digit initial [or maybe final?] segment is divisible by `n` for each `n` from 1 to 9", starting with the most naïve approach and progressing to a much more efficient one. It has a punchline that, for the benefit of anyone who hasn't read it, I won't spoil here.
  - zmonx 9y ago
    The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated as CLP. Constraints automatically prune those parts of the search space that do not contain solutions. This typically leads to extremely significant speedups over naively generating all possibilities. For example, integer constraints are available under the name "constraint logic programming over finite domains", abbreviated as CLP(FD), in all most widely used Prolog implementations. To solve combinatorial optimization tasks with Prolog, I recommend to start with CLP(FD). If necesseary, you can always combine it with other approaches, such as applying the simplex algorithm and also custom methods and heuristics. Please note that constraints have become widely available in Prolog systems only after the book you cite was published, and it does not mention these methods at all. With current systems, you can elegantly and efficiently solve the task using CLP(FD) constraints.

BenDaglish 9y ago

A well-written tutorial, but mildly annoying that it starts off with a basic off-by-one error; 9am to 9pm is 13 trips, not 12, so the total trip number is 52 (which indeed is the number of trips shown in the example, not 48 as stated just above).

yorwba 9y ago
I interpreted it as the bus starting at 9am and stopping at 9pm, making for 12 trips of one hour each. So the off-by-one error would be in the code generating the possible trips. In fact, the code as shown only produces 48 trips, instead of the 52 given. I had to actually run it to make sure the Python interpreter in my had wasn't buggy. No idea what code they actually ran to get that result.

Tarrosion 9y ago

I'm always glad to see articles about integer programming as it's an incredibly powerful tool which deserves to be more widely known. However, I'm not sure the example chosen was the right introductory problem. As illustrated, we don't get the certifiably optimal solution because the true optimal solution may involve one of the duties we didn't randomly generate. If we don't get the optimal solution, why not just use a heuristic? Yes, there's a brief allusion to column generation which can address this problem, but surely there's an introductory problem which can be solved without requiring the user to think about column generation or similar?

contravariant 9y ago
Yeah, having read it I can't help but feel that a simulated annealing approach might end up generating a better result. If only because the limiting factor for simulated annealing is how quickly you can generate random duties and check some objective function, and not how quickly you can solve some NP complete problem for a large number of variables. Of course having found a couple of good combinations of duties with simulated annealing there's nothing stopping you from trying the integer program on those (+ variations) to try and find a better version.