Originally posted by: cdvolko

Hi,

I'm new to CPLEX. I want to use it to solve a graph coloring problem exactly. Here's my code:

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

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

IloCplex cplex (mod);
cplex.solve ();

chromaticNumberExact = cplex.getObjValue ();
}

This compiles, but it throws IloWrongUsage and terminates. What am I doing wrong?

x [i] is supposed to be the color of node i. If there is an edge between nodes i and j, x [i] must be != x [j]. The minimum number of colors is sought for.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: cdvolko

I have also tried following the recommendations for an integer program formulation of this problem more closely, but this does not even compile due to IloSum:
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 ();
}

Please help.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

There may or may not be errors in your code, but unless you surround it with {code}, it's hard to tell. The forum software translates parts of code into italics, "links" or other artifacts that make it hard to read the code.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Hi,

if you are a beginner, maybe writing a model in OPL would be easier for you.
Could that be an option?

regards
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

You need to surround you code snippet with '{code}' tags, otherwise we cannot read it.
As far as I can tell you never initialize the elements in the 'x' array? That would be a problem.
Could you please tell us which statement in your code throws the exception?
#DecisionOptimization
#MathematicalProgramming-General

Graph coloring is a simple way to assign colors to different points (nodes) in a graph so that no connected points have the same color. It helps make complex connections easier to understand and visually clear.Just like choosing colors for clarity, fun activities such as sanrio hello kitty coloring pages also use colors to create clear and enjoyable designs.

------------------------------
Globe sim
------------------------------

Original Message:
Sent: Wed December 24, 2025 03:09 AM
From: Archive User
Subject: Re: Graph coloring

Originally posted by: SystemAdmin

You need to surround you code snippet with '{code}' tags, otherwise we cannot read it.
As far as I can tell you never initialize the elements in the 'x' array? That would be a problem.
Could you please tell us which statement in your code throws the exception?
#DecisionOptimization
#MathematicalProgramming-General

in CPLEX_Studio2212\opl\examples\opl\color there is a graph coloring example

// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55
// Copyright IBM Corporation 1998, 2024. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

/* ------------------------------------------------------------

Problem Description
-------------------

The problem involves choosing colors for the countries on a map in 
such a way that at most four colors (blue, white, yellow, green) are 
used and no neighboring countries are the same color. In this exercise, 
you will find a solution for a map coloring problem with six countries: 
Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands. 

------------------------------------------------------------ */
using CP;

range r = 0..3;

string Names[r] = ["blue", "white", "yellow", "green"]; 

dvar int Belgium in r;
dvar int Denmark in r;
dvar int France in r;
dvar int Germany  in r;
dvar int Luxembourg in r;
dvar int Netherlands in r;

subject to {  
   Belgium != France; 
   Belgium != Germany; 
   Belgium != Netherlands;
   Belgium != Luxembourg;
   Denmark != Germany; 
   France != Germany; 
   France != Luxembourg; 
   Germany != Luxembourg;
   Germany != Netherlands;    
}

execute {
   writeln("Belgium:     ", Names[Belgium]);
   writeln("Denmark:     ", Names[Denmark]);
   writeln("France:      ", Names[France]);
   writeln("Germany:     ", Names[Germany]);
   writeln("Luxembourg:  ", Names[Luxembourg]);
   writeln("Netherlands: ", Names[Netherlands]);
}

tuple resultT {
	string name;
	string value;
};
{resultT} solution = {};
execute{
   solution.add("Belgium", Names[Belgium]);
   solution.add("Denmark", Names[Denmark]);
   solution.add("France", Names[France]);
   solution.add("Germany", Names[Germany]);
   solution.add("Luxembourg", Names[Luxembourg]);
   solution.add("Netherlands", Names[Netherlands]);
   writeln(solution);
}

------------------------------
[Alex] [Fleischer]
[Data and AI Technical Sales]
[IBM]
------------------------------

Original Message:
Sent: Wed December 24, 2025 03:09 AM
From: Globe sim
Subject: Re: Graph coloring

Graph coloring is a simple way to assign colors to different points (nodes) in a graph so that no connected points have the same color. It helps make complex connections easier to understand and visually clear.Just like choosing colors for clarity, fun activities such as sanrio hello kitty coloring pages also use colors to create clear and enjoyable designs.

------------------------------
Globe sim

Original Message:
Sent: Wed December 24, 2025 03:09 AM
From: Archive User
Subject: Re: Graph coloring

Originally posted by: SystemAdmin

You need to surround you code snippet with '{code}' tags, otherwise we cannot read it.
As far as I can tell you never initialize the elements in the 'x' array? That would be a problem.
Could you please tell us which statement in your code throws the exception?
#DecisionOptimization
#MathematicalProgramming-General