search

coin-or / CyLP

A Python interface to CLP, CBC, and CGL to solve LPs and MIPs.
Other
182 stars 68 forks source link

Why the basis inverse for artifical variable at first iteration is the identity matrix? #172

Open dxyzx0 opened 1 year ago

dxyzx0 commented 1 year ago

From the code in OSI, I know that the artifical variable is defined as lb <= s <= ub, Ax - s = 0.

As a result, the basis matrix of the artificial variables s should be the -I instead of I(identity matrix), but in s.basisInverse, I still see I.

Can anyone explain this confusion?

tkralphs commented 1 year ago

Could you post a minimal script that shows exactly what you're doing?

dxyzx0 commented 1 year ago

I'm just trying to understand relationship and difference between the structural variables and artifical variables in CyLP.

Assume the problem is max c'x s.t. lA <= Ax <= uA, l <= x <= u. In CLP, the problem will become max c'x s.t. lA <= s <= uA, l <= x <= u, Ax = s. x are the structural variables and s are the artificial variables.

However, at the first iteration, I found that all the artifical variables are set to basic and with basisInverse same as the identity matrix, which is confused since the constraints are Ax - s = 0, the basisInverse of s should be -I instead of I.

I'm sure I make some mistakes. Can you help me about this?

tkralphs commented 1 year ago

Your understanding is pretty much correct, but precisely what should be expected is a function of the exact form of the problem you hand to CyLP, so I was asking you to post actual code that builds an instance and passes it to CyLP where things don't behave as you expect. Then I can try to see why. It's often some minor detail of the code that is important in explaining things like this.