From 4f2818108e5f0b295e91381b730691fcdfb3516e Mon Sep 17 00:00:00 2001
From: Yann Herklotz <ymherklotz@gmail.com>
Date: Sun, 29 Oct 2017 13:13:10 +0000
Subject: Working prototype of simplex

---
 .clang-format        |  15 +++++++
 include/simplex.h    |  28 ++++++++++++
 src/simplex.cpp      | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 src/test_simplex.cpp |  19 ++++++++
 4 files changed, 179 insertions(+), 2 deletions(-)
 create mode 100644 .clang-format
 create mode 100644 src/test_simplex.cpp

diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..a4489c5
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,15 @@
+---
+BasedOnStyle: LLVM
+IndentWidth: 4
+---
+Language: Cpp
+AccessModifierOffset: -4
+AlignTrailingComments: true
+AllowShortFunctionsOnASingleLine: Inline
+AlwaysBreakTemplateDeclarations: true
+BreakBeforeBraces: Linux
+SortIncludes: true
+SpaceBeforeParens: ControlStatements
+UseTab: Never
+...
+
diff --git a/include/simplex.h b/include/simplex.h
index e69de29..22bf1e3 100644
--- a/include/simplex.h
+++ b/include/simplex.h
@@ -0,0 +1,28 @@
+#ifndef SIMPLEX_H
+#define SIMPLEX_H
+
+#include <vector>
+
+typedef std::vector<std::vector<double>> BasicRep;
+
+class Simplex
+{
+public:
+    Simplex(int m, int n);
+    Simplex(BasicRep basic_rep);
+
+    void initialize(BasicRep basic_rep);
+    void solve();
+    double getMin() const;
+private:
+    BasicRep basic_rep_;
+
+    bool isDone() const;
+    int inputBasicVar() const;
+    int outputBasicVar(int column) const;
+    void rotate(int input, int output);
+};
+
+extern void printBR(const BasicRep &basic_rep);
+
+#endif
diff --git a/src/simplex.cpp b/src/simplex.cpp
index 9039a3a..373f5b9 100644
--- a/src/simplex.cpp
+++ b/src/simplex.cpp
@@ -1,6 +1,121 @@
 #include <simplex.h>
 
-int main()
+#define DEBUG_LEVEL 2
+
+#if DEBUG_LEVEL > 0
+#include <iostream>
+#endif
+
+Simplex::Simplex(int m, int n) : basic_rep_(m, std::vector<double>(n, 0.0)) {}
+
+Simplex::Simplex(BasicRep basic_rep) : basic_rep_(basic_rep) {}
+
+void Simplex::initialize(BasicRep basic_rep)
+{
+    basic_rep_ = basic_rep;
+}
+
+void Simplex::solve()
+{
+#if DEBUG_LEVEL > 0
+    std::cout << "========== Starting Solve ==========\n";
+#endif
+    while (!isDone()) {
+#if DEBUG_LEVEL > 1
+        printBR(basic_rep_);
+#endif
+        int inputVar = inputBasicVar();
+        int outputVar = outputBasicVar(inputVar);
+
+        rotate(inputVar, outputVar);
+    }
+#if DEBUG_LEVEL > 0
+    std::cout << "========== Done Solve! ==========\n";
+#endif
+#if DEBUG_LEVEL > 1
+    printBR(basic_rep_);
+#endif
+}
+
+double Simplex::getMin() const
+{
+    return basic_rep_[0].back();
+}
+
+bool Simplex::isDone() const
+{
+    for (std::size_t i = 0; i < basic_rep_[0].size(); ++i) {
+        if (basic_rep_[0][i] > 0 && i != 0) {
+            return false;
+        }
+    }
+    return true;
+}
+
+int Simplex::inputBasicVar() const
+{
+    double max{0};
+    int ret_itr{0};
+    int itr{0};
+
+    for (auto &&var : basic_rep_[0]) {
+        if (var > max && itr != 0 &&
+            itr != static_cast<int>(basic_rep_[0].size() - 1)) {
+            max = var;
+            ret_itr = itr;
+        }
+        itr++;
+    }
+
+    return ret_itr;
+}
+
+int Simplex::outputBasicVar(int column) const
+{
+    double min{10000};
+    int ret_itr{0};
+    int itr{0};
+
+    for (auto &&bv : basic_rep_) {
+        double minVar{bv.back() / bv[column]};
+        if (minVar < min && itr != 0 && minVar > 0) {
+            min = minVar;
+            ret_itr = itr;
+        }
+        itr++;
+    }
+
+    return ret_itr;
+}
+
+void Simplex::rotate(int input, int output)
+{
+#if DEBUG_LEVEL > 0
+    std::cout << "Rotating on " << output << ", " << input << "\n";
+#endif
+    double pivot{basic_rep_[output][input]};
+    for (std::size_t i = 0; i < basic_rep_.size(); ++i) {
+        double mul{-basic_rep_[i][input] / pivot};
+        for (std::size_t j = 0; j < basic_rep_[i].size(); ++j) {
+            if (static_cast<int>(i) == output) {
+                basic_rep_[i][j] /= pivot;
+            } else {
+                basic_rep_[i][j] += mul * basic_rep_[output][j];
+            }
+        }
+    }
+}
+
+#if DEBUG_LEVEL > 1
+
+void printBR(const BasicRep &basic_rep)
 {
-    
+    for (auto &&bv : basic_rep) {
+        for (auto &&var : bv) {
+            std::cout << var << " ";
+        }
+        std::cout << "\n";
+    }
 }
+
+#endif
diff --git a/src/test_simplex.cpp b/src/test_simplex.cpp
new file mode 100644
index 0000000..ba177f8
--- /dev/null
+++ b/src/test_simplex.cpp
@@ -0,0 +1,19 @@
+#include <simplex.h>
+
+#include <iostream>
+
+int main()
+{
+    BasicRep br{
+        {1, 1, 1, 0, 0, 0, 0},
+        {0, 2, 1, 1, 0, 0, 11},
+        {0, 1, 3, 0, 1, 0, 18},
+        {0, 1, 0, 0, 0, 1, 4},
+    };
+
+    Simplex s{br};
+
+    s.solve();
+
+    std::cout << "Result: " << s.getMin() << "\n";
+}
-- 
cgit