Mixed Integer Programming (MIP) is the backbone of many optimization engines powering decision-making processes in modern industry. From logistics and finance to energy and beyond, MIP solvers like FICO Xpress have become indispensable tools for tackling real-world decision problems at scale. For decades, progress in MIP research has focused on pushing the boundaries of what’s theoretically possible—proving optimality, closing duality gaps, and tightening relaxations. While the key feature of MIP is the ability to deliver proofs of optimality, in many cases, users are equally or even more interested in MIP solvers’ ability to obtain high-quality, feasible solutions quickly.
That’s where primal heuristics come in. In our new book, Primal Heuristics in Integer Programming (Cambridge University Press, 2025), co-authored with my dear friends Andrea Lodi and Domenico Salvagnin, we set out to provide a unified overview of this crucial area: explaining not only what primal heuristics are and how they work, but also why they are so central to modern MIP solver development. All three of us have spent two decades each in academic and commercial research and development of MIP solving methods.
Why Primal Heuristics Matter
In the classic branch-and-bound framework, which underlies almost all MIP solvers, progress is measured on two fronts: improving the dual bound (how good can any solution possibly be, typically based on relaxations), and the primal bound (the value of the best feasible solution found so far). In the 20th century, research attention skewed heavily toward tightening the dual bound: better cuts, smarter branching, more sophisticated relaxations – natural, as this is arguably and theoretically justifiable as the more difficult part of the optimization process. As solver technology advanced and confronted more complex industrial problems, two things became evident: practitioners need good feasible solutions quickly—even in cases where proving optimality is out of reach—and, algorithmically, early high-quality solutions play an important role in accelerating branch-and-bound by pruning the search space more effectively.
Primal heuristics for general MIP address both these demands and have become a very active area of research in the past twenty years. Primal heuristics are fast methods embedded inside solvers, designed to find good feasible solutions as early as possible, guide the search process, and provide practical value even on instances that may never be solved to proven optimality.
As shown in our computational studies and those of others, disabling primal heuristics in state-of-the-art solvers like FICO Xpress or SCIP can dramatically slow progress toward good solutions and, in some cases, even make problems unsolvable in reasonable time.
What Exactly Are Primal Heuristics?
Primal heuristics are algorithms that focus on the primal side: producing feasible (though not necessarily optimal) solutions for a MIP. They complement the dual-focused strategies of classic branch-and-bound. Primal heuristics take many forms (see below), but always follow one of two basic goals: (i) find first feasible solutions as quickly as possible (start heuristics) or (ii) improve known feasible solutions further (improvement heuristics).
Modern solvers have developed a rich taxonomy of heuristics. Some require solving linear programs (LP-based), others work by logic and propagation alone (LP-free), and some go further to solve smaller, focused sub-MIPs to search large neighborhoods of a known solution. Each of these concepts comes with tradeoffs between speed, complexity, and solution quality. A crucial design principle throughout is the balance between diversification (exploring new regions of the solution space) and exploration (digging deeper into promising areas). Another practical lesson that I took from years of working with heuristics is the “fail fast” principle: “It’s okay to fail, as long as it happens fast”, i.e., save computational resources by quickly abandoning potential(!) dead ends.
Key Concepts to structure heuristics
In our book, we devote individual chapters and sections to classes of heuristics, roughly sorted by which concepts they predominantly use. Note, however, that many heuristics incorporate ideas from more than one of those basic concepts.
A modern MIP solver can call dozens of heuristics at various points: before or after node processing, after presolving, at the root, and so on. The challenge is to schedule these calls efficiently—not wasting time on expensive heuristics when fast ones suffice and dynamically adapting to the problem at hand. For us MIP developers, this is one of the biggest challenges: How can you add your shiny new heuristic idea to the big tool set that already exists in the code? Recent research even explores learning-based strategies for scheduling heuristics, creating a feedback loop between solver progress and heuristic deployment.
Trends and Innovations: ML and Nonlinear Problems
Speaking of learning, the book further devotes further chapters to two hot research topics:
Despite the centrality of primal heuristics in MIP practice, thus far, the field was fragmented with knowledge scattered across research papers, PhD theses, solver manuals, and conference talks. Our goal in writing Primal Heuristics in Integer Programming was to fill this gap: to offer a single, coherent resource that combines foundational concepts, detailed explanations of major heuristics, computational insights, and a perspective on where the field is heading. Synthesizing these works was in and of itself a learning opportunity for us and led us to rethink some of our own assumptions.
We have aimed to make the book accessible both as a reference for researchers and as a practical guide for anyone using MIP solvers in real-world applications – to those who are curious to know what happens “under the hood”. To support learning and self-assessment, each major chapter concludes with a set of quizzes.
Final Thoughts
Primal heuristics have transformed how integer programming is used in practice. They’re not just algorithmic “add-ons,” but essential ingredients in making solvers like FICO Xpress performant and highly usable in practice. As optimization problems grow in size and complexity, and as solver technology evolves, research on primal heuristics will remain a crucial topic.
Also, they have been my “first love” in academic research. I wrote my master’s thesis about primal heuristics twenty years ago and still find them fascinating. I hope that some of you will share that interest and find our book useful. If you are interested in learning more, diving into the algorithms, or understanding the practical realities of modern MIP, we invite you to explore Primal Heuristics in Integer Programming.
That’s where primal heuristics come in. In our new book, Primal Heuristics in Integer Programming (Cambridge University Press, 2025), co-authored with my dear friends Andrea Lodi and Domenico Salvagnin, we set out to provide a unified overview of this crucial area: explaining not only what primal heuristics are and how they work, but also why they are so central to modern MIP solver development. All three of us have spent two decades each in academic and commercial research and development of MIP solving methods.
Figure 1: MIP solvers often converge faster when primal heuristics are used
Why Primal Heuristics Matter
In the classic branch-and-bound framework, which underlies almost all MIP solvers, progress is measured on two fronts: improving the dual bound (how good can any solution possibly be, typically based on relaxations), and the primal bound (the value of the best feasible solution found so far). In the 20th century, research attention skewed heavily toward tightening the dual bound: better cuts, smarter branching, more sophisticated relaxations – natural, as this is arguably and theoretically justifiable as the more difficult part of the optimization process. As solver technology advanced and confronted more complex industrial problems, two things became evident: practitioners need good feasible solutions quickly—even in cases where proving optimality is out of reach—and, algorithmically, early high-quality solutions play an important role in accelerating branch-and-bound by pruning the search space more effectively.
Primal heuristics for general MIP address both these demands and have become a very active area of research in the past twenty years. Primal heuristics are fast methods embedded inside solvers, designed to find good feasible solutions as early as possible, guide the search process, and provide practical value even on instances that may never be solved to proven optimality.
As shown in our computational studies and those of others, disabling primal heuristics in state-of-the-art solvers like FICO Xpress or SCIP can dramatically slow progress toward good solutions and, in some cases, even make problems unsolvable in reasonable time.
What Exactly Are Primal Heuristics?
Primal heuristics are algorithms that focus on the primal side: producing feasible (though not necessarily optimal) solutions for a MIP. They complement the dual-focused strategies of classic branch-and-bound. Primal heuristics take many forms (see below), but always follow one of two basic goals: (i) find first feasible solutions as quickly as possible (start heuristics) or (ii) improve known feasible solutions further (improvement heuristics).
Modern solvers have developed a rich taxonomy of heuristics. Some require solving linear programs (LP-based), others work by logic and propagation alone (LP-free), and some go further to solve smaller, focused sub-MIPs to search large neighborhoods of a known solution. Each of these concepts comes with tradeoffs between speed, complexity, and solution quality. A crucial design principle throughout is the balance between diversification (exploring new regions of the solution space) and exploration (digging deeper into promising areas). Another practical lesson that I took from years of working with heuristics is the “fail fast” principle: “It’s okay to fail, as long as it happens fast”, i.e., save computational resources by quickly abandoning potential(!) dead ends.
Figure 2: The book visually illustrates many heuristic ideas, in more than twenty figures.
Key Concepts to structure heuristics
In our book, we devote individual chapters and sections to classes of heuristics, roughly sorted by which concepts they predominantly use. Note, however, that many heuristics incorporate ideas from more than one of those basic concepts.
- Rounding:
Starting from an LP relaxation, round fractional variables to integers (not necessarily the closest ones, though)—simple, but can quickly provide feasible solutions if done carefully. - Constraint Propagation:
Uses logical inference to update variable bounds and eliminate infeasible or-suboptimal assignments, using the structure of the constraints. - Large Neighborhood Search (LNS):
Rather than making tiny, incremental changes, LNS fixes large portions of a solution and allows the solver to re-optimize the rest. Some very important heuristics like Local Branching and RINS use this technique. - Diving:
Simulate a “dive” in the branch-and-bound tree, greedily fixing variables and re-solving relaxations to construct a solution. - Feasibility Pump:
One of the academically most influential heuristics, the feasibility pump, alternates between finding an LP solution and projecting back to the integer domain.
A modern MIP solver can call dozens of heuristics at various points: before or after node processing, after presolving, at the root, and so on. The challenge is to schedule these calls efficiently—not wasting time on expensive heuristics when fast ones suffice and dynamically adapting to the problem at hand. For us MIP developers, this is one of the biggest challenges: How can you add your shiny new heuristic idea to the big tool set that already exists in the code? Recent research even explores learning-based strategies for scheduling heuristics, creating a feedback loop between solver progress and heuristic deployment.
Figure 3: The book comes with an extensive computational study.
Trends and Innovations: ML and Nonlinear Problems
Speaking of learning, the book further devotes further chapters to two hot research topics:
- Machine Learning for Primal Heuristics:
Using data-driven approaches to guide which heuristics to apply, set parameters, or even design new heuristics. Early results are promising, and this intersection between ML and combinatorial optimization is a rapidly evolving area. - Primal heuristics for mixed integer nonlinear programming (MINLP):
Extending the principles and methods developed for MIP to broader classes of problems, where feasibility and optimality are even harder to attain.
Despite the centrality of primal heuristics in MIP practice, thus far, the field was fragmented with knowledge scattered across research papers, PhD theses, solver manuals, and conference talks. Our goal in writing Primal Heuristics in Integer Programming was to fill this gap: to offer a single, coherent resource that combines foundational concepts, detailed explanations of major heuristics, computational insights, and a perspective on where the field is heading. Synthesizing these works was in and of itself a learning opportunity for us and led us to rethink some of our own assumptions.
We have aimed to make the book accessible both as a reference for researchers and as a practical guide for anyone using MIP solvers in real-world applications – to those who are curious to know what happens “under the hood”. To support learning and self-assessment, each major chapter concludes with a set of quizzes.
Final Thoughts
Primal heuristics have transformed how integer programming is used in practice. They’re not just algorithmic “add-ons,” but essential ingredients in making solvers like FICO Xpress performant and highly usable in practice. As optimization problems grow in size and complexity, and as solver technology evolves, research on primal heuristics will remain a crucial topic.
Also, they have been my “first love” in academic research. I wrote my master’s thesis about primal heuristics twenty years ago and still find them fascinating. I hope that some of you will share that interest and find our book useful. If you are interested in learning more, diving into the algorithms, or understanding the practical realities of modern MIP, we invite you to explore Primal Heuristics in Integer Programming.
Updated 1 year ago
Version 3.0