How to model and solve this problem mixed integer nonlinear programming

MIDCP
#1

I have a problem in which I am given points (e.g., 100 points) with dimensions 12 (a point is like a vector with 12 entries). I want to find a number of points e.g., 8 points that are closest to each other. To do this, I try to find a cluster of 8 points such that the Euclidean distance between the points and the center of the cluster is minimized. The formulation is like this (Note that the formulation below is for 2 dimensions points, not 12 )

min sum_{i=1}^M u_i * [(x_i-x_d)^2+(y_i-y_d)^2]
s.t.
sum_{i=1}^M= K
u_i={0,1} for all i

M is the number of points, e.g, 100
K is the number of the points in the found cluster (similar points)
x_ and y_i are the coordinates of point i
x_D and y_D is the center of the cluster (to be found)
u_i is an indication variable (u_i= 1 if the point i is in the cluster)

We see that due to the multiplication of variables in the objetive function, the problem is not convex . Any idea if the formulation is correct?. Also, how to transform this problem to a convex problem to be solved by cvx
Thank you

#2

Section 2,8 of https://www.fico.com/en/resource-access/download/3217 shows how to linearize the product of a binary and continuous variable. So you’d end up with an MIQP, which can be solved using CVX with Gurobi or Mosek as solver.

#3

Thank you Mark. I looked at section 2.8 but it seems to be valid if we want to linearize constraints. In my problem, the product of binary and continous variables is in the objective f

#4

Where the link has y = x*d, whether x*d appears in constraints, in the objective, or in both, declare y as a variable, replace x*d with y, and add the constraints in the link.

#5

Hi Mark, the link is not available https://www.fico.com/en/resource-download-file/3217 , I would be grateful if you could help in this

#6

https://www.fico.com/en/resource-access/download/3217

Thanks for pointing out the dead link. I have now updated the link in my previous post as well.

It’s a good reference. You should have saved it when I first posted the link. You should save it now.

#7

Thanks Mark. I was looking in the document on how to deal with this problem. I have a constraint 0<1/(x-y)<10 where x and y are optimization variables which must be non-negatives. In the problem I am formulating, x must be larger than or equal to y (i.e., x>=y.) to ensure 1/(x-y) is non-negative (they are only equal if y=0). Also if y=0, then x must also be zero. To avoid 1 divided by 0 in case x=y=0, I was thinking to use y/(x-y)<10. This will work if y=0 but not if y >0. Any clue how to reformulate this.

#8

Does this combination of two constraints do what you want?

1 <= 10*(x-y)
x >= y

This does not require binary or integer variables.

#9

but It could happen that y=0 and thus x=0 (if y=0 then x must be 0) but this will not satisfy 1 <= 10*(x-y)

#10

I am confused between what the actual constraints are vs. your attempt to implement them. In particular, whether y=0 then x must be 0 is a desired constraint, or a consequence of something else?

Perhaps you have a tolerance issue. Strict inequalities are not enforced as such by CVX or the solvers it calls. All inequalities are treated as non-strict. if you want strict inequality, you must include a “fudge factor”. For instance A >= B + 1e-4, rather than A > B.

#11

To make it clearly, I will explain what I am trying to model (without formulation). What I want is that depending on the value of y, I have these situations
(1) If y>0, then the constraint 0<1/(x-y)<=10 is active/forced (it must be satisfied)
(2) If y=0, then x also equals 0 and the constraint 0<1/(x-y)<=10 can ignored (as if it was not there)

#12

I suggest you post at or.stackexchange.com/ . There are may eager beavers there who love constraints like these. You will have to deal with the tolerance issue, because solvers don’t have a clean distinction between y = 0 and y being a very small positive number.

1 Like