INFORMS Open Forum

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

Jonathon,

Thanks for sharing that. For problems that fit a paradigm (LP, MIP, QP, ...) for which good solvers are available, it makes perfect sense to try the solvers first and resort to heuristics as needed. I've seen more than a few people say, in various contexts, "the problem is NP-hard so we have to use a heuristic", rather than taking a shot at optimality using a solver. My sense is that they are mostly (all?) academics looking for a justification for their shiny new heuristic as opposed to industry folks with specific problems and looking for good solutions rather than publications.

Paul

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI

Original Message:
Sent: 06-20-2025 21:39
From: Jonathon Leverenz
Subject: Heuristics in practice

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

------------------------------
Jonathon Leverenz
Operations Research Analyst
Systems Planning and Analysis, Inc
Alexandria VA

Original Message:
Sent: 06-13-2025 15:48
From: Paul Rubin
Subject: Heuristics in practice

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI
------------------------------

Hi Paul and Jonathon,

for someone like me that has spent a significant amount of time in designing primal heuristics to be included in mixed-integer programming (MIP) solvers, this is a very interesting and useful thread, thanks!

My take is that the exercise of modeling the problem and giving it to a solver is useful to get a sense of its practical difficulty, besides its NP-hardness, and in addition any good MIP solver is now very well equipped to produce good feasible solutions, which -- in turns -- connects with Paul's argument on the need for optimality in practice.

Together with Timo Berthold and Domenico Salvagnin, we recently published a book "Primal Heuristics in Integer Programming" whose goal is indeed to highlight MIP solvers' ability to produce high-quality feasible solutions. The book presents in a principled way the algorithmic ideas at the core of the arsenal of primal heuristics in today's MIP solvers.

Hope this is useful.

Andrea

------------------------------
Andrea Lodi
Andrew H. and Ann R. Tisch Professor
Cornell Tech
New York NY

Original Message:
Sent: 06-20-2025 22:59
From: Paul Rubin
Subject: Heuristics in practice

Jonathon,

Thanks for sharing that. For problems that fit a paradigm (LP, MIP, QP, ...) for which good solvers are available, it makes perfect sense to try the solvers first and resort to heuristics as needed. I've seen more than a few people say, in various contexts, "the problem is NP-hard so we have to use a heuristic", rather than taking a shot at optimality using a solver. My sense is that they are mostly (all?) academics looking for a justification for their shiny new heuristic as opposed to industry folks with specific problems and looking for good solutions rather than publications.

Paul

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI

Original Message:
Sent: 06-20-2025 21:39
From: Jonathon Leverenz
Subject: Heuristics in practice

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

------------------------------
Jonathon Leverenz
Operations Research Analyst
Systems Planning and Analysis, Inc
Alexandria VA

Original Message:
Sent: 06-13-2025 15:48
From: Paul Rubin
Subject: Heuristics in practice

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI
------------------------------

Andrea,

Thanks for the comments (and the link to the book). I wonder if industry/government users solving MIPs or other well-studied problems ever tell the solver to run heuristics but stop with either the first feasible solution or at least before any branching, just to get a sufficiently good answer quickly (or to avoid running out of memory on really large problems)?

It probably goes without saying, but I'll say it anyway just for completeness: if you're confronted with a nonlinear, nonconvex, non-smooth, non-everything problem, heuristics are probably the only option available. So I also wonder whether that happens in practice, or whether everyone (in the real world, i.e., not academics) just forces the model to be tractable regardless of the discrepancies with reality. I recall whipping out the Nelder-Mead simplex algorithm, which has nothing to do with LPs or anything necessarily linear, a couple of times in recent years, but can't recall context.

Hi Paul and Jonathon,

for someone like me that has spent a significant amount of time in designing primal heuristics to be included in mixed-integer programming (MIP) solvers, this is a very interesting and useful thread, thanks!

My take is that the exercise of modeling the problem and giving it to a solver is useful to get a sense of its practical difficulty, besides its NP-hardness, and in addition any good MIP solver is now very well equipped to produce good feasible solutions, which -- in turns -- connects with Paul's argument on the need for optimality in practice.

Together with Timo Berthold and Domenico Salvagnin, we recently published a book "Primal Heuristics in Integer Programming" whose goal is indeed to highlight MIP solvers' ability to produce high-quality feasible solutions. The book presents in a principled way the algorithmic ideas at the core of the arsenal of primal heuristics in today's MIP solvers.

Hope this is useful.

Andrea

------------------------------
Andrea Lodi
Andrew H. and Ann R. Tisch Professor
Cornell Tech
New York NY

Original Message:
Sent: 06-20-2025 22:59
From: Paul Rubin
Subject: Heuristics in practice

Jonathon,

