Graph coloring with ILCP / Cplex

Discussion in 'C++' started by cdvolko@gmail.com, Aug 8, 2012.

  1. Guest

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

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

    chromaticNumberExact = cp.getObjValue ();
    }
     
    , Aug 8, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul A. Rubin

    Re: Cplex hangs in Perl system command

    Paul A. Rubin, Aug 4, 2003, in forum: Perl
    Replies:
    2
    Views:
    3,620
    Paul A. Rubin
    Aug 5, 2003
  2. George Sakkis
    Replies:
    1
    Views:
    465
    Szabolcs Nagy
    Jan 29, 2007
  3. Emilio Mayorga
    Replies:
    6
    Views:
    352
    Martien Verbruggen
    Oct 8, 2003
  4. Replies:
    0
    Views:
    398
  5. Replies:
    2
    Views:
    46
    Akira Li
    Jun 1, 2014
Loading...

Share This Page