MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Any idea about that?

share|cite|improve this question
If you can't tell us enough about the problem, we may not be able to tell you enough about the solution. I recommend rephrasing so that you can tell us all about an example you don't mind divulging. Gerhard "Ask Me About System Design" Paseman, 2012.10.13 – Gerhard Paseman Oct 13 '12 at 20:13
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.