Symmetry Breaking Issue
回答済みHi everyone,
I have a constraint as in the following:
And I formulate it as in the following:
My indexes for N and V start with 0;
in my hz (i,v) variables the indexes that for ii has to be 1,2,3 because of my other settings. and the set for v is (0,1,2,3,4,5,6)
so what I want to achieve is to break the symmetry as like: hz(1,0);hz(1,1);hz(2,2); hz(2,3);hz(3,4) and hz(3,5).
However, what I get with the above coding:
hz(0,0); hz(1,3); hz(1,5); hz(2,0);hz(2,4);hz(3,1);hz(3,2)
Therefore this constraint creates a new index i starts from 0.
I also tried i in another set; which I give them manually; however, this constraint did not do any symmetry breaking as in the following:
So, I have coded this in GAMS and it is working correctly:
const(i,v)$(ord(v) ge 2)..hz(i,v)=l=sum(j$(ord(j) le ord(i), hz(j,v--1))
However, in Gams settings the indexes starts from 1. So, if you could any idea, how to solve this issue, could you please share it with me?
I would be really so happy..
Cheers,
Zühal.
-
正式なコメント
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Zühal,
Could you provide a minimum working example which produces the output
hz(1,0);hz(1,1);hz(2,2); hz(2,3);hz(3,4); hz(3,5)
In particular what are \(\texttt{N}\), \(\texttt{H}\) and \(\texttt{V}\).
What is the final desired output or constraints you would like to get?
Best regards,
Jaromił0 -
-
Hi Jaromil;
Thanks for your interest.
Firstly, I would like to reach out a solution like this:
hz(1,0)=1; hz(1,1)=1; hz(2,2)=1; hz(2,3)=1; hz(3,4)=1; hz(3,5)=1. I have not reached this yet with my formulation. This kind of solution breaks the symmetry in the formulation.
Regarding my sets:
N=0,1,2,3,4,5,6,7,8,9
H =1,2,3 (is a subset of N) (h(1)=1; h(2)=1; h(3)=1; h(0)=0, h(4)=0,..the rest of the h variables are zero.) I did lb=1; ub=1 for the set H (h(i).lb=1; h(i),ub=1 for set H)
sum(i,h(i))=p
V=range(p*nv)=0,1,2,3,4,5 (nv=2 for this example)
nv is the number of vehicle for each p
h(i)<= hz(i,v) (so, hz(i,v) is only positive if h(i)=1; therefore we can use set H instead of N)
h(i) is binary; hz(i,v) binary
So, my code in Gams is producing a result; which breaks the symmetry as in the following:
GAMS code: const(i,v)$(ord(v) ge 2)..hz(i,v)=l=sum(j$(ord(j) le ord(i), hz(j,v--1))
hz(1,0)=1; hz(1,1)=1; hz(2,2)=1; hz(2,3)=1; hz(3,4)=1; hz(3,5)=1.
And it decreases solution time dramatically.
So, I would like to reach the same solution with the same constraint in GUROBI too.
However, my constraint does not produce any symmetry breaking when I use set H as in the following. The code produces something like this:
hz(1,3); hz(1,5); hz(2,0);hz(2,4);hz(3,1);hz(3,2)
When I use set N: because I defined hz (i,v) in set N and set V;
I am getting a result as in the following: hz(0,0)=1; hz(1,3)=1; hz(1,5)=1; hz(2,0)=1;hz(2,4)=1;hz(3,1)=1;hz(3,2)=1
Here, node 0 is not in the set H. So, this is an incorrect solution for me.
It looks like I need to use set H; but it does not break the symmetry; the same constraint works in GAMS though..
So, I hope it is clear and I would like to be really happy if you have any idea to solve the problem..
Thank you again,
Cheers,
0 -
-
Hi Jaromil again!
I have solved the problem, Luckily!
Thanks for your interest..
Cheers,
0 -
-
-
Hi Zühal,
Great to hear! Would it be OK for you to share your solution with the Community? This may help others in the future.
Best regards,
Jaromił0 -
-
Hi Jaromil,
I have deleted for v in V[1:] after quicksum; because I have already added this in the for loops.
So, this constraint does the job right now. If someone has some symmetry in their mathematical formulations, I strongly advise them to include this kind of constraint. The solution time decreases dramatically!
I hope this helps!
Cheers,
Zühal.
0 -
投稿コメントは受け付けていません。
コメント
6件のコメント