This repository contains the code used to perform comparisons of the peel-and-bound method and the branch-and-bound method. Details about both algorithms and their implementations can be found in the paper: Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams There is significantly improved version available here

1. Install Julia by following the instructions here. In theory any up-to-date version of Julia should work, but if not, reverting to v1.6.1 will fix any deprecation issues.

2. Clone this repository by following the instructions here

3. Open the terminal on a Mac or the command shell on a Windows. Navigate to the cloned repository and then into the src folder. If you are not sure how to navigate within the temrinal/shell I suggest using a search engine with the phrase "navigating folders in terminal/shell". I am refraining from linking a specific article in case it is removed or edited.

4. Type julia and hit Enter to start the julia REPL. It should look like this after a few seconds:

5. Type include("DDForDP,jl") into the REPL and hit Enter. This will load the code.

6. Once the code is loaded it needs to be compiled. To test that the code is working, and compile it in the process, type solveSOPPeel(8,64, loggingOn=true) into the REPL and hit Enter. After the code is done running, it should have found an optimal solution with a cost of 55. The time and specific solution may vary from computer to computer.

Now that the REPL is running and the code is compiled, there are a few methods available to you. All of the benchmark SOP problems from TSPLIB are already loaded for you. The only function you need to be familiar with is benchmarkSOPs(), but there are several options that can be adjusted. Take note that every time benchmarkSOPs() runs, it starts by solving a small problem to make sure the code has compiled. The results of this run are not saved, only written to the terminal.

• width must be the first input value and it must be an integer. This determines the maximum width decision diagram constructed while the solver is working. A minimum of 2 is required.
• fileName must be the second input value and it must be a string (surrounded by quotation marks). This determines the location of the output file.
• timeLimit must be the third input value and it must be an integer. This determines how long each problem is allowed to run for in seconds.

For example, running benchmarkSOPs(64,"outputFiles/peel_64.txt", 60) will run the solver on all of the benchmark problems for a maximum of 60 seconds, with a maximum decision diagram width of 64, create a file in the outputFiles folder called peel_64, and write all of the results to that file.

The first two optional parameters select the problems to run. Each benchmark problem has an assigned index; the indices are listed in the table at the bottom of this document.

• numStart must be a valid index and determines the first problem to solve. The default value is 1.
• numEnd must be a valid index greater than numStart and determines the last problem to solve. The default value is 41.

For example, running benchmarkSOPs(64,"outputFiles/peel_64.txt", 60, numStart=8,numEnd=9) will limit the solver so it only runs problems br17.10 and br17.12.

• usePeel must be either true or false. If true, the solver will use peel-and-bound. If false, the solver will use branch-and-bound. The default value is true.
• peelSetting must be either peellen or peelf. The default is peellen, changing it to peelf will change the way nodes are selected during peel-and-bound to the frontier method from the last exact node method. The difference is discussed in the paper, and will not be repreated here.

A command using all of the optional parameters may look like this:

benchmarkSOPs(64, "example.txt", 60;numStart=3,numEnd=3,usePeel=false, peelSetting=peelf)