-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Implementation of the two-phase simplex method in exact rational arithmetic
--   
--   Please see the README on GitHub at
--   <a>https://github.com/rasheedja/simplex-method#readme</a>
@package simplex-method
@version 0.2.0.0


module Linear.Simplex.Types
type Var = Int
type SimplexNum = Rational
type SystemRow = PolyConstraint
type System = [SystemRow]
data SystemWithSlackVarRow
SystemInStandardFormRow :: Maybe Var -> TableauRow -> SystemWithSlackVarRow

-- | This is Nothing iff the row does not have a slack variable
[$sel:mSlackVar:SystemInStandardFormRow] :: SystemWithSlackVarRow -> Maybe Var
[$sel:row:SystemInStandardFormRow] :: SystemWithSlackVarRow -> TableauRow
type SystemWithSlackVars = [SystemWithSlackVarRow]
data FeasibleSystem
FeasibleSystem :: Dict -> [Var] -> [Var] -> Var -> FeasibleSystem
[$sel:dict:FeasibleSystem] :: FeasibleSystem -> Dict
[$sel:slackVars:FeasibleSystem] :: FeasibleSystem -> [Var]
[$sel:artificialVars:FeasibleSystem] :: FeasibleSystem -> [Var]
[$sel:objectiveVar:FeasibleSystem] :: FeasibleSystem -> Var
data Result
Result :: Var -> VarLitMap -> Result
[$sel:objectiveVar:Result] :: Result -> Var
[$sel:varValMap:Result] :: Result -> VarLitMap
data SimplexMeta
SimplexMeta :: ObjectiveFunction -> Maybe FeasibleSystem -> Maybe Result -> SimplexMeta
[$sel:objective:SimplexMeta] :: SimplexMeta -> ObjectiveFunction
[$sel:feasibleSystem:SimplexMeta] :: SimplexMeta -> Maybe FeasibleSystem
[$sel:optimisedResult:SimplexMeta] :: SimplexMeta -> Maybe Result
type VarLitMap = Map Var SimplexNum

-- | List of variables with their <a>SimplexNum</a> coefficients. There is
--   an implicit addition between elements in this list.
--   
--   Example: [Var "x" 3, Var "y" -1, Var "z" 1] is equivalent to 3x + (-y)
--   + z.
type VarLitMapSum = VarLitMap

-- | For specifying constraints in a system. The LHS is a <tt>Vars</tt>,
--   and the RHS, is a <a>SimplexNum</a> number. LEQ [(1, 2), (2, 1)] 3.5
--   is equivalent to 2x1 + x2 &lt;= 3.5. Users must only provide positive
--   integer variables.
--   
--   Example: LEQ [Var "x" 3, Var "y" -1, Var "x" 1] 12.3 is equivalent to
--   3x + (-y) + x &lt;= 12.3.
data PolyConstraint
LEQ :: VarLitMapSum -> SimplexNum -> PolyConstraint
[$sel:lhs:LEQ] :: PolyConstraint -> VarLitMapSum
[$sel:rhs:LEQ] :: PolyConstraint -> SimplexNum
GEQ :: VarLitMapSum -> SimplexNum -> PolyConstraint
[$sel:lhs:LEQ] :: PolyConstraint -> VarLitMapSum
[$sel:rhs:LEQ] :: PolyConstraint -> SimplexNum
EQ :: VarLitMapSum -> SimplexNum -> PolyConstraint
[$sel:lhs:LEQ] :: PolyConstraint -> VarLitMapSum
[$sel:rhs:LEQ] :: PolyConstraint -> SimplexNum

-- | Create an objective function. We can either <a>Max</a>imize or
--   <a>Min</a>imize a <tt>VarTermSum</tt>.
data ObjectiveFunction
Max :: VarLitMapSum -> ObjectiveFunction
[$sel:objective:Max] :: ObjectiveFunction -> VarLitMapSum
Min :: VarLitMapSum -> ObjectiveFunction
[$sel:objective:Max] :: ObjectiveFunction -> VarLitMapSum

-- | TODO: Maybe we want this type TODO: A better/alternative name
data Equation
Equation :: VarLitMapSum -> SimplexNum -> Equation
[$sel:lhs:Equation] :: Equation -> VarLitMapSum
[$sel:rhs:Equation] :: Equation -> SimplexNum

