ϊΞτρμˆq      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopportable provisional'Richard Senington <sc06r2s@leeds.ac.uk> Safe-Inferred hCore concepts, location, timeslot, person, two events cannot happen in the same place at the same time. w This version expects a constrained data set, so that the roomEvent lookup for example only yields events that can + reasonably be scheduled in that room. {Originally I intended the objectives (low over scheduling of people) and the soft objectives to be handled somewhere else. z At this time, I am unsure how to abstract this, and I want a system that works now, so I will over specialise to the b time tabling competition specifications. Hopefully this can be rectified in a later version. CThe objective function as specific by the 2002 competition rules. eThe validity function as specific by the 2002 competition rules. Basically no clashes at this point. !^Splitting off the two parts of show, so we have a simple show for the state of the solution, N a more complex solution description and the constant constrained problem. "UThe other part of the time table data type. See the current status of the solution. #7A simple spread sheet display seems like a good idea. $*Maybe a helper, making it public anyway. %SFails silently and does no update the schedule if the very hard constraints fail. qNA helper method, that does not validate before descheduling. Not for export. &9Fails silently if the event is not currently scheduled. 'AFails silently if the time slot and room number are not booked. (2Just a combination of existing useful functions. /  !"#$%rstuq&'(v)  !"#$%&'() !&'%" #$(  !"#$%rstuq&'(vportable provisional'Richard Senington <sc06r2s@leeds.ac.uk> Safe-Inferred )kThis is intended to be an internal format only, though I will provide access and visibility to it so that o it can be inspected by other programs. In practice I do not expect users to operate upon the raw problem,  but instead upon TimeTable. w,Helper function that will not be exported. x,Helper function that will not be exported. y,Helper function that will not be exported. z!Helper function not for export. 5#parseFile is a file parser for the timQ format. For the output format, the FullyDescriptiveTimeTableProblem data type, p I have included a number of slots per day and number of days. These are constants in this loading routine. 6`Load in a TIM file, but keep the data in the original form, as a large number of grids of bits. 7ˆLoad a TIM file, and transform it into the constrained data format so that the look up tables no longer give back just ones and zeros, E but lists of valid options. This should be easier to work with. 8£Use the raw data to constrain problem. Only rooms that can reasonably be chosen (feature and size constraints) should be available for specific events and so on. M In short I am doing my own constraint (hard coded urg) processing here. 9‘This is for human readability. It will take a raw format and return a comma and new line separated format as a String. Dump the string to a file › and it should now be easy to load into a spread sheet and inspect. I was not comfortable incoding this as a |show| function, it seems to me that there e is far too much information here to easily display it to a user, at least in a terminal window. )*+,-./01234wxyz56789)*+,-./0123456789)*+,-./0123456789 ) *+,-./01234wxyz56789portable provisional'Richard Senington <sc06r2s@leeds.ac.uk> Safe-Inferred:;{|}~<=>€‚ƒ„…:;<=>:;>=<:;{|}~<=>€‚ƒ„…portable provisional'Richard Senington <sc06r2s@leeds.ac.uk> Safe-Inferred?vThere are three possible internal storage forms. A full explicit matrix, an upper triangular matrix or recomputation { from data points. The advantage of full explicit is speed, but it takes more memory. It is also the only option for y asymmetric TSP problems. The triangular matrix is also fast, but can only be used in symmetric problems, and also z still requires quite a bit of memory. Recomputation is the last option, it is slow because it is no longer a lookup w table, but will take much less room. Can only be used with problems where the distance between two points can be J calculated. Currently I am only supporting symmetric TSPs for this. CDThe data type for carrying the combination problem and solution to D the TSP. The route is stored as a dictionary of associations G from vertex name to a pair of values, the name of the preceding C vertex and the next vertex. This forms an infinite loop, so  use carefully. The routeElementToIndex/indexToRouteElement pair store > fixed indexes to the cities. This is intended to allow > a dumb heuristic to decide to switch elements 0 and 2, ? knowing they must be separated by 1 element, rather than = vertices 0 and 2, which may be next to each other, or ) very different parts of the cycle. J_Will generate an IntMap of the path, giving city to next and last city names as the structure. _ This is effectively the edges involved in the process. Wow, how badly written was that. LfInternally the value of the solution is stored as a fixed point value, stored in an Int64 data type. u For external visibility however this function is provided, converting the value into a floating point numbers. M?Internally all edge costs are stored as a fixed point values. t For external visibility however this function is provided, converting the values into floating point numbers. OJConverts the lookup table of a problem into a comma and newline delimited Q string. This should facilitate copying into spreadsheets for checking the < problem being used and validating solutions by hand. PWWill perform a switch of 2 cities in the path. This is by city name, not current index \ in the path. It looks up the current indexes by city name and passes the work off to  exchangeCitiesOnIndex. QDPerforms the bulk of the work for exchanging elements of the cycle. S This version no longer assumes the indices are ordered due to confusion this Y caused in my own code. In addition there was an oversight, when exchanging indices % 0 and last. This is now fixed. RNA brute force recalculation of the current length of the path. Use sparingly. SPTake a path through the system and a problem, insert the path into the system, S calculating distances and setting up appropriate look up tables. It does not T validate the list in terms of going through all the cities, or going through W a city more than once (though this is likely to break other parts of the system Y very very fast). It does organise the list so that the starting node is vertex 0.  Uses the evaluateRouteNaive1 to calculate the length of the path via a brute A force method. This is not expected to be used frequently. TNAn implementation of kexchange methods as a series of combinators. kFragments P will break a problem at specified edges and give back the path segments. c allVariations will take a set of segments and give back every possible combination of them, d and their reversals (I feel this should be broken down further, due to similarities with the _ stochastic segment reversal method). allVariations is also a more general function than < the others, not actually requiring reference to TSP. p minimumVariation is expected to be used with a set of paths (probably generated by the above two methods)  and give only the best. kstochasticReversal and shuffleFragments are similarly not really approapriate just here, but for now they v stay. Together they allow for less detailed k-exchange methods, for example, rather than exhaustively creating t variations, we will use it as a mutator for a GA. For this we might want to only create 1 permutation, which Q can be done as; kFragments >>> shuffleFragments >>> stochasticReversal >>> a s->[concat as] >>> minimumVariation \kFragments will begin by being quite fragile. Please make sure that your input sequence is i assending and does not include duplicates. Remember to initialise your route before calling this. YLShuffles a simple list of cities and then passes off the work to setRoute. ZMConstruct a TSPProblem instance for an Asymmetric TSP. That is, the distance N from A-B is the not necessarily the same as B-A. The actual route will N not be set up initially, the dictionaries will be empty. This could be N used directly for a global search system (branch and bound), or use in  conjunction with setRoute or randomiseRoute" to initialise for local search. ? Internal data structure is always fully explicit matrix. [KConstruct a TSPProblem instance for a Symmetric TSP. That is, the distance R from A-B is the same as B-A. The actual route will not be set up initially, P the dictionaries will be empty. This could be used directly for a global C search system (branch and bound), or use in conjunction with setRoute or  randomiseRoute; to initialise for local search. Should be noted that this N does not create locations and calculate distances, but rather randomly > assigns distances to each edge, making them symmetric. \KConstruct a TSPProblem instance for a Symmetric TSP. The route will not be N initially set up, the dictionaries will be empty. This does create the O vertices of the graph as points in a 2d space, and the lengths of edges D are calculated, so this supports all internal storage types. †[The definition of orderability is much faster, coming down to a simple integer comparison. ‡fThe definition of equality is quite slow, it will check the internal representation of the path that the solution follows. "?@ABCDEFGHIˆJKLMNOPQRSTUVWXYZ[\‰†‡?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\CDEFGHIMLNKJ?BA@OPQTUVXWRYSZ[\?BA@CDEFGHIˆJKLMNOPQRSTUVWXYZ[\‰†‡portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>None ŠJA data type for representing bits of the specification section of a file. = Assumed to be used later as a list of Specifications. ‹Simple 2d Euclidian. ŒAlways rounded up Euclidian. DFor only two types of file. Basically a form of rounded Euclidian. Ž(Distance between two points on the Earth')s surface. This is based upon code that R another developer wrote, based on the code proposed by TSPLIB itself. I am X not sure if this is for an earth shape, or just a sphere. I suspect earth shape. [Test for filtering specification lines, so we only get data we might want to use. Could be ` got rid of as most of the time I do dictionary lookups on the output of the specification  reading routines. Helper routine for readSpecification . Reads a single line (assumes , that input is already line by line). ‘Helper routine for  loadTSPFile.. Reads the specification section of a file. ]@Loads a TSPLIB style file. The first parameter is the internal  storage type from CombinatorialProblems.TSP. It allows for E full matrix, triangular matrix and full recalculation. If the E requested internal storage cannot be used with the file, this E will throw an error (e.g. recomputation where you are given a  full matrix in the file). (The second parameter is the file path. ’Helper routine for  loadTSPFile1. This assumes the input is just points and the % distances must be calculated. “Helper routine for  loadTSPFile9. This assumes the input data is a matrix of some form,  and loads it. ”•–—˜™Šš›œ‹ŒŽžŸ‘]’“]]”™˜—–•Šœ›š‹ŒŽžŸ‘]’“portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>None gNFor the purposes of getting a general impression of the state of the system, L it returns the number of variables in the True, and False positions. hAThe number of unsatisfied clauses in the problem, the inverse of numSATEDClauses  VPartial display function, for usage in show, this displays the logic of the problem. iUPartial display function, for usage in show, displays some general statistics about  the solution status. ‘UPartial display function, for usage in show, displays the setting of each variable. jTAlternative constructor for the data structure. Takes only those elements that can Z not be derived and correctly initialises the other components, such as calculating Y how many clauses are currently evaluating to true. Requires the number of clauses, R the number of variables, the lookup function for variables (variable index W returning two lists, the first is the indexes of clauses in which this variable ` is present, the second list the indexes of clauses in which the inverse of this variable ] is present), the lookup table for clauses (clause index to lists of variable indexes) 2 and the current settings of each variable. kJFor rapid initialisation of problem instances. This fixes the setting of P all variables to either true or false. The effect this has on the number L of clauses that evaluate to true is unknown until it is carried out. lSFor rapid initialisation of problem instances for usage in stochastic algorithms. R Specifically expected to be used for genetic algorithms and other forms of " stochastic meta-heuristic. mTI am not sure how often this will be used in practice, as randomly created problems \ often seem to be quite easy to solve. Requires a source of random numbers, the number V of variables and the number of clauses to create, in that order. It is assumed 0 that 3-SAT problems are the type wanted. n@The first low level operation. Takes a problem and changes the C setting of the indexed variable from true to false. This is B expected to be used in conjunction with other program logic & to select which index to flip. ^_`abcdefgh i‘jklmn’£€^_`abcdefghijklmn^_`abcdefhgimnjkl^_`abcdefgh i‘jklmn’£€portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>NoneovLoading routine that takes the file path and returns a SATProblem. All variables will be set to false in the initial ?setup, and the truth values of all clauses set appropriately. pKSave routine for SATProblem, outputs back into SATLIB cnf format. The code !(loadCNFFile f) >>= (saveAsCNF f) should qhave no effect upon the file. All information such as variable settings and the truth values of clauses is lost. mTo save extra information use standard prelude write file function with show. I will try to improve on that at some point. opopopop₯      !"#$%&'()*+,-./00123456789:;<=>?@@ABCDEFGHHIJKLMNOPQRSTUVWXYZ[\]^_`abbcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ‘’£€₯¦§¨combinatorial-problems-0.0.5CombinatorialOptimisation.TIMFileFormat.TIM(CombinatorialOptimisation.TSP.FixedPointCombinatorialOptimisation.TSPFileFormat.TSPLIBCombinatorialOptimisation.SATFileFormat.SATLIB TimeTablenumberOfEvents numberOfRoomsnumberOfPeoplenumberOfTimeSlotspersonEventLookupeventPersonLookupeventRoomLookuproomEventLookup eventLocation locationEvent personUsageunscheduledEventslastDay lastSlotOfDay overScheduledaynumberDecode dayslotDecode eventsInDaysingleEventInDayCounterlastSlotOfDayCountermoreThanTwoEventsCounterCounter FeatureNumber PersonNumber EventNumber RoomNumberDaySlot DayNumberTimeSlotittcObjectiveValue ittcValidityviewConstrainedProblemviewTimeTableDetailstimeTableDetailsAsCSVtimeTableForRoomAsCSVscheduledescheduleEventdescheduleSlotcurrentlyScheduledEventsRawTimeTableProblemrawNumberOfEventsrawNumberOfRoomsrawNumberOfPeoplerawNumberOfFeaturesrawNumberOfSlotsPerDayrawNumberOfDays rawRoomSizesrawPersonEventLookuprawRoomFeatureLookuprawEventFeatureLookup parseFileloadTIMFileRaw loadTIMFileconvertToConstrainedProblemrawToCSVFP fpToDouble doubleToFP unwrappedFPInternalStorage RecomputationTriangularMatrixExplicitMatrix TSPProblemsolutionValueI edgeCostI numCitiescityNameToIndexindexToCityNamegenerateDirectionalRouteMaprouteMap solutionValueedgeCostgetTSPPathAsListshowEdgeWeights swapCitiesswapCitiesOnIndexevaluateRouteNaivesetRoute kFragments allVariationsminimumVariationshuffleFragmentsstochasticReversalrandomiseRoutemakeASymmetricTSPMapmakeSymmetricTSPMapmakeEuclideanTSPMap loadTSPFile SATProblem numClausesnumSATEDClauses numVariablesvariableLookUp clauseLookUpvariablePositionclausePositiongetTrueFalseCountnumUnSATEDClauses summariseSAT satproblem setAllVarsrandomiseVariablesmakeRandomSATProblem flipVariable loadCNFFile saveAsCNF deschedulechangeInChainsbeforeafter findChain$fShowTimeTable readHeaderreadNum chunkStream invertLookup fixedPoint divConstI divConstD divConstCfpOnefivesix$fRealFP$fFractionalFP$fNumFP$fShowFP$fOrdTSPProblem$fEqTSPProblem cityAtIndex$fShowTSPProblem SpecificationeuclidianDistanceeuclidianDistanceCeilpseudoEuclideanDistance geoDistance isUsefulSpecreadSpecificationLinereadSpecificationloadFromNodePositionsloadFromMatrixSpecificationName DATAPARTTYPEEDGEWEIGHTFORMATEDGEWEIGHTTYPE DIMENSIONTYPEFAILENDSPECUSEFULIGNOREnodeCoordConstedgeWeightConst showSATLogicshowVARPosition$fShowSATProblem$fOrdSATProblem$fEqSATProblem