# Metaheuristics and feasability

Hi there!

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.

Let us consider a simple and connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a finite set $\mathcal{C}=\{1,\ldots,k\}$ and a scoring function $\phi : \mathcal{C} \rightarrow \mathbb{N}$. Then, my problem can be stated as follows: find an assignment $x \in \mathcal{C}^\mathcal{V}$ such that each node has a value in $c \in \mathcal{C}$ and has at least one neighboring node with value $d$, $\forall d<c$. – nicolas66 Oct 14 '12 at 16:38