Page 1 of 1

Integer cut

Posted: Tue Jul 09, 2019 2:59 pm
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

Re: Integer cut

Posted: Tue Jul 09, 2019 8:09 pm
by Renger
Hi Rofice

Did you see this example https://www.gams.com/latest/gamslib_ml/ ... _icut.html?

Cheers
Renger

Re: Integer cut

Posted: Wed Jul 10, 2019 5:48 am
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

Re: Integer cut

Posted: Wed Jul 10, 2019 8:00 am
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

Re: Integer cut

Posted: Wed Jul 10, 2019 10:03 pm
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

Re: Integer cut

Posted: Thu Jul 11, 2019 5:12 am
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

Re: Integer cut

Posted: Thu Jul 11, 2019 5:29 pm
by dirkse
Oops, here's the cutting.gms file.

Re: Integer cut

Posted: Thu Jul 11, 2019 5:36 pm
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