-- 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 -- https://github.com/rasheedja/simplex-method#readme @package simplex-method @version 0.1.0.0 module Linear.Simplex.Types -- | List of Integer variables with their Rational -- coefficients. There is an implicit addition between elements in this -- list. Users must only provide positive integer variables. -- -- Example: [(2, 3), (6, (-1), (2, 1))] is equivalent to 3x2 + (-x6) + -- x2. type VarConstMap = [(Integer, Rational)] -- | For specifying constraints in a system. The LHS is a -- VarConstMap, and the RHS, is a Rational number. LEQ [(1, -- 2), (2, 1)] 3.5 is equivalent to 2x1 + x2 <= 3.5. Users must only -- provide positive integer variables. -- -- Example: LEQ [(2, 3), (6, (-1), (2, 1))] 12.3 is equivalent to 3x2 + -- (-x6) + x2 <= 12.3. data PolyConstraint LEQ :: VarConstMap -> Rational -> PolyConstraint GEQ :: VarConstMap -> Rational -> PolyConstraint EQ :: VarConstMap -> Rational -> PolyConstraint -- | Create an objective function. We can either Maximize or -- Minimize a VarConstMap. data ObjectiveFunction Max :: VarConstMap -> ObjectiveFunction Min :: VarConstMap -> ObjectiveFunction -- | A Tableau of equations. Each pair in the list is a row. The -- first item in the pair specifies which Integer variable is -- basic in the equation. The second item in the pair is an equation. The -- VarConstMap in the second equation is a list of variables with -- their coefficients. The RHS of the equation is a Rational -- constant. type Tableau = [(Integer, (VarConstMap, Rational))] -- | Type representing equations. Each pair in the list is one equation. -- The first item of the pair is the basic variable, and is on the LHS of -- the equation with a coefficient of one. The RHS is represented using a -- VarConstMap. The integer variable -1 is used to represent a -- Rational on the RHS type DictionaryForm = [(Integer, VarConstMap)] instance GHC.Classes.Eq Linear.Simplex.Types.PolyConstraint instance GHC.Show.Show Linear.Simplex.Types.PolyConstraint instance GHC.Classes.Eq Linear.Simplex.Types.ObjectiveFunction instance GHC.Show.Show Linear.Simplex.Types.ObjectiveFunction -- | Converts Linear.Simplex.Types types into human-readable -- Strings module Linear.Simplex.Prettify -- | Convert a VarConstMap into a human-readable String prettyShowVarConstMap :: VarConstMap -> String -- | Convert a PolyConstraint into a human-readable String prettyShowPolyConstraint :: PolyConstraint -> String -- | Convert an ObjectiveFunction into a human-readable -- String prettyShowObjectiveFunction :: ObjectiveFunction -> String -- | Helper functions for performing the two-phase simplex method. module Linear.Simplex.Util -- | Is the given ObjectiveFunction to be Maximized? isMax :: ObjectiveFunction -> Bool -- | Extract the objective (VarConstMap) from an -- ObjectiveFunction getObjective :: ObjectiveFunction -> VarConstMap -- | Simplifies a system of PolyConstraints by first calling -- simplifyPolyConstraint, then reducing LEQ and GEQ -- with same LHS and RHS (and other similar situations) into EQ, -- and finally removing duplicate elements using nub. simplifySystem :: [PolyConstraint] -> [PolyConstraint] -- | Simplify an ObjectiveFunction by first sorting and then -- calling foldSumVarConstMap on the VarConstMap. simplifyObjectiveFunction :: ObjectiveFunction -> ObjectiveFunction -- | Simplify a PolyConstraint by first sorting and then -- calling foldSumVarConstMap on the VarConstMap. simplifyPolyConstraint :: PolyConstraint -> PolyConstraint -- | Add a sorted list of VarConstMaps, folding where the variables -- are equal foldSumVarConstMap :: [(Integer, Rational)] -> [(Integer, Rational)] -- | Get a map of the value of every Integer variable in a -- Tableau displayTableauResults :: Tableau -> [(Integer, Rational)] -- | Get a map of the value of every Integer variable in a -- DictionaryForm displayDictionaryResults :: DictionaryForm -> [(Integer, Rational)] -- | Map the given Integer variable to the given -- ObjectiveFunction, for entering into DictionaryForm. createObjectiveDict :: ObjectiveFunction -> Integer -> (Integer, VarConstMap) -- | Converts a Tableau to DictionaryForm. We do this by -- isolating the basic variable on the LHS, ending up with all non basic -- variables and a Rational constant on the RHS. (-1) is used to -- represent the rational constant. tableauInDictionaryForm :: Tableau -> DictionaryForm -- | Converts a DictionaryForm to a Tableau. This is done by -- moving all non-basic variables from the right to the left. The -- rational constant (represented by the Integer variable -1) -- stays on the right. The basic variables will have a coefficient of 1 -- in the Tableau. dictionaryFormToTableau :: DictionaryForm -> Tableau -- | If this function is given Nothing, return Nothing. -- Otherwise, we lookup the Integer 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 ObjectiveFunction -- after calling twoPhaseSimplex. extractObjectiveValue :: Maybe (Integer, [(Integer, Rational)]) -> Maybe Rational -- | Module implementing the two-phase simplex method. -- findFeasibleSolution performs phase one of the two-phase -- simplex method. optimizeFeasibleSystem performs phase two of -- the two-phase simplex method. twoPhaseSimplex performs both -- phases of the two-phase simplex method. module Linear.Simplex.Simplex -- | Find a feasible solution for the given system of -- PolyConstraints by performing the first phase of the two-phase -- simplex method All Integer variables in the -- PolyConstraint must be positive. If the system is infeasible, -- return Nothing Otherwise, return the feasible system in -- DictionaryForm as well as a list of slack variables, a list -- artificial variables, and the objective variable. findFeasibleSolution :: [PolyConstraint] -> Maybe (DictionaryForm, [Integer], [Integer], Integer) -- | Optimize a feasible system by performing the second phase of the -- two-phase simplex method. We first pass an ObjectiveFunction. -- Then, the feasible system in DictionaryForm 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 Integer -- variable equal to the ObjectiveFunction and the second item -- being a map of the values of all Integer variables appearing in -- the system, including the ObjectiveFunction. optimizeFeasibleSystem :: ObjectiveFunction -> DictionaryForm -> [Integer] -> [Integer] -> Integer -> Maybe (Integer, [(Integer, Rational)]) -- | Perform the two phase simplex method with a given -- ObjectiveFunction a system of PolyConstraints. Assumes -- the ObjectiveFunction and PolyConstraint is not empty. -- Returns a pair with the first item being the Integer variable -- equal to the ObjectiveFunction and the second item being a map -- of the values of all Integer variables appearing in the system, -- including the ObjectiveFunction. twoPhaseSimplex :: ObjectiveFunction -> [PolyConstraint] -> Maybe (Integer, [(Integer, Rational)])