Thank You for pointing out that. Now, the program is running error free.
I have further queries regarding:
(i) Why dvar (cx,cy,r) were scaled up by certain factor (here, 100) ?
(ii) Does change in scale of dvar, has any effect on original formulation ?
(iii) Why additional constraint: forall(c in circles ) z[c]==(sum(i in points) g[i][c]>=1); is added ???
(iv) I have another constraint, which checks:
if z[j]=0, It implies sum(i in point) g[i][j] = 0, i.e. all g[i] for particular [j] will be 0, if z for that [j] is 0
The constraint mentioned in point (iii) may effect constraint mentioned in point (iv).
(v) And lastly, can you please explain why constraint mentioned in point (iii) is required ?
------------------------------
PRAVEEN KUMAR
------------------------------
Original Message:
Sent: Tue April 06, 2021 11:37 AM
From: ALEX FLEISCHER
Subject: Linear objective function and non-linear constraints due to Euclidean distance
Hi,
if you got that error that means you forgot
using CP;execute{ cp.param.timelimit=60;}
------------------------------
[Alex] [Fleischer]
[EMEA CPLEX Optimization Technical Sales]
[IBM]
Original Message:
Sent: Tue April 06, 2021 11:05 AM
From: PRAVEEN KUMAR
Subject: Linear objective function and non-linear constraints due to Euclidean distance
Thank You,
(i) I tried removing sqrt() first in my original code/formulation, and the error generated was: "Error 5002: 'inside()' is not convex ->"
(ii) I tried the code provided above by you, it also generated the same error: "Error 5002".
On the basis of above formulation and subsequent error generated, is it safe to say that the constraint in my problem is forming a non-convex region and hence is not solvable by using CPLEX (as MIQCP formulation has non-convex constraint).
Thank You.
------------------------------
PRAVEEN KUMAR
Original Message:
Sent: Tue April 06, 2021 09:29 AM
From: ALEX FLEISCHER
Subject: Linear objective function and non-linear constraints due to Euclidean distance
Hi,
you could try with CPOptimizer within CPLEX:
using CP;execute{ cp.param.timelimit=60;}range points=1..20;range circles=1..10;int x[i in points]=rand(100);int y[i in points]=rand(100);int scale=100;int xmin =0;int xmax=100;int rmin =10;int rmax=100;int ymin =0;int ymax=100;dvar boolean g[points][circles];dvar boolean z[circles];dvar int+ scalecx[circles] in scale*xmin..scale*xmax;dvar int+ scalecy[circles] in scale*ymin..scale*ymax;dvar int scaler[circles] in scale*rmin..scale*rmax;dexpr float cx[c in circles] =scalecx[c]/scale;dexpr float cy[c in circles] =scalecy[c]/scale;dexpr float r[c in circles] = scaler[c]/scale;minimize sum(j in circles) z[j];subject to{ forall(c in circles ) z[c]==(sum(i in points) g[i][c]>=1); forall(i in points) sum(c in circles) g[i][c]==1;forall (i,j in circles : i<j) {overlap:(cx[i]-cx[j])^2 + (cy[i]-cy[j])^2 - (r[i] + r[j])^2 >=0;}forall(i in points) {forall(j in circles) {inside:(g[i][j]==1) => ((x[i]-cx[j])^2 + (y[i]-cy[j])^2 <= r[j]*r[j]);}}}
------------------------------
[Alex] [Fleischer]
[EMEA CPLEX Optimization Technical Sales]
[IBM]
Original Message:
Sent: Sat April 03, 2021 06:47 AM
From: PRAVEEN KUMAR
Subject: Linear objective function and non-linear constraints due to Euclidean distance
Hello,
I am trying to create a model in which objective variable is linear, but the constraint involve calculation of euclidean distance between 2 points, these 2 points are in the following form:
(i) Both are decision variables (cx[i],cy[i]) and (cx[j],cy[j])
(ii) One point is known, say (px[i], py[i]) and other point is a decision variable: (cx[j],cy[j])
PROBLEM FORMULATION (Only some portion):
OBJECTIVE: minimize sum(j in circles) z[j];
DECISION VARIABLES:
dvar boolean g[points][circles];
dvar boolean z[circles];
dvar float+ cx[circles] in xmin..xmax;
dvar float+ cy[circles] in ymin..ymax;
dvar float r[circles] in rmin..rmax;
TWO OF THE CONSTRAINT:
forall (i,j in circles : i<j) {
overlap:
sqrt((cx[i]-cx[j])^2 + (cy[i]-cy[j])^2) - (r[i] + r[j]) >=0;
}
forall(i in points) {
forall(j in circles) {
inside:
M*g[i][j] + sqrt((x[i]-cx[j])^2 + (y[i]-cy[j])^2) - r[j] >= 0;
}
On running the code, i got the following error:
CPLEX(default) cannot extract expression: ((cx[i]+cx[j]*(-1))^2+(cy[i]+cy[j]*(-1))^2)^0.5
OPL cannot extract expression: forall(i in 1..5, j in 1..5: i < j) overlap: 0 <= r[i]*(-1)+r[j]*(-1)+((cx[i]+cx[j]*(-1))^2+(cy[i]+cy[j]*(-1))^2)^0.5
and more similar errors for constraint 2
My query is:
(i) What is the correct way of writing the above expression ?
(ii) If CPLEX solver is able to solve such problem involving: Mixed integer non-linear programming, with linear objective function and non-linearity arising only due to inclusion of euclidean distance ?
(iii) If not, which software/programming language/solver I can use to solve this optimization problem ?
Thank You.
------------------------------
PRAVEEN KUMAR
------------------------------
#DecisionOptimization