Explainable Linear Programs
21 comments
·February 7, 2025firesteelrain
t_mann
Fyi, it's quite common to have a paper rejected on the first (couple of) submission(s). With feedback along the lines of "not interesting enough", it's usually worth it trying it again somewhere else. Sounds like that venue was looking for methodological innovation within optimization, you could try it at a more domain-oriented outlet that would appreciate how your solution improves upon the SOTA for cloud resource selection.
What I'm also saying: just because you had a paper rejected once with a specific comment doesn't mean that every other paper where such a comment could vaguely fit needs to be rejected as well.
whatever1
Probably you need to submit to a different journal. It is not indeed a theoretically interesting contribution but it is definitely a very interesting practical application. Many journals would welcome your contribution.
moussore
No offense to the author, but there's a wealth of research (and tools) out there on this subject - robust optimization, stable theory, etc. (not requiring LLMs and ML buzzwords)
sevensor
> it’s basically not publishable as research
I was surprised he said this, since it sounds like he’s doing sensitivity analysis, which has been a thing for longer than I’ve been alive.
j2kun
IMO it's not sensitivity analysis in the classical sense because the explanations people are looking for are not about slight perturbations of the model, but usually more drastic ones. I found that, for example, the dual of an ILP is completely useless for explanation purposes. Stuff like "shadow prices" are just not relevant for complex formulations that model supply chain dynamics.
If there is useful theory here, I'd love to hear about it, but it's not in any textbooks I've read.
taeric
Hard not to feel that most of this research has been lost on the modern practitioner? I'd wager even money that a sizeable portion of new entrants to programming are not even aware of optimization techniques. Never mind if they are familiar with them.
Nor is this limited to optimization techniques. State machines are surprisingly ignored by many.
Makes me think this would be a fun post. What are the techniques that are basically ignored by most current discourse?
NBJack
Please share; I'm super interested in ways I can apply these concepts to a related work, and I have already heard from at least individual whom believes MIP explainability is 'impossible'.
j2kun
Could you give some examples of tools that people use to automate explanation of linear programs?
rahulnair23
Pointers to said tools would be beneficial. Robust optimization is somewhat different from what the author states.
damnitbuilds
Article entitled "Explainable Linear Programs" doesn't explain a linear program, nor link to an explained linear program.
nerdponx
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
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
Simulated Annealing: https://www.youtube.com/watch?v=21EDdFVMz8I
Genetic Algorithms: https://www.youtube.com/watch?v=Jm4qGteDlZE
Ant Colony Optimization: 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
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
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.
tsumnia
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.
whatever1
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.
null
mjburgess
It seems more of an internal note to a research community about what should be published/researched, rather than anything informative.
I wrote a research paper on a novel use (or so I thought) of Linear Programming for how to optimize selection of cloud resources. The feedback I received was that application of LP in a newish area is not publishable and does not cover new ground. So don't write research papers about a new application of LP. It still covers the known and common cases of LP. No new ground to cover here.
Knowing that and thinking about it more a couple years later, what the author seems to be describing is akin to BDD approach to LP model generation as an intermediary language before you get to the actual LP model. In this case, that approach is overshadowed by the use of LLMs.
Use of LLMs to generate English language is no longer novel nor new. Therefore, any application of LLMs that do that aren't novel either.