src/simplex.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include <simplex.h>

#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