Integer cut

GAMS
1

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
Untitled_41.gms (851 Bytes)

2

Hi Rofice

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

Cheers
Renger

3

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

4

Hi Rofice

You could try something like this (and adjust it to your wishes):

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

5

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
solnpool.gms (678 Bytes)
cutting.gdx (4.33 KB)

6

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
Integer cut2.gms (1.99 KB)
Integer cut1.gms (1.66 KB)

7

Oops, here’s the cutting.gms file.
cutting.gms (1.45 KB)

8

The cut equation you have:

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