+f      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeportable provisional'Richard Senington <sc06r2s@leeds.ac.uk>.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. fghijNA 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. )  !"#$%&'() !&'%" #$()   !"#$%&'(portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>)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. *+,-./01234k,Helper function that will not be exported. l,Helper function that will not be exported. m,Helper function that will not be exported. n!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. 7Load 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. 8Use 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. 9This 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. )*+,-./0123456789)*+,-./0123456789) *+,-./01234*+,-./0123456789portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>:;opq:;:;:;;portable provisional'Richard Senington <sc06r2s@leeds.ac.uk><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. =>?@DThe 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. ArBsCDEFfInternally 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. G?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. HIJConverts 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. JWWill 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. KDPerforms 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. LNA brute force recalculation of the current length of the path. Use sparingly. MPTake 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. NLShuffles a simple list of cities and then passes off the work to setRoute. OMConstruct 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. PKConstruct 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. QKConstruct 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. <=>?@ABCDEFGHIJKLMNOPQ@ABCDEGFH<?>=IJKLNMOPQ<?>==>?@ABCDEABCDEFGHIJKLMNOPQportable provisional'Richard Senington <sc06r2s@leeds.ac.uk>tJA data type for representing bits of the specification section of a file. = Assumed to be used later as a list of Specifications. uvwxySimple 2d Euclidian. zAlways 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. R@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. RRRportable provisional'Richard Senington <sc06r2s@leeds.ac.uk>STUVWXYZ[\NFor 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. ]AThe 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. ^UPartial 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. _TAlternative 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. `JFor 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. aSFor 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. bTI 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. c@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. STUVWXYZ[\]^_`abcSTUVWXYZ[]\^bc_`aSTUVWXYZ[TUVWXYZ[\]^_`abcportable provisional'Richard Senington <sc06r2s@leeds.ac.uk>dvLoading 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. eKSave 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. dedede      !"#$%&'()*+,-./00123456789:;<=>?@@ABCDEEFGHIJKLMNOPQRSTUVWWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~combinatorial-problems-0.0.4CombinatorialOptimisation.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 loadTIMFileconvertToConstrainedProblemrawToCSVFPInternalStorage RecomputationTriangularMatrixExplicitMatrix TSPProblemrouteMap numCitiesrouteElementToIndexindexToRouteElement solutionValueedgeCostgetTSPPathAsListshowEdgeWeightsexchangeCitiesexchangeCitiesOnIndexevaluateRouteNaivesetRouterandomiseRoutemakeASymmetricTSPMapmakeSymmetricTSPMapmakeEuclideanTSPMap loadTSPFile SATProblem numClausesnumSATEDClauses numVariablesvariableLookUp clauseLookUpvariablePositionclausePositiongetTrueFalseCountnumUnSATEDClauses summariseSAT satproblem setAllVarsrandomiseVariablesmakeRandomSATProblem flipVariable loadCNFFile saveAsCNFchangeInChainsbeforeafter findChain deschedule readHeaderreadNum chunkStream invertLookup doubleToFPfivesixsolutionValueI edgeCostI SpecificationFAILENDSPECUSEFULIGNOREeuclidianDistanceeuclidianDistanceCeilpseudoEuclideanDistance geoDistancereadSpecificationLinereadSpecificationloadFromNodePositionsloadFromMatrix showSATLogicshowVARPosition