I am currently working on a graph problem where I need to assign to each vertex a unique value under some particular constraints (I cannot detail the problem because this work will be published). This problem can be formulated into an integer linear program. Now, I would like to design an efficient heuristic for solving this problem. I have already designed a greedy one which iteratively add constraints but I would like to improve it using simulated annealing for instance. However, I cannot always for instance swap two nodes in the graph due to the constraints on the nodes values. I have read some stuff about penalty methods for simulated annealing but I think that the solution is not guaranteed to be always feasible (w.r.t. to the constraints). At the end of my heuristic, the solution must be feasible but can be infeasible during the process.
Any idea about that?