Explainable Linear Programs(jeremykun.com)
jeremykun.com
Explainable Linear Programs
https://www.jeremykun.com/shortform/2025-02-06-2124/
34 comments
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.
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.
I had several comments. I posted below but here are some
This was my first and only research paper submission under my MS in Systems Engineering. It wasn’t a requirement but the department head was impressed that any Masters student might try to submit at all.
It was to IEEE. Maybe that was hard mode? It was for a Cloud Conference in 2023.
One of the comments
“ This paper shows a linear programming problem to address cloud security. It's not clear why the LP program addresses security. Comparison with SOTA is also lacking.”
“ The paper attempts a fresh perspective on Cloud Security Decisions using a well-known approach. Unfortunately, as currently presented, it does not deliver any significant research results, and thereby its contribution is limited. The paper as formulated is closer to a vision paper -- not that it actually is -- than to a research paper. This reviewer notes the limited results. No surprises, the paper is also missing an evaluation analysis of the results.”
I had evaluation of results. I had never heard of a vision paper.
This was one of the better comments that actually provide the best feedback. The section that they mention was exceptionally long was my literature review:
“ This paper describes the idea of leveraging linear programming to determine how to allocate security resources in the cloud.
It would be better if the paper focused more on describing the proposed solution. The current description in Sec III is insufficient. First, there are many assumptions that were made to explain and formulate the linear programming for security resource allocation. These assumptions need to be explained further, e.g., to provide information on parameterizing values such as the budget and weights. Second, it would be better if the paper describes the system models based on a current cloud service provider so that the discussion is more concrete.
The implementation section can be reduced significantly, e.g., the Sec V.B. can be condensed to only show important lines of code.
There is no evaluation of the proposed solution. It is hard to assess how well the proposed solution will work without evaluating the formulation based on existing cloud service providers. Additionally, it is important to choose some baselines to compare the proposed solution.
The related work section takes 2 out of the 6 pages and feels unnecessarily long. It might be sufficient to describe how prior work solves this problem and how this paper differs.
A final remark is about the problem formulation. It is unclear what the challenges of allocating security resources are and how those challenges differ from other cloud-based resource allocation problems.”
This was my first and only research paper submission under my MS in Systems Engineering. It wasn’t a requirement but the department head was impressed that any Masters student might try to submit at all.
It was to IEEE. Maybe that was hard mode? It was for a Cloud Conference in 2023.
One of the comments
“ This paper shows a linear programming problem to address cloud security. It's not clear why the LP program addresses security. Comparison with SOTA is also lacking.”
“ The paper attempts a fresh perspective on Cloud Security Decisions using a well-known approach. Unfortunately, as currently presented, it does not deliver any significant research results, and thereby its contribution is limited. The paper as formulated is closer to a vision paper -- not that it actually is -- than to a research paper. This reviewer notes the limited results. No surprises, the paper is also missing an evaluation analysis of the results.”
I had evaluation of results. I had never heard of a vision paper.
This was one of the better comments that actually provide the best feedback. The section that they mention was exceptionally long was my literature review:
“ This paper describes the idea of leveraging linear programming to determine how to allocate security resources in the cloud.
It would be better if the paper focused more on describing the proposed solution. The current description in Sec III is insufficient. First, there are many assumptions that were made to explain and formulate the linear programming for security resource allocation. These assumptions need to be explained further, e.g., to provide information on parameterizing values such as the budget and weights. Second, it would be better if the paper describes the system models based on a current cloud service provider so that the discussion is more concrete.
The implementation section can be reduced significantly, e.g., the Sec V.B. can be condensed to only show important lines of code.
There is no evaluation of the proposed solution. It is hard to assess how well the proposed solution will work without evaluating the formulation based on existing cloud service providers. Additionally, it is important to choose some baselines to compare the proposed solution.
The related work section takes 2 out of the 6 pages and feels unnecessarily long. It might be sufficient to describe how prior work solves this problem and how this paper differs.
A final remark is about the problem formulation. It is unclear what the challenges of allocating security resources are and how those challenges differ from other cloud-based resource allocation problems.”
It's hard giving feedback without having seen the paper. I think you need to ask yourself how much you'd value having a peer-reviewed publication and how much effort/frustration tolerance you want to conjure up for this.
Getting it accepted might entail multiple submissions and significant extra work on top of what you've already done. The value of the bragging rights might be limited on the non-academic job market. And getting it published is still a different thing from having impact. Up to you to decide.
Getting it accepted might entail multiple submissions and significant extra work on top of what you've already done. The value of the bragging rights might be limited on the non-academic job market. And getting it published is still a different thing from having impact. Up to you to decide.
Can I email you the paper?
The reason why application of LP in a newish area is not really publishable is because the field of Operations Research has been doing that continuously for the past 80 years. Modeling planning problems as mathematical optimization problems has been done long before computers were capable of solving them, and convex optimization problems in particular have the most historical work put into them, due to early innovations. Optimizing selections of cloud resources in particular is so ubiquitous that those exact types of problems tend to be used as tutorials to get people up to speed for various types of solvers.
Unfortunately we have a very bad branding problem, and almost nobody who hears the name "Operations Research" can infer what we actually do from the name, let alone understand the mountains of research that we've accumulated over time.
Unfortunately we have a very bad branding problem, and almost nobody who hears the name "Operations Research" can infer what we actually do from the name, let alone understand the mountains of research that we've accumulated over time.
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.
It was to IEEE. Maybe that was hard mode? It was for a Cloud Conference in 2023.
One of the comments
“ This paper shows a linear programming problem to address cloud security. It's not clear why the LP program addresses security. Comparison with SOTA is also lacking.”
“ The paper attempts a fresh perspective on Cloud Security Decisions using a well-known approach.
Unfortunately, as currently presented, it does not deliver any significant research results, and thereby its contribution is limited.
The paper as formulated is closer to a vision paper -- not that it actually is -- than to a research paper. This reviewer notes the limited results. No surprises, the paper is also missing an evaluation analysis of the results.”
I had evaluation of results. I had never heard of a vision paper.
One of the comments
“ This paper shows a linear programming problem to address cloud security. It's not clear why the LP program addresses security. Comparison with SOTA is also lacking.”
“ The paper attempts a fresh perspective on Cloud Security Decisions using a well-known approach.
Unfortunately, as currently presented, it does not deliver any significant research results, and thereby its contribution is limited.
The paper as formulated is closer to a vision paper -- not that it actually is -- than to a research paper. This reviewer notes the limited results. No surprises, the paper is also missing an evaluation analysis of the results.”
I had evaluation of results. I had never heard of a vision paper.
It is not trivial to publish to CLOUD. 3/4 of papers get rejected.
For better or worse, reviewers expect a specific structure in a paper. From the comments, it seems that you did not follow the typical structure of a research publication. Unfortunately, there are no clear guidelines; it just becomes natural with reading and writing papers. A mentor with academic experience would be a valuable resource in your case; you are probably 80% there.
For better or worse, reviewers expect a specific structure in a paper. From the comments, it seems that you did not follow the typical structure of a research publication. Unfortunately, there are no clear guidelines; it just becomes natural with reading and writing papers. A mentor with academic experience would be a valuable resource in your case; you are probably 80% there.
I didn’t really have much guidance and sort of winged it and that was my fault.
I graduated last May and do not have any advisors any longer. I could try to rework the paper myself and fix the problems with it which I may do now that I have more time.
I graduated last May and do not have any advisors any longer. I could try to rework the paper myself and fix the problems with it which I may do now that I have more time.
Article entitled "Explainable Linear Programs" doesn't explain a linear program, nor link to an explained linear program.
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.
> 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.
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.
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.
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.
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.
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.
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.
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.
> 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
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.
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
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.
I mostly use Linear Assignment because it was a simple problem that I could present to my students to serve as a foundation for learning about these algorithms and how they operate within a problem space. One aspect I believe helps in the learning process is to see an algorithm in action and to work through it at the base level.
The course is meant to serve as an intro to AI for students just coming out of a data structures course. Hungarian may be better for producing the optimal answer, I don't know I'd have to try it out. But I know that for my section on meta-heuristics Linear Assignment works as a great vehicle for demonstrating those algorithms.
The course is meant to serve as an intro to AI for students just coming out of a data structures course. Hungarian may be better for producing the optimal answer, I don't know I'd have to try it out. But I know that for my section on meta-heuristics Linear Assignment works as a great vehicle for demonstrating those algorithms.
Can you recommend some good books which explain "Mathematical Programming/Optimization" from the very beginning in a simple manner? Most books are notation heavy and seem to lack explanations for the beginning student. Long ago i was recommended N.S.Kambo's Mathematical Programming Techniques which covers a lot of ground but is very hard to understand.
The second question is, how (and where) are these techniques used in the ML/AI domain?
The second question is, how (and where) are these techniques used in the ML/AI domain?
I used Russell and Norvig's "Artificial Intelligence: A Modern Approach" as a starting point for the course's schedule and have modified it over the years to help align with things I think would continue my students have a broad overview of all of AI.
These techniques won't be as widely advertised not because they're inefficient but rather from a marketing perspective it is often easier to just say "AI". However what I would do if I needed to find use case examples would be to search for research articles on Google Scholar [1]. They haven't hooked up a GPT summarizer to Scholar so you'll have to read through everything, but the game is find papers that DID use the approach.
For example, [2] is a research paper looking at utilizing Simulated Annealing to schedule disaster relief teams.
[1] scholar.google.com
[2] https://link.springer.com/article/10.1007/s00500-021-06425-6
These techniques won't be as widely advertised not because they're inefficient but rather from a marketing perspective it is often easier to just say "AI". However what I would do if I needed to find use case examples would be to search for research articles on Google Scholar [1]. They haven't hooked up a GPT summarizer to Scholar so you'll have to read through everything, but the game is find papers that DID use the approach.
For example, [2] is a research paper looking at utilizing Simulated Annealing to schedule disaster relief teams.
[1] scholar.google.com
[2] https://link.springer.com/article/10.1007/s00500-021-06425-6
Thank You. I have the Russell & Norvig AIMA book though i have not looked at everything there; probably as you point out it would answer my second question. Any pointers to specific chapters/sections would be appreciated.
What i was specifically asking for was for some intuitive and explanatory books on Mathematical Optimization/Programming (https://en.wikipedia.org/wiki/Mathematical_optimization and https://en.wikipedia.org/wiki/Linear_programming) independent of AI/ML. This is of course a much older subject with a lot of breadth. However i have not been able to find a intuitive introduction to the subject. Everything has been symbol heavy but not much explanations on the intuitive and model building aspects which imo is crucial to understanding.
What i was specifically asking for was for some intuitive and explanatory books on Mathematical Optimization/Programming (https://en.wikipedia.org/wiki/Mathematical_optimization and https://en.wikipedia.org/wiki/Linear_programming) independent of AI/ML. This is of course a much older subject with a lot of breadth. However i have not been able to find a intuitive introduction to the subject. Everything has been symbol heavy but not much explanations on the intuitive and model building aspects which imo is crucial to understanding.
My Constraint Satisfaction lecture (https://www.youtube.com/watch?v=w5tPsbOvkmU) may help, though I will say it only serves as a light 75 minute overview of constraints. Specifically in the second half of the lecture I use girl scout cookies and scooters to try and explain Linear Programming.
A quick Googling pulled up a Linear Programming Using Excel tutorial: https://science.utm.my/procscimath/wp-content/uploads/sites/...
This type of problem was what helped me understand the optimizations. I haven't studied the inner workings of the Simplex method, but it is used in Excel's Solver as well as Apache Commons'.
While it is still computer science oriented, I also like Grokking Algorithms (https://www.manning.com/books/grokking-algorithms). I used it as a source when I was building out some examples when I was teaching Algorithmic analysis and data structures. It does a great job of distilling the problems into a beginner friendly way that will lead you to dig into "what libraries are out there that have implemented this?"
A quick Googling pulled up a Linear Programming Using Excel tutorial: https://science.utm.my/procscimath/wp-content/uploads/sites/...
This type of problem was what helped me understand the optimizations. I haven't studied the inner workings of the Simplex method, but it is used in Excel's Solver as well as Apache Commons'.
While it is still computer science oriented, I also like Grokking Algorithms (https://www.manning.com/books/grokking-algorithms). I used it as a source when I was building out some examples when I was teaching Algorithmic analysis and data structures. It does a great job of distilling the problems into a beginner friendly way that will lead you to dig into "what libraries are out there that have implemented this?"
It seems more of an internal note to a research community about what should be published/researched, rather than anything informative.
[deleted]
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)
> 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.
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.
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.
If there is useful theory here, I'd love to hear about it, but it's not in any textbooks I've read.
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'.
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?
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?
Could you give some examples of tools that people use to automate explanation of linear programs?
Pointers to said tools would be beneficial. Robust optimization is somewhat different from what the author states.
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.