HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations

Problems with modeling
Post Reply
anby
User
User
Posts: 6
Joined: 7 months ago

HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by anby » 1 month ago

So I am trying to implement an algorithm by augmenting with cuts after every iteration. The master problem is,

minimize w =-x - 10z
s.t.
-25x + 20z ≤ 30
x + 2z ≤ 10
2x - z ≤ 15
-2x - 10z ≤ -15
w >= -26
w <= -22
x is a nonnegative continuous variable, z is a nonnegative integer variable.

After the 1st iteration i want to add the constraints, 1 <= x <= 6 iff z<= 2
After the 2nd iteration I want to add the constraint, 2.5 <= x <= 8 iff z<= 1

These two constraints augmenting the problem essentially restricts the solution space yielding x=2, z=2 as the optimal solution.

I tried to add the two constraints "manually" with the following equations in my GAMS file. GAMS returned an error "Endogenous relational operations require model type "dnlp". It looks like I cannot use the value of a variable as a conditional to generate the cuts.

constrain15lt.. x =l= 6 $(z0 lt 2 );
constrain15gt.. x =g= 1 $(z0 lt 2 );
constrain15lt.. x =l= 8 $(z0 lt 1 );
constrain15gt.. x =g= 2.5 $(z0 lt 1 );

I am at a complete loss on how to add the augmented constraints. I am relatively new to GAMS. I will really appreciate if you can help me out. Thank you!

Anby
Last edited by anby on Fri Aug 17, 2018 9:31 pm, edited 3 times in total.

GabrielYin
User
User
Posts: 43
Joined: 6 months ago
Location: Dallas, TX, USA

Re: Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by GabrielYin » 1 month ago

Hi Anby,

First of all, your model is apparently infeasible because you have w <= 22 and w >= 26, which is contradictory.

Then the way you add your constraint is weird. But it is still doable in GAMS. I have written the code for you, which shows integer infeasible.

Code: Select all

Positive Variable x;
Integer Variable z;
Free Variable w;

Set      k       /1*3/;

Set cut1set(k);
cut1set(k) = no;

Set cut2set(k);
cut2set(k) = no;

Equations
         obj, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11;

obj..    w =e= - x - 10 *z;
c1..     -25 * x + 20 * z =l= 30;
c2..     x + 2 * z =l= 10;
c3..     2 * x - z =l= 15;
c4..     - 2 * x - 10 * z =l= - 15;
c5..     w =g= 26;
c6..     w =l= 22;
* z is nonnegative integer
c7..     z =g= 0;
c8(cut1set)..    x =l= 6;
c9(cut1set)..    x =g= 1;
c10(cut2set)..   x =l= 8;
c11(cut2set)..   x =g= 2.5;

Model mymodel /all/;

loop(k,
         solve mymodel use mip min w;

         if(ord(k) = 1 and z.l <= 2,
                 cut1set(k) = yes;
         );
         if(ord(k) = 2 and z.l <= 1,
                 cut2set(k) = yes;
         );
);
Note that in the 3rd iteration, cut1set constraints will remain in the model.

Hope it helps.

Gabriel

anby
User
User
Posts: 6
Joined: 7 months ago

Re: Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by anby » 1 month ago

GabrielYin wrote:
1 month ago
Hi Anby,

First of all, your model is apparently infeasible because you have w <= 22 and w >= 26, which is contradictory.

Then the way you add your constraint is weird. But it is still doable in GAMS. I have written the code for you, which shows integer infeasible.
Hello Gabriel,

Thank you for your response. I had made mistakes. I forgot the minus signs in the lower and upper bounds of variable w, and said if instead of iff in the augmented constraints. I have corrected it with, w >= -26 and w <= -22. I will read up on dynamic sets and how to use them.

I ran your script and it is giving me the solution of (x=6, z=2). However, from the constraint added after the 2nd iteration (2.5 <= x <= 8 iff z<= 1) x cannot be equal to 6 as z is not less than or equal to 1. What can I do to enforce that ?

Thanks,

Anby

GabrielYin
User
User
Posts: 43
Joined: 6 months ago
Location: Dallas, TX, USA

Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by GabrielYin » 1 month ago

I can't understand. As you say, the 3rd iteration constraint "2.5 <= x <= 8" will be added iff z result in the 2nd iteration is <= 1, but z reaches its optimum 2 in 2nd iteration. So the constraint will not be triggered. You can observe the Equation list in .lst file to check the constraints appeared in each iteration. It shows that the 2nd iteration constraint "1 <= x <= 6" have been triggered in 2nd and 3rd iteration because z satisfies your condition "z <= 2". Please clarify your aim.

Best,
Gabriel

anby
User
User
Posts: 6
Joined: 7 months ago

Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by anby » 1 month ago

GabrielYin wrote:
1 month ago
I can't understand. As you say, the 3rd iteration constraint "2.5 <= x <= 8" will be added iff z result in the 2nd iteration is <= 1, but z reaches its optimum 2 in 2nd iteration. So the constraint will not be triggered. You can observe the Equation list in .lst file to check the constraints appeared in each iteration. It shows that the 2nd iteration constraint "1 <= x <= 6" have been triggered in 2nd and 3rd iteration because z satisfies your condition "z <= 2". Please clarify your aim.

Best,
Gabriel
Hi Gabriel,

I apologize for not being clear. The problem here was originally a bilevel mixed integer optimization problem, which I was trying to solve with a recently published algorithm. Instead of putting the whole algorithm with master problem and sub-problems here and making the question super long, I mentioned just the bounds, two cuts and the set of equations which when applied gives the correct solution. The correct solution to the problem is (X=2, Z=2), which is obtained with the bounds on objective value, the original constraints, and the two cuts.

The cuts here are generated after each iteration and added progressively to the master problem. After the 1st iteration the cut of 1 <= x <= 6 iff z<= 2 is generated, which is not sufficient according to the algorithm in the second iteration and generates the second cut, and evaluates the bounds. After the 2nd iteration the cut of 2.5 <= x <= 8 iff z<= 1 is generated along with the bounds of w >= -26, and w <= -22. I just mentioned the entire set of constraints (& cuts) that finally solver the problem.

The two cuts of 1 <= x <= 6 iff z<= 2 and 2.5 <= x <= 8 iff z<= 1 essentially should leave (2,2) as the only feasible point and the final solution. If I just stack the constraints on top of the master problem (x=6,z=2) is the solution, which fulfills the constraints. However, the solution of (x=6, z=2) is not correct as z must be less than or equal to 1 if 2.5 <= x <= 8.

My question is, how do I enforce that relationship between the variable values ?

On another note is (1 <= x <= 6) <=> (z<= 2) and (2.5 <= x <= 8) <=> (z <= 1) a better way of expressing the relationships ?

Anby

GabrielYin
User
User
Posts: 43
Joined: 6 months ago
Location: Dallas, TX, USA

Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations

Post by GabrielYin » 1 month ago

anby wrote:
1 month ago
GabrielYin wrote:
1 month ago
I can't understand. As you say, the 3rd iteration constraint "2.5 <= x <= 8" will be added iff z result in the 2nd iteration is <= 1, but z reaches its optimum 2 in 2nd iteration. So the constraint will not be triggered. You can observe the Equation list in .lst file to check the constraints appeared in each iteration. It shows that the 2nd iteration constraint "1 <= x <= 6" have been triggered in 2nd and 3rd iteration because z satisfies your condition "z <= 2". Please clarify your aim.

Best,
Gabriel
Hi Gabriel,

I apologize for not being clear. The problem here was originally a bilevel mixed integer optimization problem, which I was trying to solve with a recently published algorithm. Instead of putting the whole algorithm with master problem and sub-problems here and making the question super long, I mentioned just the bounds, two cuts and the set of equations which when applied gives the correct solution. The correct solution to the problem is (X=2, Z=2), which is obtained with the bounds on objective value, the original constraints, and the two cuts.

The cuts here are generated after each iteration and added progressively to the master problem. After the 1st iteration the cut of 1 <= x <= 6 iff z<= 2 is generated, which is not sufficient according to the algorithm in the second iteration and generates the second cut, and evaluates the bounds. After the 2nd iteration the cut of 2.5 <= x <= 8 iff z<= 1 is generated along with the bounds of w >= -26, and w <= -22. I just mentioned the entire set of constraints (& cuts) that finally solver the problem.

The two cuts of 1 <= x <= 6 iff z<= 2 and 2.5 <= x <= 8 iff z<= 1 essentially should leave (2,2) as the only feasible point and the final solution. If I just stack the constraints on top of the master problem (x=6,z=2) is the solution, which fulfills the constraints. However, the solution of (x=6, z=2) is not correct as z must be less than or equal to 1 if 2.5 <= x <= 8.

My question is, how do I enforce that relationship between the variable values ?

On another note is (1 <= x <= 6) <=> (z<= 2) and (2.5 <= x <= 8) <=> (z <= 1) a better way of expressing the relationships ?

Anby
As far as I know, there is no direct way to enforce the mutual relationships between x and z about dynamic constraints. One thing you can try is to define 4 dynamic sets, namely cut1set, cut2set, cut3set and cut4set, which represent each pair of constraints and use 4 if statements to achieve this. If all constraints in the current iteration are updated w.r.t the solution of the previous iteration, which means "a priori", it is fine. Specifically, let me try to understand your way.

In first iteration, no additional constraint is triggered, which renders (6,2) as optima. Then in the second iteration, these optima satisfy both conditions ("1 <= x <= 6" and "z <= 2"), and thus two constraints will be triggered. But the optima remain the same since these new added constraints do not bind them. In the third iteration, these optima satisfy one condition ("2.5 <= x <= 8"), and thus one constraint will be triggered ("z <= 1"). Now we have three additional constraints in our model ("1 <= x <= 6", "z <= 2", "z <= 1"). But in this iteration the result is infeasible. The modified code is below.

Code: Select all

Positive Variable x;
Integer Variable z;
Free Variable w;

Set      k       /1*3/;

Set cut1set(k);
cut1set(k) = no;

Set cut2set(k);
cut2set(k) = no;

Set cut3set(k);
cut3set(k) = no;

Set cut4set(k);
cut4set(k) = no;

Equations
         obj, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13;

obj..    w =e= - x - 10 *z;
c1..     -25 * x + 20 * z =l= 30;
c2..     x + 2 * z =l= 10;
c3..     2 * x - z =l= 15;
c4..     - 2 * x - 10 * z =l= - 15;
c5..     w =g= - 26;
c6..     w =l= - 22;
* z is nonnegative integer
c7..     z =g= 0;
c8(cut1set)..    x =l= 6;
c9(cut1set)..    x =g= 1;
c10(cut3set)..   x =l= 8;
c11(cut3set)..   x =g= 2.5;
c12(cut2set)..   z =l= 2;
c13(cut4set)..   z =l= 1;

Model mymodel /all/;

loop(k,
         solve mymodel use mip min w;

         if(ord(k) = 1 and z.l <= 2,
                 cut1set(k) = yes;
         );
         if(ord(k) = 1 and x.l <= 6 and x.l >= 1,
                 cut2set(k) = yes;
         );
         if(ord(k) = 2 and z.l <= 1,
                 cut3set(k) = yes;
         );
         if(ord(k) = 2 and x.l <= 8 and x.l >= 2.5,
                 cut4set(k) = yes;
         );
);
Though I guess I still misunderstand your theory, but it is doable in this way if your dynamic constraints are generated a priori. Just use the dynamic set to achieve your goal.

Hope it helps.
Gabriel

Post Reply