Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Graph coloring with ILCP / Cplex

Reply
Thread Tools

Graph coloring with ILCP / Cplex

 
 
cdvolko@gmail.com
Guest
Posts: n/a
 
      08-08-2012
Hi,

I am trying to use ILCP or Cplex to solve the graph coloring problem exactly. The following code is an attempt to implement the recommended way of solving this problem as an integer program. Unfortunately this code does not compile due to bad usage of IloSum. Moreover, I do not know how to specify the objective function for this (which should be: minimize the maximum colornumber used).

Meaning of the variables:
x [i] [j] == 1 iff node i has color j.

void calculateChromaticNumberExact ()
{
int i, j, k, numSubgraphs = graph->getNumSubgraphs (), numNodes = graph->getNumNodes ();
IloEnv env;
IloModel mod (env);
IloIntVar x [numSubgraphs] [numSubgraphs];

for (i = 0; i < numSubgraphs; i++)
{
mod.add (IloSum (x [i]) == 1);
for (j = 0; i < numSubgraphs; i++)
{
mod.add (x [i] [j] >= 0);
mod.add (x [i] [j] <= 1);
}
for (k = 0; k < i; k++)
if (graph->getEdge (i * numNodes + k))
for (j = 0; j < numSubgraphs; j++)
mod.add (x [i] [j] + x [k] [j] <= 1);
}

IloCP cp (mod);
cp.solve ();

chromaticNumberExact = cp.getObjValue ();
}
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Linear Programming with CPLEX cdvolko@gmail.com C++ 0 10-21-2012 04:28 PM
[Boost.Graph] graph.vertices property creates new objects George Sakkis Python 1 01-29-2007 11:09 PM
Missing Graph.h and (Graph.lib) woes - any help Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM
Re: Cplex hangs in Perl system command Paul A. Rubin Perl 2 08-05-2003 10:15 PM



Advertisments