2
$\begingroup$

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
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – EhsanK
    Aug 31, 2021 at 13:12
  • $\begingroup$ Your set partitioning model is pretty much complete. Is your question "how can I code this with Cplex ?" $\endgroup$
    – Kuifje
    Aug 31, 2021 at 13:19
  • $\begingroup$ @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. $\endgroup$
    – KGM
    Aug 31, 2021 at 13:21
  • $\begingroup$ If you can use PuLp, such an example is given here (Pulp is just the modeler, you can call CPLEX to solve the problem). $\endgroup$
    – Kuifje
    Aug 31, 2021 at 13:24
  • $\begingroup$ 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 $\endgroup$
    – fontanf
    Aug 31, 2021 at 13:58

1 Answer 1

3
$\begingroup$

In OPL CPLEX you could start with

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.