-- | Value for <a>Tableau</a>. lhs = rhs.
data TableauRow
TableauRow :: VarLitMapSum -> SimplexNum -> TableauRow
[$sel:lhs:TableauRow] :: TableauRow -> VarLitMapSum
[$sel:rhs:TableauRow] :: TableauRow -> SimplexNum

-- | A simplex <tt>Tableu</tt> of equations. Each entry in the map is a
--   row.
type Tableau = Map Var TableauRow

-- | Values for a <a>Dict</a>.
data DictValue
DictValue :: VarLitMapSum -> SimplexNum -> DictValue
[$sel:varMapSum:DictValue] :: DictValue -> VarLitMapSum
[$sel:constant:DictValue] :: DictValue -> SimplexNum

-- | A simplex <a>Dict</a> One quation represents the objective function.
--   Each pair in the list is one equation in the system we're working
--   with. data Dict = Dict { objective :: DictObjective , entries ::
--   DictEntries } deriving (Show, Read, Eq, Generic)
type Dict = Map Var DictValue
data PivotObjective
PivotObjective :: Var -> VarLitMapSum -> SimplexNum -> PivotObjective
[$sel:variable:PivotObjective] :: PivotObjective -> Var
[$sel:function:PivotObjective] :: PivotObjective -> VarLitMapSum
[$sel:constant:PivotObjective] :: PivotObjective -> SimplexNum
instance GHC.Generics.Generic Linear.Simplex.Types.Result
instance GHC.Classes.Eq Linear.Simplex.Types.Result
instance GHC.Read.Read Linear.Simplex.Types.Result
instance GHC.Show.Show Linear.Simplex.Types.Result
instance GHC.Generics.Generic Linear.Simplex.Types.PolyConstraint
instance GHC.Classes.Eq Linear.Simplex.Types.PolyConstraint
instance GHC.Read.Read Linear.Simplex.Types.PolyConstraint
instance GHC.Show.Show Linear.Simplex.Types.PolyConstraint
instance GHC.Generics.Generic Linear.Simplex.Types.ObjectiveFunction
instance GHC.Classes.Eq Linear.Simplex.Types.ObjectiveFunction
instance GHC.Read.Read Linear.Simplex.Types.ObjectiveFunction
instance GHC.Show.Show Linear.Simplex.Types.ObjectiveFunction
instance GHC.Generics.Generic Linear.Simplex.Types.TableauRow
instance GHC.Classes.Eq Linear.Simplex.Types.TableauRow
instance GHC.Read.Read Linear.Simplex.Types.TableauRow
instance GHC.Show.Show Linear.Simplex.Types.TableauRow
instance GHC.Generics.Generic Linear.Simplex.Types.DictValue
instance GHC.Classes.Eq Linear.Simplex.Types.DictValue
instance GHC.Read.Read Linear.Simplex.Types.DictValue
instance GHC.Show.Show Linear.Simplex.Types.DictValue
instance GHC.Generics.Generic Linear.Simplex.Types.FeasibleSystem
instance GHC.Classes.Eq Linear.Simplex.Types.FeasibleSystem
instance GHC.Read.Read Linear.Simplex.Types.FeasibleSystem
instance GHC.Show.Show Linear.Simplex.Types.FeasibleSystem
instance GHC.Generics.Generic Linear.Simplex.Types.PivotObjective
instance GHC.Classes.Eq Linear.Simplex.Types.PivotObjective
instance GHC.Read.Read Linear.Simplex.Types.PivotObjective
instance GHC.Show.Show Linear.Simplex.Types.PivotObjective


-- | Converts <a>Linear.Simplex.Types</a> types into human-readable
--   <a>String</a>s
module Linear.Simplex.Prettify

-- | Convert a <tt>VarConstMap</tt> into a human-readable <a>String</a>
prettyShowVarConstMap :: VarLitMapSum -> String

-- | Convert a <a>PolyConstraint</a> into a human-readable <a>String</a>
prettyShowPolyConstraint :: PolyConstraint -> String

-- | Convert an <a>ObjectiveFunction</a> into a human-readable
--   <a>String</a>
prettyShowObjectiveFunction :: ObjectiveFunction -> String


-- | Helper functions for performing the two-phase simplex method.
module Linear.Simplex.Util

-- | Is the given <a>ObjectiveFunction</a> to be <a>Max</a>imized?
isMax :: ObjectiveFunction -> Bool

