Marginal value of variable strangely equaling zero!

GAMS
1

Dear GAMS experts,

Hi. I am implementing a Column Generation algorithm, which necessitates adding to the model the non-basic variables which have appropriate reduced costs, and solving the model again. To do this, I need to know the reduced costs of some variables which are not currently in my model (so they are non-basic ones). For that, you may assume the model encompasses 10 variables at the moment, and there are 20 more which are not in the model now, and we need to check their reduced costs, find a variable with a negative reduced cost, and add it to the model to solve again.
I have attached one of the iterations of the model. In it, x(16) is the variable I want to check its reduced cost; so although it is in the codes, it does not actually exist in the model; I just added it to the model with a value of zero (to remain a non-basic variable) in order to check its reduced cost. Then I found a marginal value of zero for it, so I expected no change in the objective function if it became a basic variable.
Then I did this, by changing constraint “zero” to be equal to “1”:

zero…(sum(j$(ord(j) ge 16 and ord(j) le 16),x(j))) =E= 1;

To my surprise, the objective function changed and improved for about 5E+6 units! I even checked it in MATLAB and the value of objective function improved to the same amount; so I am wondering why the marginal value of this variable wasn’t equal to -5E+6 (when I had forced the variable to take a value of zero)? Why did GAMS show zero for its marginal value?!?
What do you think about this paradox? Could it be due to degeneracy? I mean, x(16) was a basic variable even when it had a value of zero…
If this is so, is there a way in GAMS to push this variable out of the base, and force it to be a non-basic one? Because I need to find the reduced cost for this variable as a “non-basic” one, and according to the sign of the reduced cost, decide whether to add the variable to the problem or not.
I appreciate any help in advance.

With best regards,
Morianta

–
Test_37_70.gms (14.6 KB)

2

Morianta,

You find a very negative dual on the constraint that fix your variable 16 to 0 (equation zero). In a “normal” CG algorithm you do not have the variable at all in the model, so you can’t read the dual of a non-existing variable from GAMS via .m, but you might find a new variable with reduced cost less than 0 if you know where the non-zeros of the variable enter your constraint matrix and by looking at the duals of the equation. There is a simple CG model in the GAMS Model Library (http://gams.com/modlib/libhtml/cutstock.htm) that demonstrates this. I also modified your code that starts with a subset of columns (jj) and solves the corresponding LP and computes the reduced cost of the columns not in jj and adds the most negative to the problem. The reduces cost are calculated using the dual from the previous solve of the master and the matrix/obj coefficients of the to-be-added column.

Hope this helps,
Michael Bussieck - GAMSWorld Coordinator

On Friday, September 5, 2014 6:35:34 PM UTC-4, Morianta wrote:

Dear GAMS experts,

Hi. I am implementing a Column Generation algorithm, which necessitates adding to the model the non-basic variables which have appropriate reduced costs, and solving the model again. To do this, I need to know the reduced costs of some variables which are not currently in my model (so they are non-basic ones). For that, you may assume the model encompasses 10 variables at the moment, and there are 20 more which are not in the model now, and we need to check their reduced costs, find a variable with a negative reduced cost, and add it to the model to solve again.
I have attached one of the iterations of the model. In it, x(16) is the variable I want to check its reduced cost; so although it is in the codes, it does not actually exist in the model; I just added it to the model with a value of zero (to remain a non-basic variable) in order to check its reduced cost. Then I found a marginal value of zero for it, so I expected no change in the objective function if it became a basic variable.
Then I did this, by changing constraint “zero” to be equal to “1”:

zero…(sum(j$(ord(j) ge 16 and ord(j) le 16),x(j))) =E= 1;

To my surprise, the objective function changed and improved for about 5E+6 units! I even checked it in MATLAB and the value of objective function improved to the same amount; so I am wondering why the marginal value of this variable wasn’t equal to -5E+6 (when I had forced the variable to take a value of zero)? Why did GAMS show zero for its marginal value?!?
What do you think about this paradox? Could it be due to degeneracy? I mean, x(16) was a basic variable even when it had a value of zero…
If this is so, is there a way in GAMS to push this variable out of the base, and force it to be a non-basic one? Because I need to find the reduced cost for this variable as a “non-basic” one, and according to the sign of the reduced cost, decide whether to add the variable to the problem or not.
I appreciate any help in advance.

With best regards,
Morianta

–
Test_37_70.gms (14.6 KB)

3

Mr. Bussieck,

That was a real help; I learnt new things especially from the changed code you had attached. Thanks for your attention.

With best regards,
Morianta

On Monday, September 8, 2014 2:02:46 AM UTC-7, Michael Bussieck wrote:

Morianta,

You find a very negative dual on the constraint that fix your variable 16 to 0 (equation zero). In a “normal” CG algorithm you do not have the variable at all in the model, so you can’t read the dual of a non-existing variable from GAMS via .m, but you might find a new variable with reduced cost less than 0 if you know where the non-zeros of the variable enter your constraint matrix and by looking at the duals of the equation. There is a simple CG model in the GAMS Model Library (http://gams.com/modlib/libhtml/cutstock.htm) that demonstrates this. I also modified your code that starts with a subset of columns (jj) and solves the corresponding LP and computes the reduced cost of the columns not in jj and adds the most negative to the problem. The reduces cost are calculated using the dual from the previous solve of the master and the matrix/obj coefficients of the to-be-added column.

Hope this helps,
Michael Bussieck - GAMSWorld Coordinator

On Friday, September 5, 2014 6:35:34 PM UTC-4, Morianta wrote:

Dear GAMS experts,

Hi. I am implementing a Column Generation algorithm, which necessitates adding to the model the non-basic variables which have appropriate reduced costs, and solving the model again. To do this, I need to know the reduced costs of some variables which are not currently in my model (so they are non-basic ones). For that, you may assume the model encompasses 10 variables at the moment, and there are 20 more which are not in the model now, and we need to check their reduced costs, find a variable with a negative reduced cost, and add it to the model to solve again.
I have attached one of the iterations of the model. In it, x(16) is the variable I want to check its reduced cost; so although it is in the codes, it does not actually exist in the model; I just added it to the model with a value of zero (to remain a non-basic variable) in order to check its reduced cost. Then I found a marginal value of zero for it, so I expected no change in the objective function if it became a basic variable.
Then I did this, by changing constraint “zero” to be equal to “1”:

zero…(sum(j$(ord(j) ge 16 and ord(j) le 16),x(j))) =E= 1;

To my surprise, the objective function changed and improved for about 5E+6 units! I even checked it in MATLAB and the value of objective function improved to the same amount; so I am wondering why the marginal value of this variable wasn’t equal to -5E+6 (when I had forced the variable to take a value of zero)? Why did GAMS show zero for its marginal value?!?
What do you think about this paradox? Could it be due to degeneracy? I mean, x(16) was a basic variable even when it had a value of zero…
If this is so, is there a way in GAMS to push this variable out of the base, and force it to be a non-basic one? Because I need to find the reduced cost for this variable as a “non-basic” one, and according to the sign of the reduced cost, decide whether to add the variable to the problem or not.
I appreciate any help in advance.

With best regards,
Morianta

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.