Dear researchers,
In recent years, many of the researchers have introduced MIP models for engineering problems. It can be seen that many of them proposed metaheuristics to solve the models. As I know, the solution procedure in metaheuristics is related to the nature of problems not MIP models. Moreover, unlike MIP, the results of metaheuristics are not optimum. However, the many of MIP models cannot solve real world problems due to the size of them. This issue allows researchers to introduce metaheuristics for their problem. Therefore, what is the advantages of MIP model? And, why the MIP model are proposed for the problems?
The advantages of MIP model principaly hold through flexible resource profiles...
When I see a new combinatorial optimization problem, my first choice is always to model it as a MIP. At that point in time, I do not care how to solve it. This first step is to gain insight in the structure of the problem, in particular, if it is a real-world problem, where in some cases it is not clear what the problem is in the first place, then it might be unclear what are the hard constraints and the softer one (which then become the "objective function" of the MIP). So, MIP is for me is a good starting point, a common language to uniquely describe a problem in strict mathematical terms.
Once this first is done, the second great advantage of MIP is that there are lot of solvers available that solve such problems out-of-the-box (for instance, IBM Ilog Cplex, Gurobi, XPress, Scip, to name just a few). In many cases (in particular, for small-to-medium size problems) these solvers are surprisingly good in solving MIP problems without further knowledge from the user. So, as a prototype, one can rather quickly come back to the customer (the person posing the problem) and talk about the solution (usually, one has to go back to the modelling step then...).
You are right, these solvers cannot solve every problem instance to proven global optimality in short time, but it is always worth trying them first. When they fail, one has to think of how to speed up the solution process. Often, different ways how to model the very same problem are available, and some formulations are favorable for the MIP solvers compared to others. And yes, having a good heuristic at hand can also help, since MIP solvers are sometimes poor in generating feasible solutions. Most solvers however allow the integration of external heuristics into their solution process (via starting solutions or callback functionalities). From my point of view it is not "either MIP or heuristic", but more like: a heuristic is a part of a MIP solution strategy.
I agree, formulating the problem as a MIP helps to clarify what the problem is about. If real instances are too big to be solved by a solver, decomposition approaches may be tried or just use to MIP to compute a bound that certifies the quality of your heuristic solution.
I completely agree on Armin's contribution. I add one other possible direction of reasoning. Suppose you start from an heuristic approach. It may at least have the advantage to be fast(er). However, wouldn't you be interested in the quality of the generated heuristic solution? Of course, for larger problems you might not be able to solve the problem to optimality with an MILP. However, having an MILP model offers at least the option to benchmark the quality of an heuristic. Start to compare both solution approaches with different small(er) data sets. Provided that the algorithm finds the optimal solution, the best upper and/or lower bound on the objective function value is available. Even (the gap of) intermediate solution can be valuable. The offered gap can be quite informative for the quality of heuristic solutions. Developing good performing heuristics is hardly straightforward! The objective value of a feasible solution is commonly accepted as a performance indicator. The calculation effort of an heuristic may be favourable compared to an MILP but that's always at the expense of something else, i.e. the objective value.
Given the high quality of the answers of Fuegenschuh and Claassen, there is no good reason to continue this discussion! When these contributions are unclear to someone, then he or she should follow some appropriate courses in operations research . Then she or he will see, that without an appropriate toolkit of math, models, algorithms , and problem solvers, you cannot successfully practice the art of model building!
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs