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
HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations
HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations
Last edited by anby 6 months ago, edited 3 times in total.

 User
 Posts: 54
 Joined: 11 months ago
 Location: Dallas, TX, USA
Re: Augmenting master problem with cuts: GAMS does not permit conditional equations
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.
Note that in the 3rd iteration, cut1set constraints will remain in the model.
Hope it helps.
Gabriel
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;
);
);
Hope it helps.
Gabriel
Re: Augmenting master problem with cuts: GAMS does not permit conditional equations
Hello Gabriel,GabrielYin wrote: ↑6 months agoHi 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.
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

 User
 Posts: 54
 Joined: 11 months ago
 Location: Dallas, TX, USA
Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations
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
Best,
Gabriel
Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations
Hi Gabriel,GabrielYin wrote: ↑6 months agoI 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
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 subproblems 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

 User
 Posts: 54
 Joined: 11 months ago
 Location: Dallas, TX, USA
Re: HELP! Augmenting master problem with cuts: GAMS does not permit conditional equations
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.anby wrote: ↑6 months agoHi Gabriel,GabrielYin wrote: ↑6 months agoI 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
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 subproblems 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
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;
);
);
Hope it helps.
Gabriel