úÎÎñÃCÔ      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn o p q r s t u v w x y z { | } ~  € ‚ ƒ „ … † ‡ ˆ ‰ Š ‹ Œ Ž ‘ ’ “ ” • – —˜™š›œžŸ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓNone&'-0;<=FKQTVn-Give reason for being infeasible, if possible;An integer variable is constrained to be equal to a non-intLThe bound on a variable or constraint is empty - lower bound is above upper.None&'-0;<=FKQTVÆiAn assignment from variables to values. Maps integer variables to integers, and real variables to reals./The Representation class. Requires its members Z c and R c to be Num, Ord and Eq.AFor some reason, for type inference to work, the members must be data instead of type=. This gives some minor annoyances when unpacking them. See unwrapR below.Integers  Real numbers LConvert an integer to a real. This should not lose any precision. (whereas fromIntegral 1000 :: Word8 would lose precision) @Retrieve value of integer variable - or 0, if there is no value. =Retrieve value of real variable - or 0, if there is no value. URetrieve value of an integer or real variable, with result cast to a real regardless.       None&'-0;<=FKQTVxfA representation that uses native 64-bit ints and 64-bit doubles. Really, this should be 32-bit ints.4Convert a wrapped (R IntDouble) to an actual Double..Define show manually, so we can strip out the Z and R prefixes.  None&'-0;<=FKQTV"(AA representation that uses arbitrary-sized Integers and Rationals,.Define show manually, so we can strip out the Z and R prefixes.) *((/-).*,+/-).*None&'-0;<=FKQTV#ž   None&'-0;<=FKQTV+—= Convert a K to its actual representation (Z or R).>ŸFind the result type of merging, or adding, two linear functions: adding two integers produces an integer, while adding a real on either side produces a real.?|Representation of either integral of real linear functions: a list of variables with coefficients, plus a constant summand.BIClassify the result type of a linear function to either integral or real:C Integral ZDReal or mixed R=>?A@BDCBCD?@A>=?@ABCDNone&'-0;<=FKQTV8‘FAAny linear function can be converted into a real linear function.GIntegral variableH$Integral variable with coefficient 1I Real variableJ Real variable with coefficient 1KAn integral constant summandLAn integral constant summandM Constant 0N Constant 1OA real constantÔ7Helper for applying function to second element of tupleP=Negate a linear function. Negation does not change the kind.Q,Multiply a linear function by some constant.uNote that you cannot multiply a linear function by another linear function, as the result would likely be non-linear!R,Multiply a linear function by some constant.SHAdd two linear functions together. They can have different result types.TPSubtract one linear function from another. They can have different result types.?@AFGHIJKLMNOPQRST?@AFGHIJKLOMNPQRSTQ7R7S6T6None&'-0;<=FKQTVCAUDifferent kind of constraints.iThese are not all necessary, but I have a hunch that keeping some structure may be helpful in the future. Constructors: :==Equality constraint:<=Less than or equal:<EStrictly less than: this is only allowed for purely integer functions:>=Greater than or equal:>HStrictly greater than: this is only allowed for purely integer functionsBetween Between a b c is equivalent to a :<= b :&& b :<= c:&&Conjunction of two constraints:!"name" :! constr@ Annotate a constraint with a name, or other useless informationCTrueTrivially true constraint U^]\[YWVXZ UVWXYZ[\]^`_U VWXYZ[\]^V5W5X5Y5Z5\3]4None&'-0;<=FKQTVMé bCMaybe a lower bound, the variable's name, and maybe an upper bound.c„Define upper and lower bounds of program variables. Bounds may be specified multiple times: the intersection of all bounds is used.f7Create a lower and upper bound for an integer variable.g3Create only a lower bound for an integer variable. h4Create only an upper bound for an integer variable. i'A binary integer variable: can only be 0 or 1.j3Create a lower and upper bound for a real variable.k/Create only a lower bound for a real variable. l0Create only an upper bound for a real variable. bcedfghijkl cdebfghijklcde None&'-0;<=FKQTVUÀn Whole program, parameterised by: ztype of integer variablesrtype of real variablesc*representation of integers and reals (see )pOptimisation directionqThe objective functionr All constraints bundled up with :&&.s–Upper and lower bounds of variables. Not all variables need to be mentioned, and if variables are mentioned multiple times, the intersection is used.t7Direction to optimise program in: minimise or maximise. nosrqptvuwxy tuvnopqrswxynopqrstuv None&'-0;<=FKQTV\,|`Evaluate a linear function with given assignment. If the linear function is purely integral, a Z will be returned; otherwise, R.}GEvaluate a linear function with given assignment, returning real value.~.Check whether assignment satisfies constraint.JCheck whether an assignment satisfies the program's constraints and bounds|}~€|}~€None&'-0;<=FKQTV] ==>?@ABCDFGHIJKLMNOPQRSTUZXVWY[\]^bcdefghijklnopqrstuvwxy|}~€ None&'-0;<=FKQTVcsLinear function is represented as a map from either a integral variable or an real variable, to a real coefficient.ƒ>Create linear function from list of variables and coefficients„.Evaluate linear function with given assignment…/Find set of all variables mentioned in function‚ƒ„…‚ƒ„…‚ None&'-0;<=FKQTVh”ˆA simple constraint‰AMaybe a lower bound, a linear function, and maybe an upper bound.JIn order to be meaningful, at least one of lower or upper bound should be Just.Š!Conjunction of simple constraintsŒ4Check whether an assignment satisfies the constraint"Get set of variables in constraintˆ‰Š‹ŒŠ‹ˆ‰Œˆ‰Š‹ None&'-0;<=FKQTVn>Ž‹A program represented by objective, constraints and bounds. There is no need for an optimisation direction; the objective is just negated.“.Find set of all variables mentioned in program”!Merge some lower and upper bounds•JCheck whether an assignment satisfies the program's constraints and bounds Ž’‘“”•– Ž‘’“”•–Ž‘’None&'-0;<=FKQTVz—6Substitute assignment into linear function. However, } isn't quite a linear function! That is, it doesn't have a constant summand. So we must return the constant summand we lose. Satisfies: Rforall a b f. let (f', c') = substLinear a f in eval (a <> b) f == eval b f' + c'  subst (x := 5) in 2x + y (y, 10)˜<Substitute assignment into a single linear constraint. See ™. 15 <= 2x + y <= 10 subst (y := 3) 2 <= 2x <= 7™CSubstitute assignment into a set of linear constraints. Satisfies: Mforall a b f. let c' = substConstraint a c in check (a <> b) c == check b c' 1subst (x := 5) in 15 <= 2x + y <= 20 5 <= y <= 10šBSubstitute assignment into a program. What does this satisfy? Hm.—˜™š—˜™šNone&'-0;<=FKQTV€q›&Crunch the constraints in some programœICrunch some constraints. Constraints with the same function, for example J 2x + y < 5 && 0 < 2x + y && 2x + y < 10becomes  0 < 2x + y < 5This should satisfy: hforall a c. check a c == check a (crunchConstraint c) forall a. length (checkConstraint c) <= length c›œ›œNone&'-0;<=FKQTV…9ž6Convert a single constraint into a bound, if possible. Abounder $ Constraint (5 <= y <= 10) == Bound (Just 5) y (Just 10) Cbounder $ Constraint (5 <= 2y <= 10) == Bound (Just 2.5) y (Just 5) Abounder $ Constraint (10 <= 2y <= 5) == Left InfeasibleBoundEmptyžŸ žŸ None&'-0;<=FKQTV†¡¢¡None&'-0;<=FKQTV“·£Convert a Frontend ? into a Canon K. Returns the constant summand as well, as Canon Linear do not have these.Should satisfy that Fforall a l. P.evalR a l == evalR a (fst $ linear l) + (snd $ linear l)¤Convert a Frontend U into a Canon Š.Should satisfy that 1forall a c. P.check a c == check a (constraint c)¥Convert a Frontend n into a Canon Ž.LIf we had a solve function that worked on either, it would ideally satisfy (forall p. P.solve p == solve (program p)…However, due to potential non-determinism in solving functions, it could be possible to get a different, but still optimal, solution: Óforall p. let aP = P.solve p p' = program p a = solve p' in P.eval aP (P._objective p) == eval a (_objective p') && check a (P._constraints p) && check ...£¤¥£¤¥None&'-0;<=FKQTV”‡‚ƒ„…ˆ‰Š‹ŒŽ‘’“”•–£¤¥None&'-0;<=FKQTV˜¦RFind the constants in a program, only by looking at the bounds with lo==up. (See "Numeric.Limp.Canon.Simplify.Stride" to convert constraints to bounds)¦¦None&'-0;<=FKQTV˜É§¨§¨None&'-0;<=FKQTV™™©ª©ªNone&'-0;<=FKQTV§Å ¬A normal variable­HA slack variable, introduced to make less-eq constraints into equalities®eMagic objective, used when hiding an existing objective as a constraint and creating a new objective¯¡When a variable has a lower bound other than 0, we replace all occurences with with a new version minus the lower bound. x >= 5 ==> Lx - 5 >= 5 ==> Lx >= 0°†When unconstrained variables are encountered, they are replaced with x = SVPos x - SVNeg x so both parts can be constrained to >= 0.´[Entire program in standard form, as well as substitutions required to extract an assignment¹0A single linear function with a constant summandº'Sum a list of linear functions together»/Perform substitution over a linear function/row¼(Convert canon program into standard form½.Get the coefficient of a variable in given row¾%Get objective or basis value of a row«±°¯®­¬²³´µ¸·¶¹º»¼½¾¹´µ¶·¸³²«¬­®¯°±º»¼½¾«¬­®¯°±´µ¶·¸None&'-0;<=FKQTV¬Ã Result of a single pivot attemptÄMaximum reached!ÅPivot was madeÆ6No progress can be made: unbounded along the objectiveÇpTry to find a pivot and then perform it. We're assuming, at this stage, that the existing solution is feasible.Èõ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.É!Find minimum, or nothing if emptyÊPPerform pivot for given row and column. We normalise row so that row.column = 1 norm = row / row[column]aThen, for all other rows including the objective, we want to make sure its column entry is zero: row' = row - row[column]*normNIn the end, this means "column" will be an identity column, or a basis column.ËGSingle phase of simplex. Keep repeating until no progress can be made.ÌPTwo phase: first, find a satisfying solution. then, solve simplex as normal.Íû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Ð Minimise whatever variables are basicA in given standard input must not already have an objective row SVOF, because the existing objective is added as a new row with that nameÑ‚Find the basic variables and "price them out" of the objective function, by subtracting multiples of the basic row from objectiveÒCPull the previously-hidden objective out of constraints, and use itÃÆÅÄÇÈÉÊËÌÍÎÏÐÑÒÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÃÄÅÆÕ  !"#$%&'()*+,"#-./0123456789:;<=>?@"#./ABC3456789:;<=>?DEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrst u u v w x y z { | } ~  € ‚ ƒ „ … † F F ‡ ƒ ˆ ‰ Š ‹ Œ \ \ „ u u w x y Ž … †‘’“”•–—˜™š›œ}žŸ ¡¢£¤¥¦§¨©ª««wx¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈ#limp-0.3.2.2-5iqVkjUTA5PJQ6hA15f28DNumeric.Limp.ErrorNumeric.Limp.Rep.RepNumeric.Limp.Rep.IntDoubleNumeric.Limp.Rep.ArbitraryNumeric.Limp.Program.ResultKindNumeric.Limp.Program.LinearNumeric.Limp.Program.ConstraintNumeric.Limp.Program.BoundsNumeric.Limp.Program.ProgramNumeric.Limp.Program.EvalNumeric.Limp.Canon.LinearNumeric.Limp.Canon.ConstraintNumeric.Limp.Canon.Program!Numeric.Limp.Canon.Simplify.Subst"Numeric.Limp.Canon.Simplify.Crunch#Numeric.Limp.Canon.Simplify.BounderNumeric.Limp.Canon.PrettyNumeric.Limp.Canon.Convert$Numeric.Limp.Canon.Analyse.ConstantsNumeric.Limp.Canon.Simplify Numeric.Limp.Solve.Branch.Simple'Numeric.Limp.Solve.Simplex.StandardFormNumeric.Limp.Solve.Simplex.MapsNumeric.Limp.RepNumeric.Limp.ProgramNumeric.Limp.Canon InfeasibleInfeasibleNotIntegralInfeasibleBoundEmpty$fEqInfeasible$fShowInfeasible AssignmentRepZRfromZzOfrOfzrOfassSize$fMonoidAssignment$fSemigroupAssignment$fShowAssignment IntDoubleunwrapR$fShowR$fShowZD:R:ZIntDouble0D:R:RIntDouble0$fRepIntDouble$fOrdZ$fEqZ $fIntegralZ$fRealZ$fNumZ$fEnumZ$fOrdR$fEqR$fNumR$fEnumR $fFractionalR$fRealR $fRealFracR ArbitraryD:R:ZArbitrary0D:R:RArbitrary0$fRepArbitraryKRepKMergeLinearLZLRKKZKR $fShowLineartoRzz1rr1conconZc0c1conRneg.**..+..-. Constraint:==:<=:<:>=:>Between:&&:!CTrue$fMonoidConstraint$fSemigroupConstraint$fShowConstraintBBoundsBoundZBoundR lowerUpperZlowerZupperZbinary lowerUpperRlowerRupperR $fShowBoundsProgram _direction _objective _constraints_bounds DirectionMinimiseMaximiseprogramminimisemaximise$fShowDirection $fShowProgramevalevalRcheck checkProgram checkBoundsmkLinear varsOfLinear $fOrdLinear $fEqLinear Constraint1C1varsOfConstraint varsOfProgram mergeBounds substLinearsubstConstraint1substConstraint substProgram crunchProgramcrunchConstraintBoundbounderConstraint1bounderConstraintbounderProgrampprlinear constraintconstantsProgramsimplify simplify'branch makeIntegral StandardVarSVSVSSVOSVLowerSVPosSVNegStandardLinear StandardSubstStandard_substs StandardRow addLinearsstandard lookupRowobjOfRow$fEqStandardVar$fOrdStandardVar$fShowStandardVar$fShowStandard IterateResultDoneProgressStucksimplex1pivotRowForColminBy'pivotsingle_simplexsimplexfind_initial_sat assignmentAll assignmentminimise_basics pricing_outdrop_fake_objective$fShowIterateResulton2