Varying results depending on packed mode for CoinIndexedVector

[choidami]

I was playing around with the pivotColumn function in the Dantzig pivot class and I found that the reduced costs computed using getBInvRow and the updated reduced costs in the pivotColumn class was different after a few steps on a simple problem.

After some digging, I found that these two lines of code

model_->factorization()->updateColumnTranspose(spareRow2, updates);
model_->clpMatrix()->transposeTimes(model_, -1.0, updates, spareColumn2, spareColumn1);

produce a different spareColumn1 vector depending on whether updates is in packed mode or not. For example, for

A = [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
updates_after_line_1 = [6, 0, -6]

then the result should be

spareColumn1 = [6, 0, -6]

But I get

spareColumn1 = [6, 0, 0]

Is this an expected behaviour?

The problem I was testing on was

A = ([[1, 2, 2], [2, 1, 2], [2, 2, 1]])
b = CyLPArray([20, 20, 20])
c = CyLPArray([-10, -12, -12])

Minimize c^T x
subject to Ax <= b and x >= 0

[jjhforrest]

updates_after_line_1 = [6, 0, -6] |

is an invalid CoinIndexedVector in packed mode.

On 25/09/2020 08:58, Dami Choi wrote:

I was playing around with the pivotColumn function in the Dantzig pivot class https://projects.coin-or.org/Clp/browser/trunk/src/ClpPrimalColumnDantzig.cpp#L58 and I found that the reduced costs computed using getBInvRow and the updated reduced costs in the pivotColumn class was different after a few steps on a simple problem.

After some digging, I found that these two lines of code https://projects.coin-or.org/Clp/browser/trunk/src/ClpPrimalColumnDantzig.cpp#L80

|model_->factorization()->updateColumnTranspose(spareRow2, updates); model_->clpMatrix()->transposeTimes(model_, -1.0, updates, spareColumn2, spareColumn1); |

produce a different spareColumn1 vector depending on whether updates is in packed mode or not. For example, for

|A = [[1, 2, 2], [2, 1, 2], [2, 2, 1]] updates_after_line_1 = [6, 0, -6] |

then the result should be

|spareColumn1 = [6, 0, -6]|

But I get

|spareColumn1 = [6, 0, 0]|

Is this an expected behaviour?

The problem I was testing on was

|A = ([[1, 2, 2], [2, 1, 2], [2, 2, 1]]) b = CyLPArray([20, 20, 20]) c = CyLPArray([-10, -12, -12]) Minimize c^T x subject to Ax <= b and x >= 0 |

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Clp/issues/162, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHB24YLV2KURWAC7GRTSHRERHANCNFSM4RZHKJBA.

[choidami]

Sorry, why is it an invalid CoinIndexedVector in packed mode? When I print the dense vector, I get [-6, 6] with indices [2, 0].

[jjhforrest]

Apologies - I misunderstood how you were describing vector.

The correct answer is that the code does not compute entries for basic variables.

John Forrest On 25/09/2020 17:15, Dami Choi wrote:

Sorry, why is it an invalid CoinIndexedVector in packed mode? When I print the dense vector, I get [-6, 6] with indices [2, 0].

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/coin-or/Clp/issues/162#issuecomment-699020120, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHB6NJD57DLKHDCUQ6TSHS63VANCNFSM4RZHKJBA.

[choidami]

I'm sorry for being slow, but could you please elaborate? My main confusion is that whether updates is packed or not, the final output should be the same, but it's not.

If the code doesn't compute entries for basic variables, then how are the updated reduced costs going to be accurate? It might not matter in the current iteration, since we're not choosing among the basic variables, but what happens when that basic variable leaves and becomes non-basic? Or is the dj_ variable updated outside of the pivotColumn class to prevent this from happening?