[C/C++/Mat Lab] Graph vertex coloring - Branch and Price

[evil_stefano]

Ciao ragazzi,

qualcuno ha idea di come si realizza un algoritmo di branch and price ?

devo fare un programma che risolva il problema della colorazione dei vertici di un grafo con meno colori possibili, in pratica mi è stato chiesto di riprodurre il lavoro di Mehrotra e Trick ma con la variante di usare l'algoritmo di Lawler & al. per il pricing.

Il linguaggio di programmazione può essere C/C++/C# , ma penso conterrà anche parti in linguaggio matematico (tipo matlab) per usare i risolutori lineari.

Qualcuno ha suggerimenti o anche parti di codice già fatto ?



Grazie.



PS:
esempio di cosa devo fare:
http://mat.gsia.cmu.edu/COLOR/solvers/trick.c

[evil_stefano]

UP !