Release Date: January 7, 2008 (initial version); July 21, 2018 (updated version)
The coordinated brute force method, as introduced in our Appetizer "Globe Optimizer," has a unique property: it is originally an exact solution to the hard computational problems, but it can be easily scaled back to a heuristic method only by decreasing the amount of the required space (memory). This memory reduction definitely causes some performance reductions, but there are some tricks & techniques to reduce the performance reduction in this situation. In this research kit, we introduce these techniques and investigate the performance of this method in its heuristic form. In 2008, the important question was how this method works in its weakest form, i.e. the most limited assigned space, when applied to the TSP as the most challengeable NP-C problem. To this end, we set the width of the space tape (see "Globe Optimizer" in our Appetizer series for the concept) to one, and applied the method to the 14 symmetric and 10 asymmetric samples of TSPLIB. As the exact solutions of these samples had been known, we was able to measure the approximation rate for each sample. The interesting result was the low approximation rates: 1.39 in the worst case and 1.10 in the best case. The average approximation rate for the symmetric samples was 1.27 and for the asymmetric ones was 1.23. We also investigated how the results improve when we increase the assigned space. So we increased the width of the space tape to two and repeated the test. The average approximation rate for the symmetric and asymmetric samples decreased to 1.23 and 1.18, respectively. The largest sample we tested had 4461 cities (nodes).
In 2018, we decided to go one step ahead and instead of giving a table of test results to the potential users of this method, deliver them a binary version of the method implementation to enable people to test the method by their own data sets and in their desired situations. To this end, the binary version was developed on both of the Microsoft Windows and Linux platforms and delivered here for free. This binary version supports both of the symmetric (2D Euclidean) and asymmetric data sets that are compatible with the TSPLIB format. It supports up to 5000 cities (nodes) for both of the symmetric & asymmetric samples. This threshold (5000 nodes) is an arbitrary limitation and can be easily increased in the program source code. It also supports multithreading to benefit the maximum computation power of the underlying hardware.
A screenshot from the Windows binary
This research kit contains an executive summary, a research report which explains the techniques to use the coordinated brute force method as a heuristic method, the binary version of the method implementation, and two documented source codes of the method implementations (single & multithreaded implementations) in Free Pascal Language. The source codes can be directly compiled by Lazarus (a free cross platform IDE for Free Pascal) on different platforms. The executive summary and the binary version of the multithreaded implementation are free and can be downloaded from the following links. As our other products, this research kit is released under ATG Blue License. We urge you to read the executive summary before any decision regarding the purchase of this research kit.
This research kit is the extension of our Appetizer entitled "Globe Optimizer." Therefore you must read this paper to be able to follow the technical stuff in this research kit. The firms and individuals who are working on technologies regarding routing, planning, placement, scheduling, computational biology, and discrete optimization in general, are among the potential users of this research kit. The coordinated brute force method is a general optimization technology which can be applied to a range of combinatorial optimization problems including TSP, facility location, knapsack, bin packing, graph coloring, the subset sum, and many mores.
Price (USD): $8,750
Tip: What is a research kit? To be familiar with the concept of research kit and have a complete list of our research kits, please visit this page.