Skip to Main Content

English

Developer Resources

About Us

Skip to Main Content

Blog

Recent Advances in the Use of Large Language Models to Solve Mixed-Integer Programming Models

The past few months have brought some exciting new developments in the use of LLMs to MIP models. Here, we'll share what we've learned, where the improvements are coming from, and what these developments could mean for the field of optimization.

Blog

Recent Advances in the Use of Large Language Models to Solve Mixed-Integer Programming Models

The past few months have brought some exciting new developments in the use of LLMs to MIP models. Here, we'll share what we've learned, where the improvements are coming from, and what these developments could mean for the field of optimization.

Blog

Recent Advances in the Use of Large Language Models to Solve Mixed-Integer Programming Models

The past few months have brought some exciting new developments in the use of LLMs to MIP models. Here, we'll share what we've learned, where the improvements are coming from, and what these developments could mean for the field of optimization.

Novel use of an LLM 

With LLMs now able to formulate entire optimization models starting from a textual description of the problem to be solved, it is only natural to wonder what role they are likely to play in solving these models.  

Recent work from the LLM4MIP project provides an interesting glimpse into the future, examining whether an LLM could be used in conjunction with a state-of-the-art MIP solver to accelerate the overall solution process. This research looked at both sides of the coin: using an LLM to improve the MIP primal bound (the best feasible solution), and using it to improve the dual bound (the bound on the best possible solution).  

Researchers had success with both: they improved dual bounds primarily through model reformulation and specialized cutting planes, and they improved primal bounds through improved heuristic techniques. They measured improvements using the MIPLIB 2017 test set, a set of 1,065 models that were collected to serve as a testbed for trying out new ideas for solving MIP models.  The set has two interesting subsets: a 240-model benchmark set which is used to track progress over time and compare performance among different solvers on tractable problems; and the open set, which serves as a challenge set of models that have never been solved to optimality. Much progress has been made in the eight years since MIPLIB 2017 was first released, with modern MIP solvers giving much better performance on the benchmark set and finding provably optimal solutions for many models that were considered open at the time the set was released. Out of the original 1,065 models in the set, 217 remain open.   

Over the years, the MIPLIB open model set has received a steady stream of user contributions of new best-known solutions. Improvements typically come from multiple sources: for example, a specialized heuristic may produce new best solutions for a few models from a particular class. In aggregate, the number of improvements over the years has been substantial. The recent LLM4MIP work was able to find new best-known solutions for 59 of these open models, which was an impressive number for a single new technology. 

At Gurobi, we have been exploring the implications of such an approach for several weeks, considering how LLMs might be integrated into a production MIP process. Using a similar scheme, we found better solutions than those reported by the LLM4MIP effort on over 50 open MIPLIB models, perhaps because we were using the latest version of Gurobi (version 14).  We have since submitted our results to MIPLIB. 

More recently, Anthropic announced that its Claude agents had reportedly found new best-known solutions for 72 open MIPLIB models, using teams of up to 300 agents. What do these results mean for our users? Let's take a look from a few different angles. 

Are these representative models? 

The first question we should address is how representative the MIPLIB 2017 open set is of the broad set of MIP models that people want to solve. The overall MIPLIB 2017 set was crafted with great care, with an eye toward capturing models from a wide range of use cases. However, we should keep in mind that the open set is made up entirely of models that have defied solution by MIP technology for at least 8 years. Progress on this set definitely represents a step towards expanding the set of problems that MIP can solve, but the set does not capture the vast array of problems that modern MIP solvers can already solve well. 

To put this in perspective, we tried using the LLM-guided approach that worked so well for the open set (described in more detail below) on the benchmark set instead, and it was more than three times slower than Gurobi’s default settings. We also allowed the LLM to craft a tuned strategy by studying the results of the first run (which allowed the LLM to overtune based on knowledge of past results), but that approach was still significantly slower than Gurobi’s default settings. Nevertheless, the LLM was able to find solutions faster on several models. Improving results on open models is definitely important, but we want to reiterate that the results won't necessarily carry over to more tractable models.  

What sort of computing resources are required to obtain a benefit? 

As we already noted, the recent Claude announcement indicated that they used "teams of up to 300 agents" to obtain their MIPLIB results. It wasn't clear from their announcement what impact this might have for people who don't have ready access to a swarm of 300 machines.  We've been trying to look at this work from a more pragmatic viewpoint: do these approaches allow you to solve MIP models faster when using more readily available computing resources (plus some help from a frontier LLM model)? 

To that end, one simple question we posed was the following: imagine you have a modest machine (in our case, an 8-core AMD EPYC 4364P system), a modest time budget (10,000 seconds in our case), and an LLM license (Claude Opus 5.5 in our case). Will you get better results for this test set from using Gurobi out of the box, or from asking the LLM to manage Gurobi?  

For the Gurobi (version 14) runs, we chose three different parameter settings: Default settings, MIPFocus=1 to focus on finding feasible solutions, and NoRelHeurTime=10000 to invoke a heuristic that often helps to find good solutions to very difficult models. We refer to the LLM-guided MIP solve as an 'LLM hyper-heuristic' below. We provided the LLM with a minimal prompt: basically, “use Gurobi to find good solutions to this MIP model.” We restricted our attention to the 173 open MIPLIB models that have seen some movement in their best solution values since 2020, to focus on models for which it is likely to be difficult but not impossible to find better solutions. Results are presented in this chart: 

 

 

