Numeric.Limp.Solve.Simplex.Maps

The simplest, stupidest possible simplex algorithm. The idea here is to be slow, but "obviously correct" so other algorithms can be verified against it.

That's the plan, at least. For now this is just a first cut of trying to implement simplex.

Documentation

data IterateResult z r c

Result of a single pivot attempt

Constructors

Done

Maximum reached!

Progress (Standard z r c)

Pivot was made

Stuck

No progress can be made: unbounded along the objective

Instances

(Show z, Show r, Show (R c)) => Show (IterateResult z r c)

simplex1 :: (Ord z, Ord r, Rep c) => Standard z r c -> IterateResult z r c

Try to find a pivot and then perform it. We're assuming, at this stage, that the existing solution is feasible.

pivotRowForCol :: (Ord z, Ord r, Rep c) => Standard z r c -> StandardVar z r -> Maybe (StandardVar z r)

Find pivot row for given column. We're trying to find a way to increase the value of column from zero, and the returned row will be decreased to zero. Since all variables are >= 0, we cannot return a row that would set the column to negative.

minBy' :: (a -> a -> Ordering) -> [a] -> Maybe a

Find minimum, or nothing if empty

pivot :: (Ord z, Ord r, Rep c) => Standard z r c -> (StandardVar z r, StandardVar z r) -> Standard z r c

Perform pivot for given row and column. We normalise row so that row.column = 1

norm = row / row[column]

Then, for all other rows including the objective, we want to make sure its column entry is zero:

row' = row - row[column]*norm

In the end, this means "column" will be an identity column, or a basis column.

single_simplex :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c)

Single phase of simplex. Keep repeating until no progress can be made.

simplex :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c)

Two phase: first, find a satisfying solution. then, solve simplex as normal.

find_initial_sat :: (Ord z, Ord r, Rep c) => Standard z r c -> Maybe (Standard z r c)

Find a satisfying solution. if there are any rows with negative values, this means their basic values are negative (which is not satisfying the x >= 0 constraint) these negative-valued rows must be pivoted around using modified pivot criteria

assignmentAll :: Rep c => Standard z r c -> (Map (StandardVar z r) (R c), R c)

assignment :: (Ord z, Ord r, Rep c) => Standard z r c -> (Assignment () (Either z r) c, R c)

minimise_basics :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c

Minimise whatever variables are basic in given standard input must not already have an objective row SVO, because the existing objective is added as a new row with that name

pricing_out :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c

Find the basic variables and "price them out" of the objective function, by subtracting multiples of the basic row from objective

drop_fake_objective :: (Ord z, Ord r, Rep c) => Standard z r c -> Standard z r c

Pull the previously-hidden objective out of constraints, and use it