# How to code this with Cplex?

I have an optimization problem as below.

For $$g\in G$$, let $$\mathcal{N}_g$$ be the nodes in group $$g$$, and let binary variable $$u_g$$ indicate whether group $$g$$ is used. The problem has this following constraint

\begin{align} \sum_{g\in G:\ i\in N_g} u_g &= 1 &&\text{for all i} \end{align}

How can Model this in Cplex?

For example, G=10;

$$\mathcal{N}_1={1,2}$$

$$\mathcal{N}_2={1,3,4}$$

$$\mathcal{N}_3={1,3,5}$$

$$\mathcal{N}_4={1,4,5,6}$$

...

$$\mathcal{N}_{10}={1,6,7,8}$$

The only constraint says that every node must be chosen just once.

Here is what I tried so far

IloEnv env;
try{

IloNum G=10;

IloNumVarArray Ug(env, G,0,1,ILOINT)

IloModel model(env)


In order to make it efficient for implementation I do a reformulation. I generate a binary matrix,$$B$$ of size $$N_{node}\times G$$, where $$N_{node}$$ is the number of nodes. If node $$n, n\in{1,2,\cdots,N_{node}}$$ is present in group $$g, g\in{1,2,\cdots,G}$$, then $$B_{n,g}=1$$, otherwise 0.

IloExpr constFun(env)


Note: In Matlab, this constraint now can be expressed as

  for n=1:N

sum(Ug(find(B(n,:)==1)))==1;

end

• Please edit your question and show what you have tried so far and where you are stuck. That way you can get better answers regarding your specific problem.
– EhsanK
Aug 31 at 13:12
• Your set partitioning model is pretty much complete. Is your question "how can I code this with Cplex ?" Aug 31 at 13:19
• @Kuifje yes. I am not so familiar with Cplex. Especially, the constraint is creating some problem. I do not know how to code this non-symmetric 2D array. Aug 31 at 13:21
• If you can use PuLp, such an example is given here (Pulp is just the modeler, you can call CPLEX to solve the problem). Aug 31 at 13:24
• You seeem to use C++. Here is a C++ example of an implementation of the Generalized Assignment Problem with Cplex. That's from what I start every time I write a new Cplex model in C++. Maybe it will help you Aug 31 at 13:58

int g=10;
range G=1..g;
range I=1..5;

{int} Ng[G]=[{1,2},{3,4},{5},{},{},
{},{},{},{},{}];

dvar boolean u[G];

subject to
{
forall(i in I) sum(g in G:i in Ng[g]) u[g]==1;
}