Skip to main content

clustering without distances and an objective function

Answered

Comments

4 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
    First Comment
    First Question

    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 Gurobi Staff

    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
    First Comment
    First Question

    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.