Thanks for sharing that. For problems that fit a paradigm (LP, MIP, QP, ...) for which good solvers are available, it makes perfect sense to try the solvers first and resort to heuristics as needed. I've seen more than a few people say, in various contexts, "the problem is NP-hard so we have to use a heuristic", rather than taking a shot at optimality using a solver. My sense is that they are mostly (all?) academics looking for a justification for their shiny new heuristic as opposed to industry folks with specific problems and looking for good solutions rather than publications.

Paul

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI

Original Message:
Sent: 06-20-2025 21:39
From: Jonathon Leverenz
Subject: Heuristics in practice

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

------------------------------
Jonathon Leverenz
Operations Research Analyst
Systems Planning and Analysis, Inc
Alexandria VA

Original Message:
Sent: 06-13-2025 15:48
From: Paul Rubin
Subject: Heuristics in practice

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI
------------------------------

Andrea,

Thanks for the comments (and the link to the book). I wonder if industry/government users solving MIPs or other well-studied problems ever tell the solver to run heuristics but stop with either the first feasible solution or at least before any branching, just to get a sufficiently good answer quickly (or to avoid running out of memory on really large problems)?

It probably goes without saying, but I'll say it anyway just for completeness: if you're confronted with a nonlinear, nonconvex, non-smooth, non-everything problem, heuristics are probably the only option available. So I also wonder whether that happens in practice, or whether everyone (in the real world, i.e., not academics) just forces the model to be tractable regardless of the discrepancies with reality. I recall whipping out the Nelder-Mead simplex algorithm, which has nothing to do with LPs or anything necessarily linear, a couple of times in recent years, but can't recall context.

Hi Paul and Jonathon,

for someone like me that has spent a significant amount of time in designing primal heuristics to be included in mixed-integer programming (MIP) solvers, this is a very interesting and useful thread, thanks!

My take is that the exercise of modeling the problem and giving it to a solver is useful to get a sense of its practical difficulty, besides its NP-hardness, and in addition any good MIP solver is now very well equipped to produce good feasible solutions, which -- in turns -- connects with Paul's argument on the need for optimality in practice.

Together with Timo Berthold and Domenico Salvagnin, we recently published a book "Primal Heuristics in Integer Programming" whose goal is indeed to highlight MIP solvers' ability to produce high-quality feasible solutions. The book presents in a principled way the algorithmic ideas at the core of the arsenal of primal heuristics in today's MIP solvers.

Hope this is useful.

Andrea

------------------------------
Andrea Lodi
Andrew H. and Ann R. Tisch Professor
Cornell Tech
New York NY

Original Message:
Sent: 06-20-2025 22:59
From: Paul Rubin
Subject: Heuristics in practice

Jonathon,

Thanks for sharing that. For problems that fit a paradigm (LP, MIP, QP, ...) for which good solvers are available, it makes perfect sense to try the solvers first and resort to heuristics as needed. I've seen more than a few people say, in various contexts, "the problem is NP-hard so we have to use a heuristic", rather than taking a shot at optimality using a solver. My sense is that they are mostly (all?) academics looking for a justification for their shiny new heuristic as opposed to industry folks with specific problems and looking for good solutions rather than publications.

Paul

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI

Original Message:
Sent: 06-20-2025 21:39
From: Jonathon Leverenz
Subject: Heuristics in practice

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

------------------------------
Jonathon Leverenz
Operations Research Analyst
Systems Planning and Analysis, Inc
Alexandria VA

Original Message:
Sent: 06-13-2025 15:48
From: Paul Rubin
Subject: Heuristics in practice

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI
------------------------------

Paul:

You asked:

I wonder if industry/government users solving MIPs or other well-studied problems ever tell the solver to run heuristics but stop with either the first feasible solution or at least before any branching, just to get a sufficiently good answer quickly (or to avoid running out of memory on really large problems)?

The answer to your question about what happens in industry is "it depends".  Usually, pure optimality doesn't matter. Factors to consider:

• Are we trying to improve on some manual decision process?  If so, then any solution a solver can come up with is good enough to gain customer acceptance.  However, if the end user can look at the answer from that first feasible solution and determine a "better" answer by hand, then you need to let the solver run longer, or design a better model.
• What is the decision cadence?  i.e., at what frequency will the optimization be run, and how soon do answers need to be delivered, and then acted upon by the business?  E.g., if you are doing supply chain network design to determine where your next facility will be located, you have time to get an optimal solution - you don't solve that problem every hour.  But I've been in cases where there is a problem solved every 5 minutes, with the solutions needed pretty quickly, so you set a time limit on the solver so that there is enough time for the decisions to flow out to the operational system.
• If the problem will be solved multiple times - with just changes in the data - how robust can you make the solution so that it delivers a reasonable answer in a fixed amount of time?  If using a solver, there are reasonable controls to make that work.  But if you are designing your own heuristic for some complex problem, the challenge is to make that heuristic robust across multiple data sets - especially data sets that you haven't seen.
• Another challenge with a specialized heuristic for a problem is what to do when the requirements change?  For example, you get your heuristic to work and be robust for today's problem requirements.  But in 6 months, a new constraint comes along, and your heuristic doesn't work.  One of the nice things about MIP is that you can usually just add a new constraint to your existing model and it will continue to work.  On the other hand, sometimes the new constraint means you have to revisit your original modeling approach.

