clustering without distances and an objective function

Answered

Permanently deleted user

• December 03, 2021 20:16

Consider 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.

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • December 06, 2021 10:01

  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
• 

  Permanently deleted user

  • December 06, 2021 12:28

  

  

  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
• 

  Tobias Achterberg

  Gurobi Staff

  • December 06, 2021 14:20

  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
• 

  Permanently deleted user

  • December 06, 2021 15:26

  

  

  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.