The AI Fundamentalists
A podcast about the fundamentals of safe and resilient modeling systems behind the AI that impacts our lives and our businesses.
The AI Fundamentalists
Linear programming: Building smarter AI agents from the fundamentals, part 3
We continue with our series about building agentic AI systems from the ground up and for desired accuracy. In this episode, we explore linear programming and optimization methods that enable reliable decision-making within constraints.
Show notes:
- Linear programming allows us to solve problems with multiple constraints, like finding optimal flights that meet budget requirements
- The Lagrange multiplier method helps find optimal solutions within constraints by reformulating utility functions
- Combinatorial optimization handles discrete choices like selecting specific flights rather than continuous variables
- Dynamic programming techniques break complex problems into manageable subproblems to find solutions efficiently
- Mixed integer programming combines continuous variables (like budget) with discrete choices (like flights)
- Neurosymbolic approaches potentially offer conversational interfaces with the reliability of mathematical solvers
- Unlike pattern-matching LLMs, mathematical optimization guarantees solutions that respect user constraints
Make sure you check out Part 1: Mechanism design and Part 2: Utility functions. In the next episode, we'll pull all of the components from these three episodes to demonstrate a complete travel agent AI implementation with code examples and governance considerations.
What we're reading:
- Burn Book - Kara Swisher, March 2025
- Signal and the Noise - Nate Silver, 2012
- Leadership in Turbulent Times - Doris Kearns Goodwin
What did you think? Let us know.
Do you have a question or a discussion topic for the AI Fundamentalists? Connect with them to comment on your favorite topics:
- LinkedIn - Episode summaries, shares of cited articles, and more.
- YouTube - Was it something that we said? Good. Share your favorite quotes.
- Visit our page - see past episodes and submit your feedback! It continues to inspire future episodes.
The AI Fundamentalists a podcast about the fundamentals of safe and resilient modeling systems behind the AI that impacts our lives and our businesses. Here are your hosts, andrew Clark and Sid Mungalik. Hello everybody, welcome to this episode of the AI Fundamentalists. Today we are continuing with our series on agentic AI and building it the right way. Today's topic is going to focus on linear programming, and, before we get into that, we've got some responses to the books we were reading last week when we introduced the episode. So I am going to ask this question again Sid what's on your desk? What are you reading?
Speaker 2:I have finally gotten back to rereading Signal in the Noise. I mean a very classic book in this optimization, thinking about the world in a very quantifiable way, and it's a little bit, you know, more boring on the second read, but I think it, like a lot of what's in there is still very interesting and thinking about, like how do we want to predict the real world in a very principled and mathematical way? So it's been fun to get back into there and think a little bit about that book. And you know we're all still fans of Nate Silver if he gets some predictions wrong.
Speaker 1:Yeah, for sure, Andrew. What are you into right now?
Speaker 3:Actually, I just finished a really good book called Leadership in Turbulent Times by Doris Keynes Goodwin. So it's essentially about four us presidents Abraham Lincoln, teddy Roosevelt, fdr and then I think, lyndon Johnston I think it was. Yeah, the author worked under him, so that's kind of how he got into that group. It's really good book about kind of like how how they grew up and kind of like some of the how did they become who they were in? The like the turbulent times they, they, they had their.
Speaker 3:Like Lincoln he had a really depressive episode at one point when he felt like he was failing at life and things like that early on. And then really how we got out of the funk was just reading and studying and things. That's kind of a common theme of every of the presidents kind of learned a different. But we hear this also, like anybody that follows finance and Warren Buffett and things, he's like I give up. He gives away what he does for free. Like you guys just got to read 500 plus pages a day. No one's going to do it, but that's how to get really successful. So it's just interesting with some of these books you keep seeing this trend over and over and over again of you know the be a leader, be a reader, type thing of like really understanding and getting in the nuts and bolts of how things work. And it kind of coincides well with this podcast and thanks for all listeners for taking this journey with us of like let's, let's crack open the textbooks we haven't touched in a long time and really start like learning the fundamentals of the different things, like that's.
Speaker 3:What just really struck me from this book of like Lincoln was, you know the. He was a before he became president and all the great stuff he did. It was a. It was just a small town lawyer that was just traveling around and doing things and he was staying up late at night reading Luke Lydian uh, you know, like the, the, the initial parts of a geometry book and stuff from from Euclid, like just random stuff, like that as just a small town lawyer. And then there's just like that, not the knowledge compounds and, just like this, the interdisciplinary thinking is where that magic happens. So just really enjoy that book and it's just no matter what, how you like your history or leadership or want to learn more about Lincoln and some of the great presidents, it's definitely a great book.
Speaker 1:Oh, awesome. Along similar lines, there's a cliche that we get frustrated with here. We know when we get really, really excited about the better ways to make models, and it's the old Facebook, the old Facebook poster that was on the wall in their offices when they first started move fast and break things, and how frustrating that is to think about what that did. So the book that I had been dying to read and I finally got to sit down with it this weekend was Burn Book by Kara Swisher, who, if anybody has followed tech at all in the past 20 years, you know her work, you know her writing through the Wall Street Journal and previously All Things D. She needs no promotion from us, but she brought up that quote in her book and it made me laugh.
Speaker 1:One think of this podcast and every time we get frustrated with that phrase. But I did feel it was. She felt it was important and I feel it's important to remind everybody that. There's important to remind everybody that there's a second part to that. They actually switched that poster at Facebook. Do you guys know what they changed it to in 2014?
Speaker 2:I don't what, what. What is it? What is it now?
Speaker 1:In 2014,. They actually ended up as they figured out that they needed a business strategy. They changed it to move fast with stable infrastructure which plus catchy I think that is memorable I know, yeah, see how things have to come back to some kind of normalcy when you actually have to try and have a business and make money.
Speaker 1:Well, you, know, but I thought but you know it, just that was probably probably about like a chapter or two into the book. That she brought that up again and, you know, made me think about, like, when we get frustrated with like, just everybody remembers the reckless part, but nobody remembers like, hey, and eventually even Facebook had to settle down and make a business, and it's time to stop breaking the things that work so that we can make more things on top of that, foundationally and fundamentally, which is what we're going to get into today. So, sid, what have we got?
Speaker 2:All right, what we're on to today is linear solvers. Before I do that, let's do a quick recap of utility functions, which is our last episode. It's going to queue up very nicely, I promise. So utility functions were a way for us to describe the wants and needs of an agent in a very quantifiable way. We do this by maximizing the quote-unquote utils that an agent generates, ie value for a customer.
Speaker 2:In the case of our travel agent, we needed utility functions so that we could model in an underspecified and undercontrolled environment, so that this agent could then operate in a real-world setting where things are not all cleanly laid out and people are not going to just tell you exactly the flight that they want. They're going to give you very wide sets of parameters and to zoom one one more level out uh, when we talk about mechanism design at the beginning and that's basically allowing all of these different agents to operate together over some higher system level utility function. So why does a travel agent need a linear solver then? Is that we can then solve the utility function. If the utility function tells us the combination of parameters and likes and dislikes that a customer has, a linear solver will actually let you find that optimal solution.
Speaker 3:Yeah, and this is where we're going to talk about some not all of just the plain so linear solvers, linear program, linear programming specifically, which we named the episode, is only one component of this larger field.
Speaker 3:But this is really like the mathematical optimization field and it's kind of it's not deterministic but it makes more. You understand the problem, you set up the problem a specific way and you're optimizing for a specific solution, versus the more machine learning approach where you're like learning the parameters and more making that prediction. So there's a lot of these methodologies that, like the, that have been around a long time, like linear programming, as an example came out of, I think, the 1940s and some of the supply and chain management things we've talked about that before. So we can get, we can start with like what is linear programming and and kind of how is it different from some of the loss optimizers or things you might be calling some of these prediction algorithms, and then get into some of the other related disciplines and kind of how they fit together, and then we can pull it back into the specifics of our agentic travel agent and then next episode we'll really dig into like putting the whole, all those pieces together.
Speaker 2:Absolutely, and so let's take for an example solving for a continuous variable with linear programming. This is a very canonical example and it's actually rather straightforward. You could think of this as the budget constraint for a user. The budget constraint for a user is not like a bin of money, it's not like exactly $10, exactly $50. It's a spectrum of money that they can specify that they want to put in and that they want to get a different itinerary for. One very powerful method of doing this is through the method of Lagrange multipliers. This is a technique for looking at a utility function, which is defined by a set of constraints, and finding local minima or maxima, meaning solutions that are maybe not the globally perfect solution, but at least solutions that will approximate an ideal solution, and over multiple iterations you can typically find either the global or an answer that's similar to the global maxima.
Speaker 3:What's really interesting about these solutions that's really helpful and, sid, you touched on it is the notion of constraint, and this is where it gets really interesting about these solutions. That's really helpful and, sid, you touched on it is the notion of constraint, and this is where it gets really interesting. And different than other types of some of these solvers you'll have like stochastic gradient descent and things like that in machine learning is all of the different constraints you have, like budget. This is where it works really well. Best flight, that hits my preference, that my utility, and there's we have those several different knobs of the that we'll talk we've talked through before of, like the shortest route, luxury basket, like those sorts of things we've talked about. Um, so there's those preferences, but I have a budget constraint. I also have to pay for a hotel and I might have air, uh, I might have a cab fare, like other things. So I have to have those different constraints. I might also only be able to fly on a Monday before my work schedule, so I have to make sure it lines up to Monday, so you can keep adding all of these little constraints. And this is where it's not really deterministic, because you're still doing that mathematical optimization with, hopefully, the global or maximum or minimum, but it may not be. But you're constraining the space to be what these specific parameters are.
Speaker 3:Now setting up the problem is more difficult, which is why I think these methods aren't used that often is because setting up what these constraints are can be difficult. But this is where you really will know and have it constrained in this whole like feature space down to what is the acceptable area based off of. You will not, when you set up this problem correctly, get a flight that is over your budget, like you can very much know. So, when you can control the space, it's in versus like a large language model, like you have no idea what's going to be happening there. What is it doing, is it? We don't personally think it's reasoning on this podcast, but whatever you think it's doing, calculating, it's harder to constrain and you don't know exactly what's going on there. Versus these you can constrain to this specific area based off of your hard coded parameters of. I can only spend $2,000 to go on this flight.
Speaker 2:That's exactly right and in that sense we can even think of the constraints as their own type of negative utility function which can also be solved. And that's the heart of the Lagrange method is that we take our constraints and we take the utilities that the customer actually wants and then we can have a total set of gradients, or IE, like slopes of curves, that we can follow down to get to reformulations of the original problem which are then tractable, solvable, into Lagrangian for those of us who have done a physics major. Building upon this, we had a Donsig Simplex method and I'll tell you the story of this before I tell you a little bit more about it. This was made by a scientist who was working for the Air Force during World War II and he mistakenly saw an unsolved math problem and believed it was a homework assignment. And he solved this homework assignment and we turned it into his professor. He said you know, you solved one of the great problems in mathematics. This could be your thesis and in fact it was his thesis. He turned in that old homework assignment, a little bit rewritten, and obtained his doctorate with it. This is also a similar method to the Lagrange multipliers, building up a little bit into a linear programming solver which utilizes these Lagrangian reformulations of the original task In order to solve some objective function.
Speaker 2:For us, our objective function is our utilities, and that brings us over to our next set of optimizations, which is considered combinatorial optimizations, and that's mostly what we're going to be interested with here. For our travel agent, this deals with the problem of we don't simply get to pick a flight for a budget and then we're done. That'd be incredibly easy. The combinatorial optimization piece of this problem is that we need to optimize for several items at the same time. It should be a short flight, it should be a cheap flight, it should lead to a good hotel and it should result in X amount of days of travel Right. So we have multiple choices to make, and any given choice we make will incur some quote unquote regret, right, that you know we did this, but we could have spent our money on this other option. And so our agent has to optimize for pairings of selected trip elements to forego certain exploratory spaces.
Speaker 3:And this is what we talked about last time some on podcast, when we was more of the microeconomics bent last time which is these are the consumer baskets. So also the way to distinguish between the like the linear programming example, and then the combinatorial field is that you're going from a continuous outcome, essentially so like the outcome is more continuous in linear programming, so you have the subject to certain constraints, but you could have any value between, like the constraint, anything above zero. For that I could spend on the flight less than 2000, or whatever that would be the amount you could have an output within a more continuous versus. This combination is more like I can. Only it's that there's the baskets.
Speaker 3:You have to choose one. You can't, you can't have this. This mixture of those so you have some of these more, gets into the field of more discrete optimization. You can't choose one and a half flights, right? So you have to choose one of the flights. And how do you weigh which of those flights to choose based off of your preferences as those quote, unquote baskets as a consumer?
Speaker 2:That's exactly right. And usually that broader class of problems is called the assignment problem right, where you make choice A, which means you can't make choice B as well. So you make one choice and you lock yourself at other choices. One very notable example of this, which maybe you've run into in a math class, is the knapsack problem, a very common dynamic programming problem in a CS course, which is this example like hey, you need to escape from your house and you have a single backpack. What goes in the backpack?
Speaker 2:And yes, this is like, obviously like a more sentimental question, but I guess if you have to be like purely mathematical about it, if you choose to take this book, you can't bring that laptop. If you take, you know, this precious heirloom, you have to leave behind this sentimental notebook. So it's the question of how do you optimize the value of items that you choose versus the amount of cost it takes to take on those items. So this is a surprisingly difficult problem to do purely efficiently to maximize the amount of space you put in. But this fits in really nicely with our assignment problem, where we want to minimize regret by getting as close to our threshold as we can.
Speaker 3:And this is a great one to illustrate as well why we're trying to do these solvers versus. You could just brute force this right, try every single combination of all items until you get something that works right, and then you actually have to do all items because you want to make sure you have the optimal one, even if you get two that work right. So that's where we're trying to find these methods of how do we solve this more efficiently than just brute force. This is where you get into, like the NP-hard and some of those concepts from computer science. It's like you don't want to have to just brute force all this. You want to have those more efficient methods, like the simplex one we talked about, but that was continuous. The math is a little easier when it's continuous versus when it's a discrete.
Speaker 2:That's right. And for those who don't know about, like the P equals NP problem, basically, this is described in algorithmic sciences that there's a certain class of problem that is difficult enough to do that the only way to get the correct answer every single time is to brute force it. There's no fancy and cute heuristic you can use to basically shortcut your way to an answer. That's more than a linear time speed up. For example, you may have heard of the traveling salesman.
Speaker 2:Or, more simply, you can think of this as like the shortest path problem right Between your home and the nearest hospital. If you need to make that trip, which roads can you take that will always get you there in the fastest time? This is a problem which requires quite a bit of thinking and a little bit of optimization to get to the fastest time. This is a problem which requires quite a bit of thinking and a little bit of optimization to get to the true answer. And while there are very good optimization algorithms out there that are very time efficient, space efficient, these types of shortest path problems often end up being these types of questions that agents have to solve, which is either brute forcing or having very strong heuristics for finding solutions which are valid.
Speaker 3:And this slight tangent but is related, of getting into the graph theory side, like the shortest route problem you just mentioned. It's really like if you think about roads as an example or on a graph. So a graph is just like those connected nodes and edges or vertices and then they connect. You can have different like weighted means. You have weights on these different edges between the nodes.
Speaker 3:You probably everyone sees, like the social network, you know how many distance you are from away, from how many friends you have, like if you have five friends here's how far distance are from other friends, like that kind of just some cool like network style graphs and things. Well, that's based off this graph theory where you have these different directed graphs, non-directed, weighted, with these edges where you're really trying to. You can impose, like roads and things like that, on those spaces and then find that shortest path route. That's an example of one of the type in graph theory, one of the ways we can do solving for that kind of a problem. One of the ways we can do solving for that kind of a problem.
Speaker 2:So we've kind of worked our way through how we usually think about more continuous problems and then combinational problems. Let's think about, then, how you solve discrete problems. Discrete problems are a little bit harder because you don't always have access to the same types of simple linear functions that you can just solve and find this maximum minimum point. You need to make a choice from a discrete set of choices, so we'll then consider this to instead be a linear programming, integer programming. When we're trying to solve these types of integer programming problems, we're going to use a class of solutions which come from dynamic programming.
Speaker 2:Dynamic programming, very, very broadly, is this idea that you can take very large problems, break them down into simpler subproblems and then solve those recursively.
Speaker 2:This is usually very efficient for space and for compute, because you no longer need to solve huge problems at scale. You can solve smaller and smaller and smaller problems until you basically break the problem down to a simple base case which has a known solution. A very common way that this is described is BNB, not Airbnb. This is a branch and bound where we take large optimization problems, break them into smaller sub-optimization problems and then bound off any solutions that definitely don't contain the optimal answer, and if we repeat the cycle multiple times, we'll at least end up on a set of valid optimal answers of a size that we're happy with, and we do this without having to do that much computational load. We can then evaluate these different options to make sure that they are like either equivalent to the end user, or search even further to get the exact right one. But these types of methods are very good for integer-based problems where we can't just quickly solve the utility function.
Speaker 3:And bringing that back as well to the kind of the economics and the utility spin is one of the ways.
Speaker 3:One of the algorithms you can use in dynamic programming is the Bellman equation, which is essentially taking it's cutting into these small problems one step at a time, from the end solution of how do you maximize utility reinforcement learning to kind of optimize as you go for a value function, even like Pavlovian style training, and actually back like AlphaGo and some of those or the early Watson thing.
Speaker 3:Some of them are based off of this Bellman equation, like reinforcement learning, where you're like penalizing or rewarding the system, its value function on these steps. But so you cut it into those recursive steps. But you actually even use this utility function style methodology all the way up, but working like here's the end state I'm trying to get to, and then you work it up that way, which is somewhat analogous to what we've been doing with the mechanism design and how we're going to tie the whole utility agent together, but a long, long way of saying like that's also in this type of a space. That used to be what the cutting edge AI was back in the day of using these types of recursive programming, but having still that allows that flexibility with the Bellman equation to have some of this utility maximization or minimization at each stage in the game.
Speaker 2:That's right, and that actually leads really nicely to another potential solution which you may find a lot of use for is well, if you keep telling me that continuous optimization is always easier than integer optimization, that continuous optimization is always easier than integer optimization, maybe in some cases I can remove and relax this integer constraint, solve this as a linear problem and then just go back and truncate back to an integer solution, right?
Speaker 2:So, for example, this might be like okay, well, I want to spend this amount of money on a hotel, but hotels don't come at every single price range. They come at fixed price ranges or fixed prices, and so you could solve this as a linear problem and then just simply just scooch over to the closest discrete answer. So there are ways to get around this sometimes, but for things which are more categorical and less obviously translatable, you may have to use some of these more advanced dynamic programming approaches. And that brings us to our final class of optimizations which we're going to be dealing with for our travel agent, which is mixed integer operation, which is that we have to both work with discrete outcomes and continuous outcomes. For example, our budget might be $550, which is a continuous number, but when it comes time to pick a flight, we only get to pick a single flight, so we have to make both discrete optimizations on continuous constraints and that becomes a tractable, possible but more complex problem, which is a really good fit for these types of agents.
Speaker 3:Also worth noting one of the original agents I like to call Google maps. So you're you're telling the agent where you want to go and how to get there, and it's actually built off of a mixed integer programming, and Google actually has some really great open source or operations research. That's the other thing worth mentioning. A lot of these methodologies came out of the operations research, which is the supply chain logistics field is where these came from. So Google actually has some great open source tools around. They don't get a lot of press around this doing these types of solvers, and Google Maps is an example of a mixed integer programming problem is an example of a mixed integer programming problem.
Speaker 1:What's starting to come to mind is there's a little bit of a friction between the accuracy and the found in the fundamentals. What we're introducing to build the models and get to accuracy and get to constraints, where does where do things like recommendation engines and models come in from that end? That might either help or disrupt this process, for in the model that you're building, because that's the user interface that you're ultimately getting to- yeah, so recommendation engines are that's a different type of like collaborative filtering.
Speaker 3:That's a whole type of another collaborative filtering that's. That's a whole type of of another field that we could have. This, some of these, you could use some of these algorithms for solving that problem as well. It just depends as like, uh, those are kind of preference based as well, like netflix recommending the next movie and things they have there. But, um, this is, I would argue that there's.
Speaker 3:So there's really two answers to it. Like if you do a well-designed user interface of how do you actually do it? So like if you look at what is the conversations you're having in like an agent type workflow. It's not, it's not like completely random. Let's ask chat gpt, anything right, it's going to be more set up. You can do standard language processing. If here's like the decision tree of the possible outcomes or oh, I didn't understand that, please, please explain. Or we need to have a social security number, or not that like your TSA number or whatever. So then you can do like regex of searching to make sure that you have the correct number of inputs. There's all these ways you can do it without having to have a chat interface.
Speaker 3:However, if you do want to have a chat interface, there's another thing you have out. There is like the neurosymbolic is something that's really a field people are talking about now. What essentially that means in lay speak is that means you use like a chat gbt at the front end or some sort of web interface to have the conversation, but then you you send it to a solver like what we're talking about because one of the key things like similar that apple paper that came out, we can link it, um, I forget what what it was called, but some fantastic article, uh paper that came out showing how, like um, the latest versions of some like anthropic clod and deep seek and things like that, they're not thinking, they're pattern matching. They even gave apple, even gave like code to tower of hanoi and things like that. These all these different problems and tried to see it broke down after a certain amount of uh of, of moves versus. You know it's a deterministic programming problem that's not actually that hard to solve. It's a python assignment for people learning the program, essentially, but it showing this pattern matching and not thinking through some of these things.
Speaker 3:But Apple even gave the LLM the prompt of how to do this kind of thing and also worth noting, they had it in an environment where they're using like the complex systems and like validations on the side. So it's like, well, if you're doing it that way, just do it that way instead of doing an LLM. But that's neither here nor there. But in any case you could have this.
Speaker 3:If you really want to have that chat interface which I'm arguing you don't you can have a chat interface without actually having an LLM, but say you do want to go that route, you could still have that information. You're going to have accuracy loss though for the flexibility of the chat interface versus having that more discrete type in your number, and we go, but you then send that information to a solver. That's a neurosymbolic link, and so you can solve it with this constraint based thing. So you're going to have actual calculations and not swagging, pattern matching. So that's where you could still have the best of both worlds and that's kind of an emerging field of research. But I would still argue good UI design kind of makes that not a problem. But I don't know if that's a long-winded way of answering it and I'm sure Sid has some thoughts as well.
Speaker 2:Yeah, I mean I'll quickly contrast these recommender systems with these types of agent models, just in the sense that we don't care if the recommender gets the right answer. In fact, that's one of the utilities of it is that, like, it can work in a very unsupervised manner where it's just going to give an answer which is probably successful, and success is measured through something like click through rate. But that's not that it's not to be a guaranteed outcome. It's not like, hey, we need to show them a movie that they will love and will be their new favorite movie, which is something that maybe an agent with an extremely amazing set of constraints could actually solve. That kind of problem extremely amazing set of constraints could actually solve that kind of problem.
Speaker 2:How do I show you a movie you will like versus a movie that you might like, which is a pattern matching problem, versus this, which is an actual optimization problem? And so, putting all this together, you know if we come to a conclusion, we would say that linear solvers allow us to find optimal solutions in a space which can contain several possible valid answers. They could even be combinatorial, they could be continuous or they could be discrete. Our travel agent that we've described in this entire project, then we would then describe as having a combinatorial mixed integer optimization problem, and our goal with our final episode in this series is to put all these things together, present it to you, share the design spec and even some code so you can go along and see exactly how this would actually work and then talk about what it would take to govern such a model and how you might contrast governing this type of subject matter expert build, mathematically optimized model versus governing an LLM based agent.
Speaker 3:It's going to be fun. This is a really fun episode, a group of episodes. We've got some work to finish up, that the wrap up and we'll be doing like a company blog posts and things. But this has been a really fun journey and I hope you guys have enjoyed it as well, and the next episode will be kind of really that culmination of it. We'll also be tying it back to that first episode we had around mechanism design, which is designing the rules of the game and kind of how all these things can fit together. So, um, really been enjoying this series and um, thanks for taking us through this one, sid yeah, thank you guys.
Speaker 1:If you have questions about anything that you've heard in these first three parts, please drop us a line. We're happy to answer those questions and we hope you're looking forward to us wrapping this up Until next time.
