We implement several recent algorithms for the satisfiabiiity problem in propositional logic and test them on a wide variety of benchmark problems. We focus on algorithms based on some kind of tree search, including three versions of the classical Davis-Putnam-Loveland method, the method of Jeroslow and Wang, the Horn Relaxation method of Gallo and Urbani, the branch and cut method of Hooker and Fedjki, and the column subtraction method of Harche and Thompson. We design experiments so as to identify the important factors that influence the performance of tree search algorithms. We find that the choice of which variable to branch on is a key factor. Methods based on weak relaxations (e.g., Horn relaxation) are best for easy problems, and the column subtraction method is clearly the most robust, as it was the only algorithm to solve the hardest problems. if Davis-Putnam-Loveland is properly implemented, it and the remaining methods generally excel on problems that are neither too easy nor too hard. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A computer code for the transportation problem that is even more efficient than the primal-dual method is developed. The code uses the well-known (primal) MODI method and is developed by a benefit-cost investigation of the possible strategies for finding an initial solution, choosing the pivot element, finding the stepping-stone tour, etc. A modified Row Minimum Start Rule, the Row Most Negative Rule for choice of pivot, and a modified form of the Predecessor Index Method for locating stepping-stone tours were found to perform best among the strategies examined. Efficient methods are devised for the relabeling that is involved in moving from one solution to another. The 1971 version of this transportation code solves both 100 × 100 assignment and transportation problems in about 1.9 seconds on the Univac 1108 Computer, which is approximately the same time as that required by the Hungarian method for 100 × 100 assignment problems. An investigation of the effect on mean solution time of the number of significant digits used for the parameters of the problem indicates that the cost parameters have a more significant effect than the rim parameters and that the solution time “saturates” as the number of significant digits is increased. The Minimum Cost Effect, i.e. the fact that total solution time asymptotically tends to the time for finding the initial solution as the problem size is increased (keeping the number of significant digits for the cost entries constant), is illustrated and explained. Detailed breakup of the solution times for both transportation and assignment problems of different sizes is provided. The paper concludes with a study of rectangular shaped problems.

Adjacent extreme point problems involving a tree basis (e.g. the transportation problem) require the determination of cycles which are created when edges not belonging to the basis are added to the basis-tree.This paper offers an improvement over the predecessorindex method for finding such cycles and involves the use of a distance function defined on the nodes of the tree, in addition to the predecessor labels.It is shown that the relabeling associated with a basis change can be minimized by defining yet another function called the successor function.The algorithms for labeling and relabeling are then specialized for the specific case of transportation problems.

article Free Access Share on An Algorithm for Finding a Minimum Equivalent Graph of a Digraph Authors: Dennis M. Moyles Carnegie-Mellon University, Pittsburgh, Pennsylvania Carnegie-Mellon University, Pittsburgh, PennsylvaniaView Profile , Gerald L. Thompson Carnegie-Mellon University, Pittsburgh, Pennsylvania Carnegie-Mellon University, Pittsburgh, PennsylvaniaView Profile Authors Info & Claims Journal of the ACMVolume 16Issue 301 July 1969pp 455–460https://doi.org/10.1145/321526.321534Published:01 July 1969Publication History 61citation1,053DownloadsMetricsTotal Citations61Total Downloads1,053Last 12 Months101Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF