Originally posted by: Timothy_Chow

I have an LP in standard form, i.e., all the constraints are equality constraints.  I solved it with the simplex method and used CPXgetbase to get the basis.  I was expecting all the basic variables to be associated with columns, but to my surprise, some of the basic variables were associated with rows (i.e., the rstat array was not all zero).  This surprised me, and I am unsure what this means.  I understand that for an inequality, there is an implicit slack variable that measures the difference between the two sides, and I understand what it would mean for this slack variable to be a basic variable, but what precisely is the definition of an artificial or slack variable for an equality?  In particular, what does it mean for it to be a basic variable?  Is it always possible to drive such variables out of the basis with CPXpivot?

I also have a related but slightly different question.  Is there a way to find out the reduced cost associated to a slack or artificial variable?  The CPXgetdj documentation seems to be unclear on this point.

Originally posted by: T_O

I guess this has something to do with degeneracy. Of course, an artificial variable can be basic but take 0 as value.

Imagine the trivial constraint:

0x + 0y = 0

Then of course, you need some basis variable for this constraint. So the slack variable will be basic Here we call it artificial variable. Just imagine the equality as

0x + 0y + 1s = 0

with 0 <= s <= 0.

In this case you will not be able to pivot out the artificial variable.

I hope this is not too comfusing.

Best regards,
Thomas

Originally posted by: Timothy_Chow

Thanks for the reply.  I'm not sure I fully understand.  Are you saying that if my system of equations in standard form is linearly dependent, with (for example) m rows but rank r < m, then the simplex algorithm will still try to create a basis of size m by introducing artificial variables if necessary?

Also, could you please give an example where the artificial variable associated with an equality constraint CAN be pivoted out?  That is what is happening in my system, but I don't fully understand what is happening or why.

Originally posted by: T_O

Concerning your first question: I think, artificial variables are created for every equality constraint. I'm not sure whether preprocessing might eliminate them, but that should not matter. Just think that there is one artificial variable for every equality constraint. The rank does not matter here.

Concerning your second question: Imagine the following constraint:

1*y = 0

with 0 <= y <= 0.

Then there will be an artificial variable s, the problem is transfered to:

1*y + 1*s = 0

with 0 <= y <= 0 and 0 <= s <= 0. Then it does not matter whether y or s is basic.

Best regards,
Thomas

Thomas is correct about how/why an artificial variable might show up in the basis. If you want more detail, you might try searching for the "two-phase simplex method".

Regarding the reduced cost of an artificial variable (or slack), if the variable is basic, the reduced cost is automatically zero. Otherwise, the reduced cost equals the dual multiplier/shadow price of the constraint in which it appears.

Paul