The results are clear: using the LLM to guide the search for solutions on this set is much more effective than any of the three Gurobi parameter settings we used. 

Where are the improvements coming from? 

A natural question at this point is where these improvements are coming from. The first guess we typically hear is that the LLM is acting as a parameter tuning tool, matching each model to the Gurobi parameters that work well on that model. That has been the traditional approach to improving MIP performance on a specific class of models for decades. 

In fact, the LLM hyper-heuristic is doing very little of that. We asked the LLM to identify the most important techniques that it used, and the one that had the largest impact was customized Large Neighborhood Search (LNS), where neighborhoods were crafted by the LLM using knowledge it derived about the structure of the problem. Gurobi already makes heavy use of LNS, with RINS  being Gurobi's most effective and most often used heuristic. RINS uses MIP-specific information (relaxations) to craft effective neighborhoods. The LLM is going one step further, identifying and exploiting structure in the problem. For example, in a time-series network the LLM might construct a neighborhood where solution values in the current best solution are fixed for the first few timesteps, and later decisions are reoptimized by recursively calling the MIP solver. For several models, these custom neighborhoods are extremely effective. 

That's not the only approach that the LLM used. In some cases, it built custom heuristics (written in C), typically by identifying simple, cheap 'move' operators and performing a meta-heuristic search like simulated annealing or tabu search on top of these moves. In other cases, it performed substantial reformulations of the models and solved these transformed models using entirely different techniques (for example, some of the open models are pure SAT or CVRP problems). The main theme of these improvements was that they relied on the LLM identifying structure in the model, and our observation is that the structure that the LLM identified varied quite a bit from model to model. 

One thing we should add is that it is always difficult to point to one heuristic as the sole source of improvement in a MIP solution. Solutions from one heuristic often feed into the next heuristic, enabling it to find even better solutions. The LLM integrates solutions found by each of the techniques it tries into the overall MIP framework, thus reaping the benefits of applying a diverse set of strategies. 

How tuned are these results to this model set? 

Given that LLMs train on a vast universe of data, one question that must be asked is whether the LLM is doing well on these models because it is aware of references that talk about better ways to solve them. The MIPLIB open set has been around for a while, and many papers have used these models to test newly proposed techniques. 

To gauge this effect, we tried a test where we hid the origins of our 173 models. We ran each model through Gurobi 14 presolve, randomly permuted the rows and columns in the result, and removed variable, constraint, model, and file names, thus giving the LLM almost no information to use to trace the model back to its source. The chart below shows the number of times (after 10,000 seconds) the LLM found a better solution on the original MIPLIB model, the number of times it found a better solution on the obfuscated model, and the number of ties. 



While obfuscation clearly takes some wind out of the LLM's sails, this data provides strong evidence that the majority of the benefit is still there - the LLM is still able to identify and exploit model structure. 

What does this mean for you? 

These developments open up exciting possibilities for optimization practitioners, but how easily they can be applied depends on the use case. Experimenting with LLM-guided optimization on an individual model can be relatively straightforward. Integrating these approaches into production applications, however, introduces additional considerations. 

If you have a Gurobi license, a Claude license, and an MPS file, you can simply ask Claude Code to use Gurobi to try to solve the model. Prompting is a bit of an art form in LLMs, but as noted previously, we got good results by simply saying, "Use Gurobi to find good solutions to this model" (you should also provide a time limit). 

Bringing this approach into a production optimization application is more complex. It introduces considerations such as network connectivity, data security when sending your model and data to a third party, the non-determinism that is inherent in LLMs, the need to build an appropriate harness to pass your model to the LLM, etc. A local LLM could potentially address some of these issues, but our early tests indicate that local LLMs don't provide nearly the boost that a frontier model provides in our context. 

Another possibility is to ask the LLM to design and implement a custom method to capture and exploit the structure in your problem.  The LLM is happy to oblige, but the result may not be able to deal with the inevitable changes in the model over time. 

We are of course also looking at the lessons that can be learned from these results for improving the internals of the MIP solver itself. Some of these results have clear value that can be decoupled from the LLM, while others may require the full power of an LLM. 

The bottom line, though, is that these developments offer the potential to greatly expand the set of MIP models that can be solved. The history of MIP solvers is one of constant improvement, with new ideas coming from a number of directions.  It is great to have a major new source for such ideas. 

Start Solving with Gurobi

Try Gurobi on your own optimization models and see how it performs on real decision problems.

Start Solving with Gurobi

Try Gurobi on your own optimization models and see how it performs on real decision problems.

Start Solving with Gurobi

Try Gurobi on your own optimization models and see how it performs on real decision problems.

Join our newsletter to stay up to date on features releases and more.

By subscribing you agree to with our Privacy Policy

© Gurobi Optimization, LLC. All Rights Reserved.

Join our newsletter to stay up to date on features releases and more.

By subscribing you agree to with our Privacy Policy

© Gurobi Optimization, LLC. All Rights Reserved.