Hi,

many users try to write something similar to

dvar int x in 2..10;
dvar boolean b;

maximize x;
subject to
{
b*x<=7;
}

but they get

CPLEX Error  5002: 'q1' is not convex.  

and that is quite normal.

What can they do ?

1) Use CP:

using CP;

dvar int x in 2..10;
dvar boolean b;

maximize x;
subject to
{
b*x<=7;
}

2) Use logical constraints within CPLEX:

dvar int x in 2..10;
dvar boolean b;

dvar int bx;

maximize x;
subject to
{
bx<=7;

(b==1) => (bx==x);
(b==0) => (bx==0);
}

3) Linearize:

dvar int x in 2..10;
dvar boolean b;

dvar int bx;

maximize x;
subject to
{
bx<=7;

 

2*b<=bx;
bx<=10*b;

bx<=x-2*(1-b);
bx>=x-10*(1-b);
}

I hope this will help some.

regards

Originally posted by: skalli785

hello ; 

im new in Cplex and i try to solve a vehicle routing problem , so for that i can't execute my full program because i face a similar error that says Q is not positive semi definite and i try to use the first solution with using Cp but i didn't get any solution , and for those solutions (2) and (3) i can't convert them in my program , really it's been a long time that i struggle with this error , so i need some help , thank you in advance

so here is :

range  N=1..n;
range V=1..v;
range Z=2..n;

dvar boolean X[N][N][V];
dvar int u[N][V];

forall(i in N,k in V) contrainte7:
       a[i]<=u[i][k]<=b[i];
      forall (i in N,j in Z,k in V) contrainte8:
      X[i][j][k]*((s[i]+t[i][j]+w)+u[i][k])<=u[j][k];    

Hi,

you could use the three ways: 1) 2) or 3)

Let me show use with logical constraints, method 2)

You would write:

 
 
 int n=8;
 int v=4;
 
 range  N=1..n;
range V=1..v;
range Z=2..n;

int a[i in N]=0;
int b[i in N]=n;
int s[i in N]=n;
int t[i in N][j in Z]=ftoi(abs(j-i));
int w=1;

dvar boolean X[N][N][V];
dvar int u[N][V];
dvar int Xu[N][N][V]; // Xu = X * u

subject to
 {
 
 // Xu
 
 forall (i in N,j in Z,k in V)
   (X[i][j][k]==1)=>(Xu[i][j][k]==u[i][k]);
 
forall (i in N,j in Z,k in V)
   (X[i][j][k]==0)=>(Xu[i][j][k]==0);
    
forall(i in N,k in V) contrainte7:
       a[i]<=u[i][k]<=b[i];
      forall (i in N,j in Z,k in V) contrainte8:
      X[i][j][k]*((s[i]+t[i][j]+w))+Xu[i][j][k]<=u[j][k];    
    } 

regards

Originally posted by: skalli785

thank you for helping me , i used the 3 ways and it works perfectly just for n=8 or 10 customers , but in my project , i should execute this model for n=35 customers , so for that i have no errors and no solution neither , so i don't know how to solve this problem , and really i'd like to help me , thank you in advance , so  this is what i have so far :

tried aggregator 2 times.
MIP Presolve eliminated 252 rows and 260 columns.
MIP Presolve modified 7 coefficients.
Aggregator did 7 substitutions.
Reduced MIP has 45130 rows, 18634 columns, and 151424 nonzeros.
Reduced MIP has 9310 binaries, 9072 generals, 0 SOSs, and 0 indicators.
Elapsed time 10.02 sec. for 6% of probing (10 vars fixed).
Elapsed time 20.03 sec. for 12% of probing (26 vars fixed).
Probing fixed 26 vars, tightened 976 bounds.
Probing time =   21.78 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 654 rows and 542 columns.
MIP Presolve modified 17588 coefficients.
Reduced MIP has 44476 rows, 18092 columns, and 141698 nonzeros.
Reduced MIP has 9046 binaries, 9046 generals, 0 SOSs, and 0 indicators.
Presolve time =   22.45 sec.
Probing time =    0.34 sec.
Clique table members: 83920.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time =    0.48 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0       50.9260   428                     50.9260     1083         
      0     0        cutoff                                       2110         
Elapsed real time =  26.52 sec. (tree size =  0.00 MB, solutions = 0)

Implied bound cuts applied:  2
Gomory fractional cuts applied:  4

Root node processing (before b&c):
  Real time             =    4.07
Parallel b&c, 4 threads:
  Real time             =    0.00
  Sync time (average)   =    0.00
  Wait time (average)   =    0.00
                          -------
Total (root+branch&cut) =    4.07 sec.

Refine conflict on 10109 members...

 Iteration  Max Members  Min Members
         1         5055            0
         2         2528            0
         3         1264            0
         4          948            0
         5          790            0
         6          786            0
         7          784            0

Originally posted by: skalli785

hey

im still waiting for any answer , it's been a while that i am stuck with this problem , i don't know how to slove it , thank you in advance 

I think your model is infeasible.

You should read

Do not hesitate to watch https://www.youtube.com/watch?v=tUALbhJ2xWY

Originally posted by: AMM1

good morning

i am solving vrpmtw using cp optimizer

in my data set , i have the x and y coordinates of each client

i have problem regarding Transition matrix used in NoOverlap function

i calculate the distances using 

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))))> | p1, p2 in Positions };

