Simplex/SimplexSolver.cpp at master · armytrong/Simplex · GitHub

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
//
// Created by jgier on 25.05.2022.
//

#include <cassert>
#include "SimplexSolver.h"
#include "LinearProgram.h"

State SimplexSolver::solve() {
    SimplexTableau tableau = create_extended_simplex_tableau();
    State state;
    //tableau.print();
    while((state = tableau.iterate()) == SOLVED){
        //tableau.print();
    }
    assert(state == OPTIMAL && "The auxiliary simplex must reach an optimal solution");
    if( not tableau.crop_tableau(_linear_program.num_equations())){
        return INFEASIBLE;
    }
    tableau.set_target_equation(0, _linear_program.target_vector());
    //tableau.print();
    while(tableau.iterate() == SOLVED){
        //tableau.print();
    }
    _linear_program.set_solution(tableau.extract_solution());
    return tableau.iterate();
}


SimplexTableau SimplexSolver::create_extended_simplex_tableau() {
    VarID const num_original_variables = _linear_program.num_variables();
    VarID const num_slack_variables = _linear_program.num_equations();

    std::vector<bool> index_in_basis(num_original_variables, false);
    for(VarID i = 0; i < num_slack_variables; i++){
        index_in_basis.push_back(true);
    }

    Column constant_summands_of_equations(num_original_variables,0);
    for(VarID i = 0; i < num_slack_variables; i++){
        constant_summands_of_equations.push_back(_linear_program.constraints_vector()[i]);
    }

    (negate(_linear_program.constraints_vector()));
    Matrix linear_coeffitients_of_equations;
    for(VarID i = 0; i < num_original_variables; i++){
        linear_coeffitients_of_equations.emplace_back(num_original_variables + num_slack_variables);
    }
    for(VarID i = 0; i < num_slack_variables; i++){
        linear_coeffitients_of_equations.push_back(negate(_linear_program.constraints_matrix()[i]));
        for(VarID j = 0; j < num_slack_variables; j++){
            linear_coeffitients_of_equations.back().push_back(0);
        }
    }

    Value constant_term_of_target_equation = 0;
    Row linear_coeffitients_of_target_equation(num_original_variables  + num_slack_variables,0);
    for(VarID i = num_original_variables; i < num_slack_variables + num_original_variables; i++){
        add(linear_coeffitients_of_target_equation, multiply(linear_coeffitients_of_equations[i],-1));
        constant_term_of_target_equation -= constant_summands_of_equations[i];
    }

    return {index_in_basis, constant_summands_of_equations, linear_coeffitients_of_equations,
            constant_term_of_target_equation, linear_coeffitients_of_target_equation};
}

SimplexSolver::SimplexSolver(LinearProgram &linear_program) :
        Solver(linear_program){
    _linear_program.make_constraints_vector_non_negative();
}