fixed simplex

hitonanode · hitonanode · commit 9de21c807cfe · 2021-02-28T16:53:36.000+09:00
diff --git a/combinatorial_opt/simplex.hpp b/combinatorial_opt/simplex.hpp
@@ -120,7 +120,7 @@ template <typename Float = double, int DEPS = 30, bool Randomize = true> struct
         _initialize(A, b, c);
         _solve();
 
-        if (Randomize) {
+        if (Randomize and x.size() == c.size()) {
             auto xtmp = x;
             for (unsigned j = 0; j < c.size(); j++) x[shuffle_idx[j]] = xtmp[j];
         }
diff --git a/combinatorial_opt/simplex.md b/combinatorial_opt/simplex.md
@@ -67,10 +67,11 @@ $
   - さもなくば原点が実行可能領域から飛び出るので
   - 複数存在する場合は添字番号最小（Bland's rule）
 
-#### ワーストケースの回避
+### ワーストケースの回避
 
 - 指数回のステップを要する恣意的なケースが知られている．
 - 特に [1] の p.43 (2.71) で挙げられているケースに関しては，変数・制約の順序をランダムに取り換えることで回避が可能であることを経験的に確認したので，デフォルトでこれを行うことにした．
+- ただし，常にシャッフルした方がよいわけではなく，[最小費用流の問題](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B) ではむしろ遅くなった．
 
 ## 問題例
 
diff --git a/combinatorial_opt/test/simplex.mcf.test.cpp b/combinatorial_opt/test/simplex.mcf.test.cpp
@@ -24,6 +24,6 @@ int main() {
         b.push_back(cap);
         c.push_back(-cost);
     }
-    Simplex<Float, 20> simplex(A, b, c);
+    Simplex<Float, 20, false> simplex(A, b, c);
     cout << (simplex.infeasible ? -1 : -llround(simplex.ans)) << '\n';
 }

Original file line number	Diff line number	Diff line change
`@@ -120,7 +120,7 @@ template <typename Float = double, int DEPS = 30, bool Randomize = true> struct`
`120`	`120`	`_initialize(A, b, c);`
`121`	`121`	`_solve();`
`122`	`122`
`123`		`- if (Randomize) {`
	`123`	`+ if (Randomize and x.size() == c.size()) {`
`124`	`124`	`auto xtmp = x;`
`125`	`125`	`for (unsigned j = 0; j < c.size(); j++) x[shuffle_idx[j]] = xtmp[j];`
`126`	`126`	`}`
Original file line number	Diff line number	Diff line change
`@@ -24,6 +24,6 @@ int main() {`
`24`	`24`	`b.push_back(cap);`
`25`	`25`	`c.push_back(-cost);`
`26`	`26`	`}`
`27`		`- Simplex<Float, 20> simplex(A, b, c);`
	`27`	`+ Simplex<Float, 20, false> simplex(A, b, c);`
`28`	`28`	`cout << (simplex.infeasible ? -1 : -llround(simplex.ans)) << '\n';`
`29`	`29`	`}`