subtour elimination constraint pyomo
up vote
0
down vote
favorite
I am struggling to formulate the following subtour elimination constraint for TSP-like problem in Pyomo, given a graph G(V,A) where node 1 is the depot:
where x_ij and y_h are binary constraints that I have previously defined as binary variables.
First, I created a dictionary of all possible subsets S such that node 1 is always contained: subsets_s.
Then, I have been trying with something like this, but I am running into errors:
model1.con3=ConstraintList()
for h in model1.V:
if h is not 1:
for i in model1.S:
if h not in subsets_s[i]['nodes_subset']:
S=subsets_s[i]['nodes_subset']
for v in S:
print(v)
model1.con3.add(sum(sum(model1.x[v,j]) for j in
model1.V if j not in S)>=model1.y[h])
Do you have any suggestions?
Thank you
constraints traveling-salesman pyomo
edited Nov 9 at 22:02
Joel
1,6086719
asked Nov 9 at 21:12
Mike
217
add a comment |
up vote
0
down vote
favorite
I am struggling to formulate the following subtour elimination constraint for TSP-like problem in Pyomo, given a graph G(V,A) where node 1 is the depot:
where x_ij and y_h are binary constraints that I have previously defined as binary variables.
First, I created a dictionary of all possible subsets S such that node 1 is always contained: subsets_s.
Then, I have been trying with something like this, but I am running into errors:
model1.con3=ConstraintList()
for h in model1.V:
if h is not 1:
for i in model1.S:
if h not in subsets_s[i]['nodes_subset']:
S=subsets_s[i]['nodes_subset']
for v in S:
print(v)
model1.con3.add(sum(sum(model1.x[v,j]) for j in
model1.V if j not in S)>=model1.y[h])
Do you have any suggestions?
Thank you
constraints traveling-salesman pyomo
edited Nov 9 at 22:02
Joel
1,6086719
asked Nov 9 at 21:12
Mike
217
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
1
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
1
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am struggling to formulate the following subtour elimination constraint for TSP-like problem in Pyomo, given a graph G(V,A) where node 1 is the depot:
where x_ij and y_h are binary constraints that I have previously defined as binary variables.
First, I created a dictionary of all possible subsets S such that node 1 is always contained: subsets_s.
Then, I have been trying with something like this, but I am running into errors:
model1.con3=ConstraintList()
for h in model1.V:
if h is not 1:
for i in model1.S:
if h not in subsets_s[i]['nodes_subset']:
S=subsets_s[i]['nodes_subset']
for v in S:
print(v)
model1.con3.add(sum(sum(model1.x[v,j]) for j in
model1.V if j not in S)>=model1.y[h])
Do you have any suggestions?
Thank you
constraints traveling-salesman pyomo
edited Nov 9 at 22:02
Joel
1,6086719
asked Nov 9 at 21:12
Mike
217
I am struggling to formulate the following subtour elimination constraint for TSP-like problem in Pyomo, given a graph G(V,A) where node 1 is the depot:
where x_ij and y_h are binary constraints that I have previously defined as binary variables.
First, I created a dictionary of all possible subsets S such that node 1 is always contained: subsets_s.
Then, I have been trying with something like this, but I am running into errors:
model1.con3=ConstraintList()
for h in model1.V:
if h is not 1:
for i in model1.S:
if h not in subsets_s[i]['nodes_subset']:
S=subsets_s[i]['nodes_subset']
for v in S:
print(v)
model1.con3.add(sum(sum(model1.x[v,j]) for j in
model1.V if j not in S)>=model1.y[h])
Do you have any suggestions?
Thank you
constraints traveling-salesman pyomo
constraints traveling-salesman pyomo
edited Nov 9 at 22:02
Joel
1,6086719
asked Nov 9 at 21:12
Mike
217
edited Nov 9 at 22:02
Joel
1,6086719
asked Nov 9 at 21:12
Mike
217
edited Nov 9 at 22:02
Joel
1,6086719
edited Nov 9 at 22:02
Joel
1,6086719
edited Nov 9 at 22:02
Joel
1,6086719
1,6086719
asked Nov 9 at 21:12
Mike
217
asked Nov 9 at 21:12
Mike
217
asked Nov 9 at 21:12
Mike
217
217
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
1
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
1
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34
add a comment |
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
1
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
1
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
1
1
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
1
1
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53233334%2fsubtour-elimination-constraint-pyomo%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Please state a clear question and describe how you previously tried to find an answer to that question on your own.
– Tom
Nov 9 at 21:31
What have you tried? How are you struggling? Is it because of performance or because you couldn't write your constraint?
– V. Brunelle
Nov 9 at 21:31
Thank you. I have tried to provide more details now.
– Mike
Nov 9 at 21:37
1
For a graph with n nodes, there will be approximately 2^n subtour elimination constraints. The method I learned in university to deal with this is to start with no subtour elimination constraints and see what the solution is. If the solution includes a subtour, add a subtour elimination constraint to remove that subtour. Continue until you have no more subtours in your optimal solution. (If this takes too long, you can always use a heuristic method to get a "good" but not necessarily optimal solution)
– Joel
Nov 9 at 22:02
1
Could you post the error messages you're seeing?
– Bethany Nicholson
Nov 12 at 15:34