clustering without distances and an objective function
AnsweredConsider a clustering problem; grouping N points into K clusters:
x = m.addVars(N, K, vtype=GRB.BINARY)
m.addConstrs((x.sum(i, '*') == 1 for i in range(N)))
I have a list of pairs of points that I would like to put in the same cluster. It may not happen as there are other constraints. I think the code below should would work in theory (I have not tested it) but I suspect for a large problem this will be too slow (MIQP).
expr = QuadExpr()
for p in PairsThatShouldStayTogether:
i = p[0]
j = p[1]
for k in range(K):
expr += x[i,k] * x[j,k]
m.setObjective(expr, GRB.MAXIMIZE)
Is there a better way? How about this?
expr = LinExpr()
and then in the loop
expr += abs_( x[i,k]  x[j,k] )
and then try to minimize the expression?
PS: The code above may not work  I don’t think Gurobi allows using abs_() like this
expr += abs_( x[i,k]  x[j,k] )
so I would need to introduce other variables to fix that.

Note that the multiplication of 2 binary variables can be reformulated in linear fashion meaning that the problem is actually still a MIP. This approach should work the way you want.
The abs approach does not seem safe, because the value can be \(0\) either if both points are in cluster \(k\) or none of them is.
You could also consider introducing additional binary variables \(x_{ijk}\) which state that points \(i,j\) are both in cluster \(k\) if \(x_{ijk}=1\) and \(=0\) otherwise and use indicator constraints to model
\[\begin{align}
x_{ijk}=1 &\rightarrow x_{ik} + x_{jk} = 2\\
x_{ijk}=0 &\rightarrow x_{ik} + x_{jk} \leq 1
\end{align}\]I cannot tell which of the approaches would work best, so some experimentation is definitely required.
Best regards,
Jaromił0 
Ahh, I see it, you could introduce another binary variable z and then do this
z <= x, z <= y, z >= x + y  1
Thank you.
0 
Yes, you can do this manually. But you can also just use the "and" general constraint: addConstr(z == and_(x,y)).
Moreover, you can just stick with your quadratic objective function as indicated in your original post. Gurobi is clever enough to find out that the products of binary variables can be represented by a new auxiliary binary variable and a set of linear constraints. It will perform this reformulation automatically for you during presolve if you leave the "PreQLinearize" parameter at its default value, see https://www.gurobi.com/documentation/9.5/refman/preqlinearize.html#parameter:PreQLinearize
Regards,
Tobias
0 
Thank you Tobias, you saved my time, I was about to reformulate my problem. So quite likely my x * y formulation, which gets translated to MIP behind the scene, is as fast as it gets.
PS: I enjoyed your presentation last Fri 12/3.
0
Please sign in to leave a comment.
Comments
4 comments