5 ms·

Might be interesting to use logic programming (for example Prolog) or some rule engine to deal with these. Put in the requirements and then ask what options are

Might be interesting to use logic programming (for example Prolog) or some rule engine to deal with these. Put in the requirements and then ask what options are available. For example Prolog can do this via backtracking. I was once doing research for an optimization task and found out the related term is "integer programming". Compared to linear optimization the difference is that you have integer constraints. Like the plane either flies or it does not, you can't use 0.9 of this plane and 0.1 of the other. It was also revealing to find out the problem is NP-complete, so there's no easy solution or some magical algorithm. In your case, the proper thing might be mixed-integer programming. Setting some constraints as integers (you need to have 2 pilots, they need to be the same for the whole flights) and others like travel speed as linear. I was checking these years ago and at least back then there was not too many open source packages for this kind of optimization. Various commercial packages did exist.

wenc 8y ago
There is a bit of an art to formulating a correct and efficient mixed integer program (MIP) of non-trivial size, and in my experience, it's not something that can be picked up easily. It's easy to formulate toy problems (most of us use this guide [1]), but formulating large complex problems efficiently requires quite a bit of know-how and years of study (e.g. convex hull relaxations, custom cuts, heuristics, decomposition, leveraging randomness, etc.) This kind of thing lie in the domain of specialists (operations research folks) rather than software developers. The performance of commercial solvers (Gurobi, CPLEX, Xpress) has improved a lot and many are used in things like airline crew scheduling. The best open-source MIP solver is currently CBC (SCIP is better but only free for non-commercial use), but commercial solvers beat these by a mile. Even so large-scale MIPs are still complex beasts. It's worth noting that if the problem doesn't require any optimization (merely constraint satisfaction), MIPs might be overkill. A rules engine would probably be easier to implement and maintain. Even SQL (which is set theory in disguise) will often get you most of the way there. And if optimization was needed, a greedy algorithm would probably work most of the time. There are many successful commercial applications of MIPs but typically they are in circumscribed areas. MIPs are best deployed when there is a definite need for an optimal result, and when there is expertise available to maintain the resulting complex models. (Note: even ITA software in the linked article didn't attempt to model the problem as an MIP) [1] https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf
- tonyarkles 8y ago
  Interesting historical note: Google bought ITA in 2010.
  - wenc 8y ago
    Right. ITA's flight search tool was best-of-class in its time (and still is). Their competition at the time were Amadeus and Sabre which were written in assembly and ran on old-school mainframes. ITA's founders were MIT AI Lab alum so they wrote the first version of their software in Lisp. [1] ITA's code now powers Google Flights. [1] http://www.paulgraham.com/carl.html http://www.paulgraham.com/carl.html
dmichulke 8y ago
Hi, thanks for your response. I did a few years of work for my PhD thesis in Prolog but since then I'm a little disenchanted. A small overview as to why can be seen here: http://programming-puzzler.blogspot.com/2013/03/logic-programming-is-overrated.html http://programming-puzzler.blogspot.com/2013/03/logic-progra... I'm also trying to put as much logic as possible into SQL (because it's declarative and can easily be reordered) but eventually you have too many conditionals to handle it in SQL, especially when high level parameters are involved that change whole queries and you'd have therefore conditional subqueries that can't easily be joined (e.g., flight paths, like ADA, ABDA, ABDBA, ZADAZ) where A/D is source/destination of the passenger.

wenc 8y ago

There is a bit of an art to formulating a correct and efficient mixed integer program (MIP) of non-trivial size, and in my experience, it's not something that can be picked up easily. It's easy to formulate toy problems (most of us use this guide [1]), but formulating large complex problems efficiently requires quite a bit of know-how and years of study (e.g. convex hull relaxations, custom cuts, heuristics, decomposition, leveraging randomness, etc.) This kind of thing lie in the domain of specialists (operations research folks) rather than software developers. The performance of commercial solvers (Gurobi, CPLEX, Xpress) has improved a lot and many are used in things like airline crew scheduling. The best open-source MIP solver is currently CBC (SCIP is better but only free for non-commercial use), but commercial solvers beat these by a mile. Even so large-scale MIPs are still complex beasts. It's worth noting that if the problem doesn't require any optimization (merely constraint satisfaction), MIPs might be overkill. A rules engine would probably be easier to implement and maintain. Even SQL (which is set theory in disguise) will often get you most of the way there. And if optimization was needed, a greedy algorithm would probably work most of the time. There are many successful commercial applications of MIPs but typically they are in circumscribed areas. MIPs are best deployed when there is a definite need for an optimal result, and when there is expertise available to maintain the resulting complex models. (Note: even ITA software in the linked article didn't attempt to model the problem as an MIP) [1] https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf

tonyarkles 8y ago
Interesting historical note: Google bought ITA in 2010.
- wenc 8y ago
  Right. ITA's flight search tool was best-of-class in its time (and still is). Their competition at the time were Amadeus and Sabre which were written in assembly and ran on old-school mainframes. ITA's founders were MIT AI Lab alum so they wrote the first version of their software in Lisp. [1] ITA's code now powers Google Flights. [1] http://www.paulgraham.com/carl.html http://www.paulgraham.com/carl.html

dmichulke 8y ago

Hi, thanks for your response. I did a few years of work for my PhD thesis in Prolog but since then I'm a little disenchanted. A small overview as to why can be seen here: http://programming-puzzler.blogspot.com/2013/03/logic-programming-is-overrated.html http://programming-puzzler.blogspot.com/2013/03/logic-progra... I'm also trying to put as much logic as possible into SQL (because it's declarative and can easily be reordered) but eventually you have too many conditionals to handle it in SQL, especially when high level parameters are involved that change whole queries and you'd have therefore conditional subqueries that can't easily be joined (e.g., flight paths, like ADA, ABDA, ABDBA, ZADAZ) where A/D is source/destination of the passenger.