Maybe glitch in simplex solver when choosing subject?

[starwing]

Hi,

I'm studying with this library by rewriting a new Lua version of Cassowary algorithm. It's real good example of how to use C++11 to write neat code. but I think maybe I found a little glitch in simplex_solver.cpp#L532:

               // v is restricted.  If we have already found a suitable
                // restricted variable just stick with that.  Otherwise, if v
                // is new to the solver and has a negative coefficient pick
                // it.  Regarding being new to the solver -- if the variable
                // occurs only in the objective function we regard it as being
                // new to the solver, since error variables are added to the
                // objective function when we make the Expression.  We also
                // never pick a dummy variable here.
                if (!found_new_restricted && !v.is_dummy() && c < 0.0) {
                    auto i(columns_.find(v));
                    if (i == columns_.end()
                        || (columns_.size() == 1
                            && columns_has_key(objective_))) {
                        subj = v;
                        found_new_restricted = true;
                    }
                }

If I'm not misunderstanding, columns_ is a map with the parameter variable and the set of basic variable which expression contain this parameter variable. so to see the v is only occurs in objective function, maybe we should found objective_ in *i, which is the basic variable set, but not in columns_ mapping.

[hfossli]

Unrelated to this issue, but fyi: there's a branch named 0.3 which is a big rewrite of the codebase.

[starwing]

@hfossli, thanks for that information! I'm now implement my own module with look into both source. old and new.

but I have a issue, the function suggest_value, in master branch, when eplus is basic variable, it adds delta, and when eminus is basic variable, it substract delta, but the new branch has the opposite operations. and master branch saves constant as prev_constant, but the new branch saves -constant.

