3 ms·

Article entitled "Explainable Linear Programs" doesn't explain a linear program, nor link to an explained linear program.

mjburgess 2y ago
It seems more of an internal note to a research community about what should be published/researched, rather than anything informative.
nerdponx 2y ago
2nd paragraph: > A linear program is a mathematical model that defines some number of variables, linear constraints, and a linear objective function. When some variables are forced to be integer (ILPs), you can solve a lot of useful problems like scheduling, routing, and packing. That’s basically how all supply chain optimization works. The author clearly expects the audience to know what an "objective function" is (it's something that you want to optimize, e.g. minimizing fuel on a delivery route). Furthermore: > Fast forward to today, when my colleague pointed me to this 2023 paper by Microsoft researchers Beibin Li, Konstantina Mellou, Bo Zhang, Jeevan Pathuri, and Ishai Menache, “Large Language Models for Supply Chain Optimization”. They basically did the same thing as me, but added an LLM to convert natural language queries to their structured query language. The colleague who pointed me to this was working on a similar idea. The author isn't showing examples of their idea, because another group did the same thing but arguably better, so they linked to that paper instead.
tsumnia 2y ago
Shamelessly Plugging my own videos on Linear Programs and Meta-heuristic Algorithms to solve Linear Assignment Problems. The Linear Assignment Problem: https://www.youtube.com/watch?v=dMJpCnocmGk https://www.youtube.com/watch?v=dMJpCnocmGk Simulated Annealing: https://www.youtube.com/watch?v=21EDdFVMz8I https://www.youtube.com/watch?v=21EDdFVMz8I Genetic Algorithms: https://www.youtube.com/watch?v=Jm4qGteDlZE https://www.youtube.com/watch?v=Jm4qGteDlZE Ant Colony Optimization: https://www.youtube.com/watch?v=Jm4qGteDlZE https://www.youtube.com/watch?v=Jm4qGteDlZE Whenever I find some mythical free time I'd like to add a video about Constraint Satisfaction, but in the mean time here's my full lecture on CSP: https://www.youtube.com/watch?v=w5tPsbOvkmU https://www.youtube.com/watch?v=w5tPsbOvkmU When we think about Explainable AI, we're looking for a "reason the AI made a decision". LLMs are using text prediction to make their decisions, but more traditional AIs use a different heuristic for their selection process. Many of these methodologies are still in use today and get the job done quite well. The "explanation" for these AIs is a (hopefully) intuitive method inspired by other natural phenomena that occurs in the world (like evolution, blacksmithing, literally how ants move). If however you're looking for AI to explain the "why" element, I will admit that is where the traditional algorithms struggle, but I would add that LLMs aren't much more informative. Its reflection is going to be by guessing what the next right word to say is, which isn't any better or worse than the other models in terms of explainability.
- te 2y ago
  Watched your Linear Assignment video, and the whole time I'm thinking why would one ever contemplate a meta-heuristic for Linear Assignment when Hungarian/Munkres runs in polynomial time? I think I must be missing some context.
  - whatever1 2y ago
    Because you can also have additional restrictions (for example cumulative capacities) in which case the Hungarian method is not valid anymore. In real life you rarely encounter the vanilla book version of a problem. Algorithmic approaches tend to break completely if your problem does not follow the exact assumptions. Model based approaches are more flexible. You just add more variables and constraints, and you use the same solver.
  - tsumnia 2y ago
    I talk briefly about this in my video on Heuristic Functions (I won't link just to stop shameless plugging), but its a combination of funding, knowledge, and team. Scheduling problems are a specific type of Optimization problem and many of those problems are NP-hard to exponential in complexity. For example a 25x25 Linear Assignment Problem has 25! potentially configurations, which would take longer than the heat death of the universe to find the global maxima. It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible. I'm not super familiar with Hungarian/Munkres but a quick GPT conversation points out that its O(n^3) isn't really good for those types of large problem sizes. Even if 25! isn't bad, I can always increase my N. Again, how do you decide if Hungarian is better than Simulated? You find a bunch of problems that both can do and test the algorithms against them. If you get decent enough results, I'm sure there's a science journal out there that would also publish the results.
    - te 2y ago
      > which would take longer than the heat death of the universe to find the global maxima Sure, if you're using brute force, instead of a polynomial time algorithm. > It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible. Hard disagree: https://en.wikipedia.org/wiki/Hungarian_algorithm https://en.wikipedia.org/wiki/Hungarian_algorithm Linear Assignment seems a very strange choice to illustrate the utility of meta-heuristics, when that particular problem has a polynomial-time solution algorithm that has been known for 70 years.
deleted 2y ago
[deleted]

mjburgess 2y ago

It seems more of an internal note to a research community about what should be published/researched, rather than anything informative.

nerdponx 2y ago

2nd paragraph: > A linear program is a mathematical model that defines some number of variables, linear constraints, and a linear objective function. When some variables are forced to be integer (ILPs), you can solve a lot of useful problems like scheduling, routing, and packing. That’s basically how all supply chain optimization works. The author clearly expects the audience to know what an "objective function" is (it's something that you want to optimize, e.g. minimizing fuel on a delivery route). Furthermore: > Fast forward to today, when my colleague pointed me to this 2023 paper by Microsoft researchers Beibin Li, Konstantina Mellou, Bo Zhang, Jeevan Pathuri, and Ishai Menache, “Large Language Models for Supply Chain Optimization”. They basically did the same thing as me, but added an LLM to convert natural language queries to their structured query language. The colleague who pointed me to this was working on a similar idea. The author isn't showing examples of their idea, because another group did the same thing but arguably better, so they linked to that paper instead.

tsumnia 2y ago

Shamelessly Plugging my own videos on Linear Programs and Meta-heuristic Algorithms to solve Linear Assignment Problems. The Linear Assignment Problem: https://www.youtube.com/watch?v=dMJpCnocmGk https://www.youtube.com/watch?v=dMJpCnocmGk Simulated Annealing: https://www.youtube.com/watch?v=21EDdFVMz8I https://www.youtube.com/watch?v=21EDdFVMz8I Genetic Algorithms: https://www.youtube.com/watch?v=Jm4qGteDlZE https://www.youtube.com/watch?v=Jm4qGteDlZE Ant Colony Optimization: https://www.youtube.com/watch?v=Jm4qGteDlZE https://www.youtube.com/watch?v=Jm4qGteDlZE Whenever I find some mythical free time I'd like to add a video about Constraint Satisfaction, but in the mean time here's my full lecture on CSP: https://www.youtube.com/watch?v=w5tPsbOvkmU https://www.youtube.com/watch?v=w5tPsbOvkmU When we think about Explainable AI, we're looking for a "reason the AI made a decision". LLMs are using text prediction to make their decisions, but more traditional AIs use a different heuristic for their selection process. Many of these methodologies are still in use today and get the job done quite well. The "explanation" for these AIs is a (hopefully) intuitive method inspired by other natural phenomena that occurs in the world (like evolution, blacksmithing, literally how ants move). If however you're looking for AI to explain the "why" element, I will admit that is where the traditional algorithms struggle, but I would add that LLMs aren't much more informative. Its reflection is going to be by guessing what the next right word to say is, which isn't any better or worse than the other models in terms of explainability.

te 2y ago
Watched your Linear Assignment video, and the whole time I'm thinking why would one ever contemplate a meta-heuristic for Linear Assignment when Hungarian/Munkres runs in polynomial time? I think I must be missing some context.
- whatever1 2y ago
  Because you can also have additional restrictions (for example cumulative capacities) in which case the Hungarian method is not valid anymore. In real life you rarely encounter the vanilla book version of a problem. Algorithmic approaches tend to break completely if your problem does not follow the exact assumptions. Model based approaches are more flexible. You just add more variables and constraints, and you use the same solver.
- tsumnia 2y ago
  I talk briefly about this in my video on Heuristic Functions (I won't link just to stop shameless plugging), but its a combination of funding, knowledge, and team. Scheduling problems are a specific type of Optimization problem and many of those problems are NP-hard to exponential in complexity. For example a 25x25 Linear Assignment Problem has 25! potentially configurations, which would take longer than the heat death of the universe to find the global maxima. It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible. I'm not super familiar with Hungarian/Munkres but a quick GPT conversation points out that its O(n^3) isn't really good for those types of large problem sizes. Even if 25! isn't bad, I can always increase my N. Again, how do you decide if Hungarian is better than Simulated? You find a bunch of problems that both can do and test the algorithms against them. If you get decent enough results, I'm sure there's a science journal out there that would also publish the results.
  - te 2y ago
    > which would take longer than the heat death of the universe to find the global maxima Sure, if you're using brute force, instead of a polynomial time algorithm. > It doesn't matter what algorithm you use, finding the absolute best solution and proving it is impossible. Hard disagree: https://en.wikipedia.org/wiki/Hungarian_algorithm https://en.wikipedia.org/wiki/Hungarian_algorithm Linear Assignment seems a very strange choice to illustrate the utility of meta-heuristics, when that particular problem has a polynomial-time solution algorithm that has been known for 70 years.

deleted 2y ago

[deleted]