milp solver and ALNS about alns HOT 5 CLOSED

Hi @rlacjfjin,

Yes, in principle that should be doable, and would veer into the territory of a matheuristic. The question is how to achieve this for your particular problem. Without problem details I can only discuss generalities.

Within ALNS you have basically two places where you could do something with an exact solution method: in the destroy phase, or in the repair step. I suspect it is most helpful to tackle the repair step optimally. In that repair step you receive a destroyed state that contains some partial solution, and it is up to you to repair it into a feasible solution. If you can do this reparation optimally via some MILP reformulation (and, equally importantly, if you can solve that reformulation reasonably fast) you might be able to find very good solutions within just a few hundred ALNS iterations already (compared to many thousands when you repair heuristically).

from alns.

So, is it impossible to adding ALNS to general MILP solver framework(branch and bound or branch and cut)?
In fact when I use exact solution method and want to speed up in specific problem, such as vrp or bin-packing, the initial part of giving feasible solution through heurisitc method can't work very well. For example, when I sovle cvrp using cbc solver, I use C-W savings to provide initial solution, but it seems have a little effect. I don't know what's problem is it.
In your experiences, could you give me some suggestions which type of problem can solved very efficient by ALNS?
Thanks,

from alns.

It's probably not impossible, but you'll have to be careful in how you formulate your problem.

If you want to use ALNS inside a branch-and-bound scheme, one way might be via branch-and-price with a path-based VRP formulation. Here, you select a subset of paths/variables for your restricted master problem, and then iteratively solve a pricing problem to determine whether there are still better paths you have not yet added to the master problem (such that they have negative reduced costs, so their inclusion would improve the solution). You could solve the pricing problem heuristically, e.g. via ALNS.

Whether that is better than doing everything via ALNS I cannot say.

Providing an initial solution to the solver could help, if an optimal solution also looks somewhat like that solution. If not, you have at best provided a lower bound to the solver - but that need not be helpful.

from alns.

Thanks a lot!👍

from alns.

@rlacjfjin you're quite welcome. I'm closing this issue for now, since I think it has been mostly resolved. If you run into an issue implementing one of the two approaches outlined above, feel free to open a new issue!

from alns.