-- | Simplifies a system of <a>PolyConstraint</a>s by first calling
--   <tt>simplifyPolyConstraint</tt>, then reducing <a>LEQ</a> and
--   <a>GEQ</a> with same LHS and RHS (and other similar situations) into
--   <a>EQ</a>, and finally removing duplicate elements using <a>nub</a>.
simplifySystem :: [PolyConstraint] -> [PolyConstraint]

-- | Converts a <a>Dict</a> to a <a>Tableau</a> using
--   <tt>dictEntryToTableauEntry</tt>. FIXME: maybe remove this line. The
--   basic variables will have a coefficient of 1 in the <a>Tableau</a>.
dictionaryFormToTableau :: Dict -> Tableau

-- | Converts a <a>Tableau</a> to a <a>Dict</a>. We do this by isolating
--   the basic variable on the LHS, ending up with all non basic variables
--   and a <a>SimplexNum</a> constant on the RHS.
tableauInDictionaryForm :: Tableau -> Dict

-- | If this function is given <a>Nothing</a>, return <a>Nothing</a>.
--   Otherwise, we <a>lookup</a> the <a>Integer</a> given in the first item
--   of the pair in the map given in the second item of the pair. This is
--   typically used to extract the value of the <a>ObjectiveFunction</a>
--   after calling <a>twoPhaseSimplex</a>.
extractObjectiveValue :: Maybe Result -> Maybe SimplexNum

-- | Combines two 'VarLitMapSums together by summing values with matching
--   keys
combineVarLitMapSums :: VarLitMapSum -> VarLitMapSum -> VarLitMapSum
foldDictValue :: [DictValue] -> DictValue
foldVarLitMap :: [VarLitMap] -> VarLitMap
insertPivotObjectiveToDict :: PivotObjective -> Dict -> Dict
showT :: Show a => a -> Text
logMsg :: (MonadIO m, MonadLogger m) => LogLevel -> Text -> m ()
extractTableauValues :: Tableau -> Map Var SimplexNum
extractDictValues :: Dict -> Map Var SimplexNum


-- | Module implementing the two-phase simplex method.
--   <a>findFeasibleSolution</a> performs phase one of the two-phase
--   simplex method. <a>optimizeFeasibleSystem</a> performs phase two of
--   the two-phase simplex method. <a>twoPhaseSimplex</a> performs both
--   phases of the two-phase simplex method.
module Linear.Simplex.Solver.TwoPhase

-- | Find a feasible solution for the given system of
--   <a>PolyConstraint</a>s by performing the first phase of the two-phase
--   simplex method All variables in the <a>PolyConstraint</a> must be
--   positive. If the system is infeasible, return <a>Nothing</a>
--   Otherwise, return the feasible system in <a>Dict</a> as well as a list
--   of slack variables, a list artificial variables, and the objective
--   variable.
findFeasibleSolution :: (MonadIO m, MonadLogger m) => [PolyConstraint] -> m (Maybe FeasibleSystem)

-- | Optimize a feasible system by performing the second phase of the
--   two-phase simplex method. We first pass an <a>ObjectiveFunction</a>.
--   Then, the feasible system in <tt>DictionaryForm</tt> as well as a list
--   of slack variables, a list artificial variables, and the objective
--   variable. Returns a pair with the first item being the <a>Integer</a>
--   variable equal to the <a>ObjectiveFunction</a> and the second item
--   being a map of the values of all <a>Integer</a> variables appearing in
--   the system, including the <a>ObjectiveFunction</a>.
optimizeFeasibleSystem :: (MonadIO m, MonadLogger m) => ObjectiveFunction -> FeasibleSystem -> m (Maybe Result)

-- | Perform the two phase simplex method with a given
--   <a>ObjectiveFunction</a> a system of <a>PolyConstraint</a>s. Assumes
--   the <a>ObjectiveFunction</a> and <a>PolyConstraint</a> is not empty.
--   Returns a pair with the first item being the <a>Integer</a> variable
--   equal to the <a>ObjectiveFunction</a> and the second item being a map
--   of the values of all <a>Integer</a> variables appearing in the system,
--   including the <a>ObjectiveFunction</a>.
twoPhaseSimplex :: (MonadIO m, MonadLogger m) => ObjectiveFunction -> [PolyConstraint] -> m (Maybe Result)