could you kindly help me about the difference about the new branch and the old? (especially the sign problem :(

[hfossli]

0.3 is a big simplification and performance improvement. Inspired by some of the changes to the cassowary implementation made here https://github.com/nucleic/kiwi

I don't have any insight about the sign problem, but I would suggest having a look at other implementations of the algorithm as well.

@Nocte- will have to answer details.

[hfossli]

A list of different implementations can be found here http://overconstrained.io/

[starwing]

Yes, I did find this library on overconstrainted.io :)

but sorry for helping, I have some troubles about the dual_optimize() algorithm. I'm trying the example in paper uist97, but I found a order issue in dual_optimize.

in paper, the constraints are:

2*xm == xl + xr -- mark by d4 below
xr <= xl + 10  -- mark by s5
xr <= 100 -- mark by s6
xl >= 0 -- mark by s7

and I'm trying to edit variable xm, using solver.add_edit_var(xm); solver.suggest_value(xm, 70).

first, the initialized solver like this:

 ----- SimplexSolver info -----
  objective Exp: 0
  rows:
  1. xr(100):   Exp: 100 - s6
  2. xm(95):    Exp: 95 - s6 - 0.5*s5 - 0.5*d4
  3. xl(90):    Exp: 90 - s5 - 1*s6
  4. s7(0): Exp: 90 - s5 - s6
 ----------------------------

after add_edit_var, it changes to this:

 ----- SimplexSolver info -----
  objective Exp: 5e+06 + 1e+06*s7 + 500000*s5 - 500000*d4 + 2e+06*em9
  rows:
  1. xr(10):    Exp: 10 + s5 + s7
  2. xm(5): Exp: 5 + s7 + 0.5*s5 - 0.5*d4
  3. xl(0): Exp: 0 + s7
  4. s6(0): Exp: 90 - 1*s5 - 1*s7
  5. ep8(0):    Exp: 5 + s7 + 0.5*s5 - 0.5*d4 + em9
 edits:
  1. xm(5.0) { Var(slack): ep8(0), Var(slack): em9(0), 0 }
 ----------------------------

correct result, but when I suggest_value(xm, 70), solver changes to that:

 ----- SimplexSolver info -----
  objective Exp: 5e+06 + 1e+06*s7 + 500000*s5 - 500000*d4 + 2e+06*em9
  rows:
  1. xr(10):    Exp: 10 + s5 + s7
  2. xm(5): Exp: 5 + s7 + 0.5*s5 - 0.5*d4
  3. xl(0): Exp: 0 + s7
  4. s6(0): Exp: 90 - 1*s5 - 1*s7
  5. ep8(0):    Exp: -65 + s7 + 0.5*s5 - 0.5*d4 + em9
 edits:
  1. xm(5.0) { Var(slack): ep8(0), Var(slack): em9(0), 70 }
 infeasible_rows: ep8
 ----------------------------

note that ep8 has a negetive constant, so dual_optimize is performed. but surprise! if we choose s7 as a enter variable, (ep8 is always the leaving variable), all is well, I get correct result:

 ----- SimplexSolver info -----
  objective Exp: 7e+07 + 1e+06*em9 + 1e+06*ep8
  rows:
  1. xr(75):    Exp: 75 - 1*em9 + 0.5*s5 + ep8 + 0.5*d4
  2. xm(70):    Exp: 70 - 1*em9 + ep8
  3. xl(65):    Exp: 65 + 0.5*d4 - 1*em9 - 0.5*s5 + ep8
  4. s6(0): Exp: 25 + em9 - 0.5*s5 - 1*ep8 - 0.5*d4
  5. s7(0): Exp: 65 - 1*em9 - 0.5*s5 + ep8 + 0.5*d4
 edits:
  1. xm(70.0) { Var(slack): ep8(0), Var(slack): em9(0), 70 }
 ----------------------------

BUT, if I choose s5 as entering variable, it will cause another infeasible rows:

----- SimplexSolver info -----
  objective Exp: 7e+07 + 1e+06*em9 + 1e+06*ep8
  rows:
  1. xm(5):     Exp: 70 - 1*em9 + ep8
  2. xr(10):    Exp: 140 - 2*em9 - 1*s7 + d4 + 2*ep8
  3. xl(0):     Exp: 0 + s7
  4. s5(0):     Exp: 130 - 2*em9 - 2*s7 + 2*ep8 + d4
  5. s6(0):     Exp: -40 + 2*em9 + s7 - 1*d4 - 2*ep8
 edits:
  1. xm(5.0) { Var(slack): ep8(0), Var(slack): em9(0), 70 }
 infeasible_rows: s6
 ----------------------------

and resulting a wrong result:

 ----- SimplexSolver info -----
  objective Exp: 7e+07 + 1e+06*em9 + 1e+06*ep8
  rows:
  1. xm(70):    Exp: 70 - 1*em9 + ep8
  2. xr(100):   Exp: 100 - 1*s6
  3. xl(40):    Exp: 40 + s6 - 2*em9 + 2*ep8 + d4
  4. s5(0):     Exp: 50 - 2*s6 + 2*em9 - 2*ep8 - 1*d4
  5. s7(0):     Exp: 40 + s6 - 2*em9 + d4 + 2*ep8
 edits:
  1. xm(70.0) { Var(slack): ep8(0), Var(slack): em9(0), 70 }
 ----------------------------

notice that s5 and s7 have the same ratio when choosing, and expression is a hash-table, so each one has possibility to choose as a entering variable. I have debugged this issue for whole night. could someone helps? thanks for reading such a long and boring data sheets :(

[Nocte-]

Thanks for the thorough analysis @starwing! I'll look into this.

[starwing]

@Nocte- this should not be a glitch, because xl + 10 >= xr, so 40, 70, 100 is legal :(

I have made a pure C version of cassowary implement, maybe you interesting it: https://github.com/starwing/amoeba

and I found the change_strength may have mistake, you should use coefficient *= strength/old_strength in update error variables, but not add diff directly, because error variable may have non 1.0 coefficient.

[Nocte-]

@starwing Indeed, it's not a bug after all.

Nice project, I like the Lua bindings! A (C)Makefile would be convenient. :)

Are you sure about the coefficient? In the original implementation, the term with the old coefficient is first subtracted from the expression, and the new term is then added back. I'm just doing it in one go here.

[starwing]

@Nocte- yes, you're right. I notice you use add() function, but not normal add term to objective. I will change my implement :( p.s. if add modify coefficient in baisc variable, to mutiple is also right, but that may bad than only add/muinus.