search

fslaborg / flips

Fsharp LInear Programming System
https://flipslibrary.com/#/
MIT License
251 stars 32 forks source link

Correctness of evaluateNode #149

Closed TysonMN closed 3 years ago

TysonMN commented 3 years ago

I am suspicious of the correctness of evaluateNode. Unfortunately I still lack sufficient understanding to either convince myself that it is correct or be confident enough to know the correct behavior.

https://github.com/fslaborg/flips/blob/16a347c18cbfd7eb4c12d6c57dea31b56dd7b54d/Flips/Types.fs#L236-L254

I am surprised by the implementation of the AddLinearExpression case on line 251.

https://github.com/fslaborg/flips/blob/16a347c18cbfd7eb4c12d6c57dea31b56dd7b54d/Flips/Types.fs#L250-L251

The multiplier used in the continuation is the multiplier returned from recursing into the left expression. This could be different if that branch of the expression includes a Multiply case. Eventually the Empty case executes the continuation by passing in the multiplier it was given.

To see what I mean, consider the LinearExpression

Multiply (2.0, AddFloat (2.0, Empty)) + AddFloat (2.0, Empty)

The floats returned for it by evaluateNode are [ 4.0; 4.0 ], but I was expecting [ 4.0; 2.0 ] because I didn't think the Multiply on the left should change what the right returns (which would have been [ 2.0 ]).

The implementation I expected to see is

| AddLinearExpression (lExpr, rExpr) ->
    evaluateNode (multiplier, state) lExpr (fun _ -> evaluateNode (multiplier, state) rExpr cont)

Is this a bug? If not, why is this the correct behavior?

TysonMN commented 3 years ago

Duplicate of #148.

Sorry. GitHub glitched out on me.