Dear all,
Is there any way to enumerate all possible solutions of attached model in a systematic manner?
Currently, I am adding integer cuts one by one after finding solution.
I will really appreciate for addressing this issue. Also I want record solution of each integer cut.
Best regards,
Rofice
Integer cut Topic is solved
Integer cut
- Attachments
-
- Untitled_41.gms
- (851 Bytes) Downloaded 262 times
Re: Integer cut
Hi Rofice
Did you see this example https://www.gams.com/latest/gamslib_ml/ ... _icut.html?
Cheers
Renger
Did you see this example https://www.gams.com/latest/gamslib_ml/ ... _icut.html?
Cheers
Renger
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
Enjoy modeling even more: Read my blog on modeling at The lazy economist
Re: Integer cut
Hi Renger,
Yes, I did. I don't get it.
I don't have integer variables in my real model; it only contains binary variables and continuous variables. That's why I just formulated simple model consisting of only binary variables. Now, if I want to use systematic enumeration procedure do I need extra binary variables that continuously add cuts to my model?
If you can provide formulation of attached model and the question I asked, it will be much easier for me to understand the concept.
Best regards,
Rofice
Yes, I did. I don't get it.
I don't have integer variables in my real model; it only contains binary variables and continuous variables. That's why I just formulated simple model consisting of only binary variables. Now, if I want to use systematic enumeration procedure do I need extra binary variables that continuously add cuts to my model?
If you can provide formulation of attached model and the question I asked, it will be much easier for me to understand the concept.
Best regards,
Rofice
Re: Integer cut
Hi Rofice
You could try something like this (and adjust it to your wishes):
Renger
You could try something like this (and adjust it to your wishes):
Code: Select all
alias(i,ii,k,m);
alias(j,jj,l,n);
parameter b(k,l,m,n) Mapping ;
b(k,l,m,n) = 0;
equation
c1 objective function
c2 logical constraint only one alternative can be selected for each i,
cut(i,j,ii,jj) cutting constraints;
c1.. OBJECTIVE =e= sum((i,j),alternative(i,j) *Y(i,j));
c2(i) .. sum(j, Y(i,j))=e=1;
cut(i,j,ii,jj)$b(i,j,ii,jj).. Y(i,j) + Y(ii,jj) =l= 1;
model mymodel /all/;
solve mymodel maximize objective using mip;
loop(k,
loop(l,
loop(m,
loop(n,
b(k,l,m,n) = 1;
solve mymodel maximize objective using mip;
);
);
);
);
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
Enjoy modeling even more: Read my blog on modeling at The lazy economist
Re: Integer cut
Rofice,
You have a model with binary variables, so the cuts are pretty easy. It is a bit messier with integer variables. Essentially, for a given solution xbar(i), you can make sure that solution is not repeated by counting the differences between xbar and x and bounding this below by 1:
sum{i s.t. xbar(i) == 0, x(i)} + sum{i s.t. xbar(i) == 1, (1-x(i))} >= 1
As you accumulate more solutions xbar, you add more constraints to the model.
Another way to do this that doesn't involve adding any cuts is to use solver-specific features that enumerate all solutions and store them in a solution pool.
I attach models that do it both ways.
-Steve
You have a model with binary variables, so the cuts are pretty easy. It is a bit messier with integer variables. Essentially, for a given solution xbar(i), you can make sure that solution is not repeated by counting the differences between xbar and x and bounding this below by 1:
sum{i s.t. xbar(i) == 0, x(i)} + sum{i s.t. xbar(i) == 1, (1-x(i))} >= 1
As you accumulate more solutions xbar, you add more constraints to the model.
Another way to do this that doesn't involve adding any cuts is to use solver-specific features that enumerate all solutions and store them in a solution pool.
I attach models that do it both ways.
-Steve
- Attachments
-
- solnpool.gms
- (678 Bytes) Downloaded 263 times
-
- cutting.gdx
- (4.33 KiB) Downloaded 239 times
Re: Integer cut
Dear Renger and Steve,
I really appreciate your suggestions and formulations.
Steve, I think you forget to attach the second model because the second file is only GDX.
I have made a formulation that systematically adds cuts to model and finds all feasible solution and terminates as soon solution become infeasible. However, I think there is still one problem. If you notice equation "cut" in the model, for each i, two new indices (actually alias) has to introduce in the equation. Now if the members of the set i increases from two to three, this means 4 indices are needed to add according to the current formulation.
Is there any way to reduce the number of indices by loops or some other strategy?
I also attached models, the first model is when i has only two members and later is when i has 3 members. You can notice that how the number of indices grows by increasing the members of i.
Best regards,
Rofice
I really appreciate your suggestions and formulations.
Steve, I think you forget to attach the second model because the second file is only GDX.
I have made a formulation that systematically adds cuts to model and finds all feasible solution and terminates as soon solution become infeasible. However, I think there is still one problem. If you notice equation "cut" in the model, for each i, two new indices (actually alias) has to introduce in the equation. Now if the members of the set i increases from two to three, this means 4 indices are needed to add according to the current formulation.
Is there any way to reduce the number of indices by loops or some other strategy?
I also attached models, the first model is when i has only two members and later is when i has 3 members. You can notice that how the number of indices grows by increasing the members of i.
Best regards,
Rofice
- Attachments
-
- Integer cut2.gms
- (1.99 KiB) Downloaded 257 times
-
- Integer cut1.gms
- (1.66 KiB) Downloaded 265 times
Re: Integer cut
Oops, here's the cutting.gms file.
- Attachments
-
- cutting.gms
- Cut off previous solutions
- (1.45 KiB) Downloaded 311 times
Re: Integer cut
The cut equation you have:
does not work. For example, if you had an all-zero previous solution, the above constraint would not cut it off.
The formulation in my GAMS file cutting.gms is, IMHO, much simpler. I believe it is also correct.
-Steve
Code: Select all
cut(kk,i,j,ii,jj)$(report1(kk,i,j) and report2(kk,ii,jj))..
y(i,j) + y(ii,jj) =l= 1;
The formulation in my GAMS file cutting.gms is, IMHO, much simpler. I believe it is also correct.
-Steve