i need to make Dist in real values not integers and then use it in noOverlap(truck[t],Dist);

how can i convert it?

and should i use after or next version? (noOverlap(truck[ t],Dist,After ),noOverlap(truck[ t],Dist,next )

Hi,

in noOverlap distances are integer.

So what you could do is scale up.

First you write

int scale=100;

Then

int         dist[<i,j> in Edges] = ftoi(ceil(scale*t[i][j]));

in order to move to integer and then in the subject to block

// Visits
    
    forall(i in Cities)   ctVisits:startOf(itvs[i]) in scale*a[i]..scale*b[i];

where a and b are earliest and latest times

regards

Originally posted by: AMM1

Thank you mr Alex for your answers,

but i still couldnt do it 

i calculate the distances using these equations

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2)))))> | p1, p2 in Positions };

 int distMatrix[p1 in Positions][p2 in Positions] = ftoi(round (sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2)))));  

so how can i change the calculated distances into float 

Hi,

since distances within noOverlap are integer I would stay integer and scale.

int scale=10000;

tuple position
{
key int id;
int x;
int y;
}

{position} Positions={<1,1,1>,<2,2,2>,<3,1,0>};

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = {
<p1.id,p2.id,ftoi(round(sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))))> | p1, p2 in Positions };

 int distMatrix[p1 in Positions][p2 in Positions] = ftoi(round (sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))));  
 
 {triplet} scaleDist = {
<p1.id,p2.id,ftoi(round(scale*sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))))> | p1, p2 in Positions };

 int scaledistMatrix[p1 in Positions][p2 in Positions] = ftoi(round (scale*sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2))));  
 
 
 execute
 {
 writeln(distMatrix);
 writeln(Dist);
 
 writeln(scaledistMatrix);
 writeln(scaleDist);
 }

gives

 [[0 1 1]
         [1 0 2]
         [1 2 0]]
 {<1 1 0> <1 2 1> <1 3 1> <2 1 1> <2 2 0> <2 3 2> <3 1 1>
     <3 2 2> <3 3 0>}
 [[0 14142 10000]
         [14142 0 22361]
         [10000 22361 0]]
 {<1 1 0> <1 2 14142> <1 3 10000> <2 1 14142> <2 2 0>
     <2 3 22361> <3 1 10000> <3 2 22361> <3 3 0>}

So you see for sqrt(2) 14142 would be a good approximation if you multiply all time by scale

That way, you deal with decimals and that is better than sticking with integer.

(Same kind of trick as in the example floatexpr at CPLEX_Studio1271\opl\examples\opl\floatexpr

regards

Regards

Originally posted by: AMM1

Good evening mr alex 

thank you for your reply

but this scaling for distances will give me inaccurate objective value since i am solving vrpmtw using cp ,

this scaling will slow up model . The model was solving  problems whithin 1 hour   and now it take a long time to solve them

Is there another way to use double precision distances matrix with noOvelap?

or any alternatives of noOoverlap to use it in vrpmtw model in order to use real ditances matrix and get real not integer objective value 

PS:

about after vs next

Note that if the transition matrix M satisfies the triangular inequality, the semantics of each of the two versions of the constraint noOverlap(π, M, Next) and noOverlap(π, M, After) is the same. If M does not satisfy the triangular inequality, constraint noOverlap(π, M, After) is stronger than noOverlap(π, M, Next).

regards

Originally posted by: Ryan Max

Hi, I am writing a code but i get stuck at the same problem with you. I guess I have to you the second method to solve this because I'll apply datasheet in to this model but it's seem quite hard for me, can you help me this:

int V=...; // set of vehicles
int N=...; // number of customers

float de[node]=...; 

float pi[node]=...;
range node=0..N+1;
range customers=1..N;
range vehicle=1..V;
dvar boolean x[node][node][vehicle];
dvar int D[node][vehicle]; 
dvar int P[node][vehicle];

forall(i in 1..N, v in vehicle,j in customers)
  {
  ( D[i][v]-D[j][v]-de[j])*x[i][j][v] == 0  ; } // constraint 14 

forall(i in 1..N,j in 1..N, v in vehicle)

{ 
(P[i][v]+ pi[j] -P[j][v])*x[i][j][v] == 0 ; }  //constraint 15 

 error : CPLEX(default) cannot extract expression

Hi

why not remembering that a product a*b is 0 iff a is 0 or b is 0

So you could rewrite

forall(i in 1..N, v in vehicle,j in customers)
  {
  ( D[i][v]-D[j][v]-de[j])*x[i][j][v] == 0  ; } // constraint 14 

into

forall(i in 1..N, v in vehicle,j in customers)
  {
  ( D[i][v]-D[j][v]-de[j]==0) || (x[i][j][v] == 0)  ; } //14

regards

https://medium.com/@alexfleischer_84755/optimization-simply-do-more-with-less-zoo-buses-and-kids-66940178db6

Originally posted by: Douglas Nogueira

Hi, Alex!

Your suggestion, "3) Linearize", worked perfectly for the mathematical model I'm proposing in my PhD thesis. Thank you!

However, in the paper I'm writing, I need to properly reference the source I got this strategy.

Could you recommend a paper or book that I could use as reference?

Thank you very much!

Douglas

Hi,

you could mention this : https://www.linkedin.com/pulse/how-opl-alex-fleischer/

regards