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)