Integer cut Topic is solved

Problems with modeling
Post Reply
Rofice
User
User
Posts: 28
Joined: 6 years ago

Integer cut

Post by Rofice »

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
Attachments
Untitled_41.gms
(851 Bytes) Downloaded 232 times
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Integer cut

Post by Renger »

Hi Rofice

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
Rofice
User
User
Posts: 28
Joined: 6 years ago

Re: Integer cut

Post by Rofice »

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
User avatar
Renger
Posts: 639
Joined: 7 years ago

Re: Integer cut

Post by Renger »

Hi Rofice

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;
           );
       );
   );
);
Renger
____________________________________
Enjoy modeling even more: Read my blog on modeling at The lazy economist
User avatar
dirkse
Moderator
Moderator
Posts: 214
Joined: 7 years ago
Location: Fairfax, VA

Re: Integer cut

Post by dirkse »

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
Attachments
solnpool.gms
(678 Bytes) Downloaded 236 times
cutting.gdx
(4.33 KiB) Downloaded 214 times
Rofice
User
User
Posts: 28
Joined: 6 years ago

Re: Integer cut

Post by Rofice »

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
Attachments
Integer cut2.gms
(1.99 KiB) Downloaded 233 times
Integer cut1.gms
(1.66 KiB) Downloaded 234 times
User avatar
dirkse
Moderator
Moderator
Posts: 214
Joined: 7 years ago
Location: Fairfax, VA

Re: Integer cut

Post by dirkse »

Oops, here's the cutting.gms file.
Attachments
cutting.gms
Cut off previous solutions
(1.45 KiB) Downloaded 279 times
User avatar
dirkse
Moderator
Moderator
Posts: 214
Joined: 7 years ago
Location: Fairfax, VA

Re: Integer cut

Post by dirkse »

The cut equation you have:

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;
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
Post Reply