0
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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 $\endgroup$ Oct 13, 2012 at 20:13
  • $\begingroup$ 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$. $\endgroup$
    – nicolas66
    Oct 14, 2012 at 16:38
  • $\begingroup$ It's been 4 years now. Please edit your problem to be more detailed--if nothing else, to incorporate your comment. $\endgroup$
    – D. Ror.
    Oct 19, 2016 at 21:23

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.