[HN Gopher] Explainable Linear Programs
___________________________________________________________________
Explainable Linear Programs
Author : matt_d
Score : 69 points
Date : 2025-02-07 19:06 UTC (3 days ago)
(HTM) web link (www.jeremykun.com)
(TXT) w3m dump (www.jeremykun.com)
| damnitbuilds wrote:
| Article entitled "Explainable Linear Programs" doesn't explain a
| linear program, nor link to an explained linear program.
| mjburgess wrote:
| It seems more of an internal note to a research community about
| what should be published/researched, rather than anything
| informative.
| nerdponx wrote:
| 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 wrote:
| 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.
| firesteelrain wrote:
| 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.
| tptacek wrote:
| Got a draft of it?
| moussore wrote:
| 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 wrote:
| > 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 wrote:
| 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.
| j2kun wrote:
| Could you give some examples of tools that people use to
| automate explanation of linear programs?
| NBJack wrote:
| 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'.
| taeric wrote:
| 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?
| rahulnair23 wrote:
| Pointers to said tools would be beneficial. Robust optimization
| is somewhat different from what the author states.
___________________________________________________________________
(page generated 2025-02-10 23:00 UTC)