Andrea,

Thanks for the comments (and the link to the book). I wonder if industry/government users solving MIPs or other well-studied problems ever tell the solver to run heuristics but stop with either the first feasible solution or at least before any branching, just to get a sufficiently good answer quickly (or to avoid running out of memory on really large problems)?

It probably goes without saying, but I'll say it anyway just for completeness: if you're confronted with a nonlinear, nonconvex, non-smooth, non-everything problem, heuristics are probably the only option available. So I also wonder whether that happens in practice, or whether everyone (in the real world, i.e., not academics) just forces the model to be tractable regardless of the discrepancies with reality. I recall whipping out the Nelder-Mead simplex algorithm, which has nothing to do with LPs or anything necessarily linear, a couple of times in recent years, but can't recall context.

Hi Paul and Jonathon,

for someone like me that has spent a significant amount of time in designing primal heuristics to be included in mixed-integer programming (MIP) solvers, this is a very interesting and useful thread, thanks!

My take is that the exercise of modeling the problem and giving it to a solver is useful to get a sense of its practical difficulty, besides its NP-hardness, and in addition any good MIP solver is now very well equipped to produce good feasible solutions, which -- in turns -- connects with Paul's argument on the need for optimality in practice.

Together with Timo Berthold and Domenico Salvagnin, we recently published a book "Primal Heuristics in Integer Programming" whose goal is indeed to highlight MIP solvers' ability to produce high-quality feasible solutions. The book presents in a principled way the algorithmic ideas at the core of the arsenal of primal heuristics in today's MIP solvers.

Hope this is useful.

Andrea

------------------------------
Andrea Lodi
Andrew H. and Ann R. Tisch Professor
Cornell Tech
New York NY

Original Message:
Sent: 06-20-2025 22:59
From: Paul Rubin
Subject: Heuristics in practice

Jonathon,

Thanks for sharing that. For problems that fit a paradigm (LP, MIP, QP, ...) for which good solvers are available, it makes perfect sense to try the solvers first and resort to heuristics as needed. I've seen more than a few people say, in various contexts, "the problem is NP-hard so we have to use a heuristic", rather than taking a shot at optimality using a solver. My sense is that they are mostly (all?) academics looking for a justification for their shiny new heuristic as opposed to industry folks with specific problems and looking for good solutions rather than publications.

Paul

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI

Original Message:
Sent: 06-20-2025 21:39
From: Jonathon Leverenz
Subject: Heuristics in practice

Paul,

   I've been working in industry the past 8 years and my inclination is the same as yours - start by framing something as an optimization problem and (assuming it can be) see what I can do with a solver.  I've found there is great benefit to always starting this way, both from a modeling and solving standpoint as well as client communication.  The real trick - and one of the things I've learned the most since moving from academia/grad school to industry - is identifying when an optimal solution is needed and when an approximate is okay.  

I'm perfectly happy using heuristics, but what I've found is the built-in methods that come with solvers are usually sufficient for getting a sufficiently good solution for most problems I deal with.  For the rest I have a few heuristic methods, but they are still ultimately based around optimization.

------------------------------
Jonathon Leverenz
Operations Research Analyst
Systems Planning and Analysis, Inc
Alexandria VA

Original Message:
Sent: 06-13-2025 15:48
From: Paul Rubin
Subject: Heuristics in practice

I'm curious about the likelihood that practitioners (not academics) will use heuristics in optimization problems they encounter, as opposed to optimization models (and solvers). For clarity, I would not count heuristics baked into solvers (for finding good feasible solutions, etc.) as a use of heuristics, but would count using a solver and stopping it short of convergence (for instance, when hitting a time limit).

As a (reformed) academic, my first inclination is to try to turn any problem into an optimization model and either feed it to a solver or devise a "clever" (and often impractical) method for solving to optimality. At the same time, when I was teaching MBA candidates, I would remind them that their models were typically a somewhat coarse approximation to reality (deterministic models in a stochastic universe, linear approximations to nonlinear phenomena, single criterion models that ignored criteria of interest to the decision makers, ...). So spending lots of time trying to get an "optimal" solution might be, to use a phrase from my graduate days, milking a duck.

Computers are a lot faster now (and vacuum tubes no longer power them), algorithms are a lot more sophisticated, and we can now solve types of problems that were simply not doable back when I started. So do practitioners almost always optimize, or are heuristics still widely applied?

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
East Lansing MI
------------------------------