Skip to content

Latest commit

 

History

History
65 lines (44 loc) · 3.03 KB

README.md

File metadata and controls

65 lines (44 loc) · 3.03 KB

TurnpikeMM: A Paper's Code Repository

This repository contains the code implementation for the paper A Much Faster Heuristic for Turnpike Problem with Measurement Uncertainty. It provides a step-by-step guide on how to set up your environment, compile the required dependencies, and execute the tests. Follow the instructions below to get started.

Prerequisites

  1. Python 3.10: Download and install Python 3.10. We recommend using Anaconda for easy management of Python environments.
  2. C++20-compliant compiler: Ensure you have a C++ compiler that supports C++20. Popular options include GCC 10 or later and Clang 11 or later.
  3. Boost: Download and install the most recent version of the Boost C++ Libraries.
  4. Eigen: Download and install the most recent version of the Eigen C++ Library.

For macOS users with Homebrew, Boost and Eigen can be installed with:

brew install boost
brew install eigen

For Ubuntu users, Boost and Eigen can be installed with:

sudo apt-get update
sudo apt-get install libeigen3-dev
sudo apt-get install libboost-all-dev

Installation

Once you have the prerequisites installed, follow these steps to set up the TurnpikeMM project:

  1. Open a terminal and navigate to the root directory of the TurnpikeMM repository.
  2. Change directory to TurnpikeMM: 
 cd TurnpikeMM
  1. Install the Python package: 
 python3.10 -m pip install -e .

Running the Tests

After installing, you can run our experiments with the following:

  1. Change directory to turnpike-solver-tests: 
 cd ../turnpike-solver-tests
  1. Run the experiment script: 
 ./run-synthetic.sh

This script will run a series of tests on synthetic data, generating results and performance metrics for the TurnpikeMM algorithm. You can view the output in the terminal and/or log files generated by the script.

Use

You only need one thing to use the solver: a distance set. It is helpful to have a rough estimate of the distance set's uncertainty, but the estimate only improves runtime. Just set a sufficiently high threshold (e.g., as large as your largest distance) if you don't have one.

To solve a Turnpike instance,

from TurnpikeMM.worker import solve 
z = solve(d, uncertainty)

The vector z is the method's point vector estimate. It satisfies the symmetry-breaking constraints detailed in the paper.