matlaboptimizationheuristicsmixed-integer-programmingsimulated-annealing

How to take into account the constraints of MIP in Simulated Annealing algorithm?


I'm trying to build a MATLAB code of Simulated Annealing heuristics algorithm for a two-echelon open location routing problem (2E-OLRP), which is a kind of combinatorial optimization problem.

However, I've been struggling to understand how SA takes into account the constraints of a MIP model. As far as I understand, SA algorithm only focuses on minimizing the objective function without considering any constraints which define the problem.

So, I was wondering what is the right approach to solve the problem, which can be formulated as MIP, using SA heuristic (or any meta-heuristics).


Solution

  • Typically a MIP model is very different from the model used in the SA algorithm (or other meta-heuristics). MIP models like to have many constraints (often the more the better). For heuristics, constraints are often more difficult. We often either handle constraints implicitly or add them with a penalty to the objective. In general, you cannot feed a MIP model directly to some heuristic algorithm. You really have to develop two very different models.