Simplex

template<class T> class Simplex

#include <simplex.hpp>

Solves a linear problem with the simplex algorithm. The variables are x_0, …, x_{n-1} For now, all the variables are supposed non-negative. If the preprocessor variable SIMPLEX_VERBOSE is defined, detailed informations about the resolution of the problem are printed on stderr.

Public Types

enum Outcome

Values:

enumerator OPTIMAL_SOLUTION

enumerator NO_SOLUTION

enumerator UNBOUNDED

enumerator NOT_FINISHED

Public Functions

Simplex(const int variables_count): Initializes the simplex algorithm to solve a problem with the given number of variables.

int variables_count() const: Returns the number of variables that the problem contains.

void add_greater_than(std::vector<T> coefs, T cst): Adds the contraint: Σ a_j x_j >= b.

void add_lower_than(std::vector<T> coefs, T cst): Adds the contraint: Σ a_j x_j <= b.

void maximize(const std::vector<T> &coefs): Runs the simplex algorithm to maximize Σ a_j x_j subject to the previously given constraints.

void minimize(const std::vector<T> &coefs): Runs the simplex algorithm to minimize Σ a_j x_j subject to the previously given constraints.

Outcome outcome() const: Returns the outcome of the simplex (NOT_FINISHED if the algorithm has not been executed yet)

T optimal_value() const: Returns the optimal value computed by the simplex.

T solution_value(const int var) const: Returns the value of a variable in the optimal solution that was found.

Private Functions

int choose_entering_variable() const: Returns the next entering variable (-1 if the solution is optimal)

int choose_leaving_variable(const int entering) const

Returns the next leaving variable (-1 if the problem is unbounded).

Parameters:: entering – The entering variable choosen before

void make_exchange(const int entering, const int leaving): Executes a transformation of the problem.

Outcome one_step(): Executes one step of the simplex algorithm.

void print_constraints(): Prints the current state of the simplex on stderr.

void resize_constraints(): Add null coefficients at the end of each constraint to take into account the new variables.

Private Members

Outcome m_outcome

int m_variables_count

std::vector<Constraint> m_constraints

Constraint m_to_optimize

struct Constraint

Public Members

int var_index

std::vector<T> coefs

T cst