Originally posted by: pnuzyf

Hi,

I want to solve a problem using cplex opl. The problem is expressed as follows:

It is a edge-coloring problem. Suppose that (m,n) denotes the edge starting from node m to node n, and (n,m) denotes the edge starting from node n to node m. Links denotes the set of edges, Channels denotes the set of colors, i denotes the index of color, Interference<m,n> denotes the set of edges which interfere with edge (m,n), note that edge (n,m) should be included in Interference<m,n>. There are two constraints:

1) Each edge can choose only one color.
2) Within a interference range, each color can be chosen at most one time.
My solution to this problem is:

forall((m,n) in Links)
{
//only one color can be assigned to a given edge
sum(i in Channels) x(m,n,i) <= 1;
}

forall((m,n) in Links, i in Channels)
{
//ensure each color can be assigned to a pair of nodes at most one time within a interference range, note that x(m,n,i) = x(n,m,i), and (n,m) belongs to Interference(m,n)
x(m,n,i) + sum((p,q) in Interference(m,n)) x(p,q,i) <= 2
}
However, after I add the second constraint to my model, it takes long time to run and finally "out of memory" message comes out. Is there any better way to express the second constraint? Thanks in advance!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

There is a separate forum for OPL questions. You might do better there.

Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The OPL forum that Paul mentions is here.
One different formulation that comes to mind: Can you define your interference sets so that each set just contains the links that must not receive the same color? Then you could express the second constraint as (non-OPL syntax)

forall (i in Channels)
   sum ((m,n) in set) x[m,n,i] <= 1;

That looks a little more compact then what you have?
In a straightforward formulation of edge-coloring I would have expected a coloring constraint that looks like this

forall (n in Nodes)
   forall (i in Channels)
      sum (m in Nodes such that (m,n) in Links) x[m,n,i] +
      sum (m in Nodes such that (n,m) in Links) x[n,m,i]
      <=
      1;

which also seems different from what you have.
Maybe also research the literature about graph coloring, node coloring (which is closely related to edge coloring) and edge coloring. There is plenty of literature and there are different modeling approaches.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: pnuzyf

Thank you for your kind reply! I think you do not consider the direction of a link! In fact (n,m) and (m,n) both denotes the edge between node m and node n, but the directionality is different. The Interference set for link (m,n) includes all the links which could interfere with link (m,n). Note that (n,m) should be included in the interference set for link (m,n).
#CPLEXOptimizers
#DecisionOptimization