úÎwhu>(      !"#$%&'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.  JConverts 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. WWill 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. DPerforms the bulk of the work for exchanging elements of the cycle. Q It assumes that the order of the indexes is increasing (e.g. 0 2 not 2 0). R While changing the order it will also calculate the change in value of the R route and update this. This is performed fairly efficiently by finding the R edges being removed, and the edges being created and adding the difference - between the two to the current price. NA brute force recalculation of the current length of the path. Use sparingly. PTake 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. LShuffles a simple list of cities and then passes off the work to setRoute. MConstruct 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.      portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>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. #SFor 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. $TI 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. %@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.  !"#$% $%!"# !"#$%portable provisional'Richard Senington <sc06r2s@leeds.ac.uk>&vLoading 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. 'KSave 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. &'&'&'*      !"#$%&'()*+,combinatorial-problems-0.0.1CombinatorialOptimisation.TSPCombinatorialOptimisation.SATFileFormat.SATLIBInternalStorage RecomputationTriangularMatrixExplicitMatrix TSPProblem currentPricerouteMap edgePrices numCitiesrouteElementToIndexindexToRouteElementshowEdgeWeightsexchangeCitiesexchangeCitiesOnIndexevaluateRouteNaivesetRouterandomiseRoutemakeASymmetricTSPMapmakeSymmetricTSPMapmakeEuclideanTSPMap SATProblem numClausesnumSATEDClauses numVariablesvariableLookUp clauseLookUpvariablePositionclausePositiongetTrueFalseCountnumUnSATEDClauses summariseSAT satproblem setAllVarsrandomiseVariablesmakeRandomSATProblem flipVariable loadCNFFile saveAsCNF showSATLogicshowVARPosition