1      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKL M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p qrstuvwxyz{|}~None!"(*234=BHKM-Give reason for being infeasible, if possibleLThe bound on a variable or constraint is empty - lower bound is above upper.;An integer variable is constrained to be equal to a non-intNone!"(*234=BHKMiAn 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 numbersLConvert 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!"(*234=BHKMfA 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!"(*234=BHKMAA representation that uses arbitrary-sized Integers and Rationals.Define show manually, so we can strip out the Z and R prefixes.None!"(*234=BHKM None!"(*234=BHKM CMaybe a lower bound, the variable's name, and maybe an upper bound. Define upper and lower bounds of program variables. Bounds may be specified multiple times: the intersection of all bounds is used.#7Create a lower and upper bound for an integer variable.$3Create only a lower bound for an integer variable. %4Create only an upper bound for an integer variable. &'A binary integer variable: can only be 0 or 1.'3Create a lower and upper bound for a real variable.(/Create only a lower bound for a real variable. )0Create only an upper bound for a real variable.  !"#$%&'()  !"#$%&'() "!#$%&'()  "!#$%&'()None!"(*234=BHKM* 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./IClassify the result type of a linear function to either integral or real:0Real or mixed R1 Integral Z*+,-./01*+,-./01/10,.-+**+,.-/10None!"(*234=BHKM2AAny linear function can be converted into a real linear function.3Integral variable4$Integral variable with coefficient 15 Real variable6 Real variable with coefficient 17An integral constant summand8An integral constant summand9 Constant 0: Constant 1;A real constant7Helper for applying function to second element of tuple<=Negate a linear function. Negation does not change the kind.=,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!>,Multiply a linear function by some constant.?HAdd two linear functions together. They can have different result types.@PSubtract one linear function from another. They can have different result types.23456789:;<=>?@,-.23456789:;<=>?@,.-2345678;9:<=>?@23456789:;<=>?@=>?@None!"(*234=BHKMADifferent 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 ABCDEFGHIJK ABCDEFGHIJ AJIHGFEDCBKA JIHGFEDCBKCDFGHIJ None!"(*234=BHKML Whole program, parameterised by: ztype of integer variablesrtype of real variablesc*representation of integers and reals (see )NOptimisation directionOThe objective functionP All constraints bundled up with :&&.QUpper and lower bounds of variables. Not all variables need to be mentioned, and if variables are mentioned multiple times, the intersection is used.R7Direction to optimise program in: minimise or maximise. LMNOPQRSTUVW LMNOPQRSTUVW RTSLMNOPQUVWLMNOPQRTSUVW None!"(*234=BHKMX`Evaluate a linear function with given assignment. If the linear function is purely integral, a Z will be returned; otherwise, R.YGEvaluate a linear function with given assignment, returning real value.Z.Check whether assignment satisfies constraint.[JCheck whether an assignment satisfies the program's constraints and boundsXYZ[\XYZ[\XYZ[\XYZ[\None!"(*234=BHKM= !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJLMNOPQRSTUVWXYZ[\ None!"(*234=BHKM]sLinear 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 assignmenta/Find set of all variables mentioned in function]^_`a]^_`a]^_`a]^_`a None!"(*234=BHKMbA simple constraintcAMaybe 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.d!Conjunction of simple constraintsf4Check whether an assignment satisfies the constraintg"Get set of variables in constraintbcdefgbcdefgdebcfgbcdefg None!"(*234=BHKMhA program represented by objective, constraints and bounds. There is no need for an optimisation direction; the objective is just negated.m.Find set of all variables mentioned in programn!Merge some lower and upper boundsoJCheck whether an assignment satisfies the program's constraints and bounds hijklmnop hijklmnop hijklmnophijklmnopNone!"(*234=BHKMqConvert 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)rConvert a Frontend A into a Canon d.Should satisfy that 1forall a c. P.check a c == check a (constraint c)sConvert a Frontend L into a Canon h.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 ...qrsqrsqrsqrsNone!"(*234=BHKM]^_`abcdefghijklmnopqrsNone!"(*234=BHKMtututtuNone!"(*234=BHKMvRFind 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)vvvvNone!"(*234=BHKMx6Convert 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 InfeasibleBoundEmptywxyzwxyzwxyzwxyzNone!"(*234=BHKM{&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!"(*234=BHKM}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 <= 7CSubstitute 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 <= 10BSubstitute assignment into a program. What does this satisfy? Hm.}~}~}~}~None!"(*234=BHKMNone!"(*234=BHKM When unconstrained variables are encountered, they are replaced with x = SVPos x - SVNeg x so both parts can be constrained to >= 0.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 >= 0eMagic objective, used when hiding an existing objective as a constraint and creating a new objectiveHA slack variable, introduced to make less-eq constraints into equalitiesA normal variable[Entire program in standard form, as well as substitutions required to extract an assignment0A 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!"(*234=BHKM Result of a single pivot attempt6No progress can be made: unbounded along the objectivePivot was madeMaximum reached!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 emptyPPerform 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 nameFind the basic variables and "price them out" of the objective function, by subtracting multiples of the basic row from objectiveCPull the previously-hidden objective out of constraints, and use it None!"(*234=BHKM !"#$%&'( !)*+,-./ !*+0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_ ` ` a b c d e f g h i j k l m n o @ @ p l q r s U U m t ` ` b c d u v n owxhyz{|}~bc limp-0.3.2.1Numeric.Limp.ErrorNumeric.Limp.Rep.RepNumeric.Limp.Rep.IntDoubleNumeric.Limp.Rep.ArbitraryNumeric.Limp.Program.BoundsNumeric.Limp.Program.ResultKindNumeric.Limp.Program.LinearNumeric.Limp.Program.ConstraintNumeric.Limp.Program.ProgramNumeric.Limp.Program.EvalNumeric.Limp.Canon.LinearNumeric.Limp.Canon.ConstraintNumeric.Limp.Canon.ProgramNumeric.Limp.Canon.ConvertNumeric.Limp.Canon.Pretty$Numeric.Limp.Canon.Analyse.Constants#Numeric.Limp.Canon.Simplify.Bounder"Numeric.Limp.Canon.Simplify.Crunch!Numeric.Limp.Canon.Simplify.SubstNumeric.Limp.Canon.Simplify'Numeric.Limp.Solve.Simplex.StandardFormNumeric.Limp.Solve.Simplex.Maps Numeric.Limp.Solve.Branch.SimpleNumeric.Limp.RepNumeric.Limp.ProgramNumeric.Limp.Canon InfeasibleInfeasibleBoundEmptyInfeasibleNotIntegral AssignmentRepZRfromZzOfrOfzrOfassSize$fMonoidAssignment IntDoubleunwrapR$fShowR$fShowZTFCo:R:ZIntDoubleTFCo:R:RIntDouble$fRepIntDouble ArbitraryTFCo:R:ZArbitraryTFCo:R:RArbitrary$fRepArbitraryBBoundsBoundRBoundZ lowerUpperZlowerZupperZbinary lowerUpperRlowerRupperRKRepKMergeLinearLRLZKKRKZtoRzz1rr1conconZc0c1conRneg.**..+..-. ConstraintCTrue:!:&&Between:>:>=:<:<=:==$fMonoidConstraintProgram _direction _objective _constraints_bounds DirectionMaximiseMinimiseprogramminimisemaximiseevalevalRcheck checkProgram checkBoundsmkLinear varsOfLinear Constraint1C1varsOfConstraint varsOfProgram mergeBoundslinear constraintppr $fShowProgramconstantsProgramBoundbounderConstraint1bounderConstraintbounderProgram crunchProgramcrunchConstraint substLinearsubstConstraint1substConstraint substProgramsimplify simplify' StandardVarSVNegSVPosSVLowerSVOSVSSVStandardLinear StandardSubstStandard_substs StandardRow addLinearsstandard lookupRowobjOfRow IterateResultStuckProgressDonesimplex1pivotRowForColminBy'pivotsingle_simplexsimplexfind_initial_sat assignmentAll assignmentminimise_basics pricing_outdrop_fake_objectivebranch makeIntegralon2