Documentation

Mathlib.Tactic.Linarith.Oracle.SimplexAlgorithm.SimplexAlgorithm

Simplex Algorithm #

To obtain required vector in Linarith.SimplexAlgorithm.findPositiveVector we run the Simplex Algorithm. We use Bland's rule for pivoting, which guarantees that the algorithm terminates.

An exception in the SimplexAlgorithmM monad.

Instances For
    @[reducible, inline]

    The monad for the Simplex Algorithm.

    Equations
      Instances For
        def Linarith.SimplexAlgorithm.doPivotOperation {matType : NatNatType} [UsableInSimplexAlgorithm matType] (exitIdx enterIdx : Nat) :

        Given indexes exitIdx and enterIdx of exiting and entering variables in the basic and free arrays, performs pivot operation, i.e. expresses one through the other and makes the free one basic and vice versa.

        Equations
          Instances For

            Check if the solution is found: the objective function is positive and all basic variables are nonnegative.

            Equations
              Instances For

                Chooses an entering variable: among the variables with a positive coefficient in the objective function, the one with the smallest index (in the initial indexing).

                Equations
                  Instances For

                    Chooses an exiting variable: the variable imposing the strictest limit on the increase of the entering variable, breaking ties by choosing the variable with smallest index.

                    Equations
                      Instances For

                        Chooses entering and exiting variables using (Bland's rule)[(https://en.wikipedia.org/wiki/Bland%27s_rule)] that guarantees that the Simplex Algorithm terminates.

                        Equations
                          Instances For

                            Runs the Simplex Algorithm inside the SimplexAlgorithmM. It always terminates, finding solution if such exists.

                            Equations
                              Instances For