MIP based heuristic vs. meta-heuristic

[mimi]

Dear all, 

give me please some idea or reference for comparison of MIP-based heuristics (embedded within CPLEX for example) and meta-heuristics (evolutionary algorithms). 

What are advantageos of MIP-based vs Genetic Algorithms for example?

Thank you!

Best,

Milos

[AMPL Google Group]

There is an interesting Gurobi report in this area:

4 Key Advantages of Using Mathematical Optimization Instead of Heuristics

In general I would say that if you can create a MIP model formulation without too much trouble, then a MIP solver will have the advantage: with MIP you can more easily model changes and complications, and you can get a bound on the optimality gap (which meta-heuristics do not provide). When a MIP is simply too difficult to formulate or to solve, then sometimes you can do better to program a meta-heuristic approach to your problem. Also the MIP and meta-heuristic approaches can be used together (see Matheuristics).

I am sure there are other discussions of this topic online, which you can find quickly with a Web search.

--
Robert Fourer
am...@googlegroups.com

{#HS:1777983352-108492#}

[mimi]

Thank you! What was my doubt is actually related to embedded solver heuristics such as CPLEX-based heuristics (or gurobi or scip) vs. meta or any other kind of tailor made heursitic approach (GA, SA...).

Since, in case when it can not find optimal, CPLEX or SCIP turns on the heuristics... - so my doubt is whether to build heurstical approach or it is better to use CPLEX-based heuristics for example. 

Best,

m

[AMPL Google Group]

After some initial processing, a MIP solver works to construct a search tree and to carry out a branching search. The solver continues its branching search until it proves that the current best solution is within some "gap" tolerance of being optimal, or it is stopped by the user (such as through a time limit). Also during the whole branching search, heuristics are used to look for better solutions (and for making other decisions that affect the solver's efficiency).

Thus for a MIP solver, seeking an optimum (to within the gap tolerance) and applying heuristics (to find better solutions) go on at the same time throughout the run. This makes MIP solvers significantly different from meta-heuristics, which do not have the overhead of building a search tree, but cannot prove optimality (to within some gap tolerance). You can't tell which approach will be better for a particular application, except by trying both, but if there is a good MIP formulation then that may be the easier thing to try first.

It is also possible to use a MIP solver as a sort of meta-heuristic, by running it for a certain amount of time, and then accepting whatever was the best solution found before the time limit. There's some discussion of this in Gurobi's MIP Models and Heuristics slides. Again it's hard to predict what approach will be better, but you probably want to start with whichever is easier.

--
Robert Fourer
am...@googlegroups.com

{#HS:1777983352-108492#}

On Fri, Feb 4, 2022 at 7:12 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thank you! What was my doubt is actually related to embedded solver heuristics such as CPLEX-based heuristics (or gurobi or scip) vs. meta or any other kind of tailor made heursitic approach (GA, SA...).

Since, in case when it can not find optimal, CPLEX or SCIP turns on the heuristics... - so my doubt is whether to build heurstical approach or it is better to use CPLEX-based heuristics for example.

Best,
m

On Fri, Feb 4, 2022 at 7:04 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

There is an interesting Gurobi report in this area:

4 Key Advantages of Using Mathematical Optimization Instead of Heuristics

In general I would say that if you can create a MIP model formulation without too much trouble, then a MIP solver will have the advantage: with MIP you can more easily model changes and complications, and you can get a bound on the optimality gap (which meta-heuristics do not provide). When a MIP is simply too difficult to formulate or to solve, then sometimes you can do better to program a meta-heuristic approach to your problem. Also the MIP and meta-heuristic approaches can be used together (see Matheuristics).

I am sure there are other discussions of this topic online, which you can find quickly with a Web search.

--
Robert Fourer
am...@googlegroups.com

[mimi]

Very valuable information. 

Thank you Bob!!