Decision Optimization

 View Only
  • 1.  Linear objective function and non-linear constraints due to Euclidean distance

    Posted Tue April 06, 2021 07:15 AM

    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


  • 2.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Tue April 06, 2021 09:29 AM
    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]
    ------------------------------



  • 3.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Tue April 06, 2021 11:05 AM
    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
    ------------------------------



  • 4.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Tue April 06, 2021 11:38 AM
    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]
    ------------------------------



  • 5.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Tue April 06, 2021 01:22 PM
    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
    ------------------------------



  • 6.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Wed April 07, 2021 02:42 AM
    Hi,

    (i) Why dvar (cx,cy,r) were scaled up by certain factor (here, 100) ?

    ==> Within CPOptimizer decision variables cannot be float so as a workaround I used dvar int and divided by scale in order to get decimal expressions.

    (ii) Does change in scale of dvar, has any effect on original formulation ?

    ==> yes , this changes the precision

    (iii) Why additional constraint: forall(c in circles ) z[c]==(sum(i in points) g[i][c]>=1); is added ???

    ==> To know whether a circle is uded I added that but if you do not need that you may remove.

    regards

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 7.  RE: Linear objective function and non-linear constraints due to Euclidean distance

    Posted Sat April 10, 2021 11:16 AM
    Thank you very much Alex.

    I tried to formulate my problem in the setup described above, with some little modification and it is working great.
    Using CP Optimizer with desired/required level of precision.

    ------------------------------
    PRAVEEN KUMAR
    ------------------------------