Reducing data sparsity in linear integer programming
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix of decision variables and are there any recommended performance tuning approaches to overcome this?
string V = "A","B";
string K = "Y","Z";
dvar boolean X[V][K];
dvar boolean Y[V][V][K][K];
subject to
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[i][u] ;
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[j][v];
forall(i,j in V,u,v in K) Y[i][j][u][v]>=X[i][u]+X[j][v]-1;
assert forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];
linear-programming integer-programming mixed-integer-programming
asked Aug 29 at 10:32
Malith
12
add a comment |Â
up vote
-1
down vote
favorite
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix of decision variables and are there any recommended performance tuning approaches to overcome this?
string V = "A","B";
string K = "Y","Z";
dvar boolean X[V][K];
dvar boolean Y[V][V][K][K];
subject to
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[i][u] ;
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[j][v];
forall(i,j in V,u,v in K) Y[i][j][u][v]>=X[i][u]+X[j][v]-1;
assert forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];
linear-programming integer-programming mixed-integer-programming
asked Aug 29 at 10:32
Malith
12
add a comment |Â
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix of decision variables and are there any recommended performance tuning approaches to overcome this?
string V = "A","B";
string K = "Y","Z";
dvar boolean X[V][K];
dvar boolean Y[V][V][K][K];
subject to
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[i][u] ;
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[j][v];
forall(i,j in V,u,v in K) Y[i][j][u][v]>=X[i][u]+X[j][v]-1;
assert forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];
linear-programming integer-programming mixed-integer-programming
asked Aug 29 at 10:32
Malith
12
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix of decision variables and are there any recommended performance tuning approaches to overcome this?
string V = "A","B";
string K = "Y","Z";
dvar boolean X[V][K];
dvar boolean Y[V][V][K][K];
subject to
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[i][u] ;
forall(i,j in V,u,v in K) Y[i][j][u][v]<=X[j][v];
forall(i,j in V,u,v in K) Y[i][j][u][v]>=X[i][u]+X[j][v]-1;
assert forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];
linear-programming integer-programming mixed-integer-programming
asked Aug 29 at 10:32
Malith
12
edited Aug 29 at 10:47
asked Aug 29 at 10:32
Malith
12
asked Aug 29 at 10:32
Malith
12
asked Aug 29 at 10:32
Malith
12
12
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
You can delete the last set of constraints (forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];) because it is already expressed by the first three sets of constraints due to the X and Y variables being binary.
answered Aug 29 at 12:09
YukiJ
1,6752624
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
You can delete the last set of constraints (forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];) because it is already expressed by the first three sets of constraints due to the X and Y variables being binary.
answered Aug 29 at 12:09
YukiJ
1,6752624
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
 |Â
show 2 more comments
up vote
0
down vote
You can delete the last set of constraints (forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];) because it is already expressed by the first three sets of constraints due to the X and Y variables being binary.
answered Aug 29 at 12:09
YukiJ
1,6752624
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
 |Â
show 2 more comments
up vote
0
down vote
up vote
0
down vote
You can delete the last set of constraints (forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];) because it is already expressed by the first three sets of constraints due to the X and Y variables being binary.
answered Aug 29 at 12:09
YukiJ
1,6752624
You can delete the last set of constraints (forall(i,j in V,u,v in K) Y[i][j][u][v]==X[i][u]*X[j][v];) because it is already expressed by the first three sets of constraints due to the X and Y variables being binary.
answered Aug 29 at 12:09
YukiJ
1,6752624
answered Aug 29 at 12:09
YukiJ
1,6752624
answered Aug 29 at 12:09
YukiJ
1,6752624
answered Aug 29 at 12:09
YukiJ
1,6752624
1,6752624
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
 |Â
show 2 more comments
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
That is needed to derive Y from X. Which is Y=X*X
– Malith
Aug 29 at 14:33
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
No, as I said, the first few sets of constraints implies that Y=X*X. There is no need to add this as a constraint.
– YukiJ
Aug 29 at 14:48
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
Yes you are right. I removed the line but the execution time of the solver remains the same.
– Malith
Aug 29 at 15:06
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
@Malith what is the objective function you are maximizing/minimizing?
– YukiJ
Aug 30 at 7:03
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
It is to maximize (E - e) with constrain $$ e >= sum_k=1^Np sum_u x(i,u) + sum_k=1^Np-1 sum_u,v y(i_k,i_k+1),(u,v) ~~~~~~~~~~~~~~~~~ ∀p∈ G $$
– Malith
Aug 31 at 12:56
 |Â
show 2 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898219%2freducing-data-sparsity-in-linear-integer-programming%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
