Is it possible to solve a NP-hard p‌r‌o‌b‌l‌e‌m using both heuristic and mathematical programming?

Question

I have a Genetic Algorithm and mixed-integer programming model of a parallel machine scheduling problem. But mathematical model takes too much time to solve the problem and unlikely genetic algorithm takes less time but doesn't show the optimal solution. So I am curious about if it is impossible to take solution from the Genetic Algorithms and to set them as a starting point into the math programming. Is it possible in fact?

Answer 1

With the assumption, that you use a classical Branch and Bound MIP-Solver, it will help the solver up to a certain amount, if u supply heuristic solutions (for example by the corresponding callback). Not only one, you can supply even more to the solution pool.

1. The Problem is, that in most cases MIP-Solvers try to prove optimality. Even if the found the optimal solution, they run hours and days to prove, that they found the optimum. So maybe you can set a greater gap for the objective Value, which is accepted for optimality. Usually that helps a lot.
2. Scheduling problems usually are highly symetrical and usually perform rather bad with straightforward formulatins. Try to find scientific literature for your scheduling problem. Maybe in some math forum on stack-exchange.
3. If these problems are formulated straight forward, the LP-relaxation is often not super tight. In many cases, you will need some exra cuts, to perform at least acceptable. This has also implications to the duality gap.

So try to give for first big allowed gap for the objective value. Then try to pass several good (and different solutions) to the MIP-Solver for example by the corresponding heuristic callback. If it still not works acceptable, try to find some literature for your problem. But I think, the MathOverflow-Forum is more suited for those model topics (and propably, you will find there more skilled opinions for this topic than here).