Paper Experiments (Algebraic)

How to reproduce paper experiment (algebraic)

1. Links

• Paper link: (ArXiv)
• Graph instances (OSF): in the data/alenex25 directory

2. Building executable

• Install dependencies described in README.md:
  • C++ compiler supporting the C++14 standard and OpenMP (GCC recommended)
  • GNU Make
  • CMake Version 3.24 or later
  • CLI11 (included in this repository)
  • Gurobi Optimizer:
    • Version 11.0.1 on Mac/Linux
      • You may need to recompile libgurobi_c++.a. See this post.
    • Version 9.0.3 on Linux
• In the Files section on OSF, click on acda-25 -> OSF Storage (United States).
• Click on Download as zip and download files as osfstorage-archive.zip
• Extract osfstorage-archive.zip.
• In the extracted directory, run make. Make sure that build/Release/ip-solver is created.

3. Running solver

• Generated graph instances are stored in the data/crisp and data/drone directories.
  • Each instance consists of three files: {graph_prefix}_vertex, {graph_prefix}_edge, and {graph_prefix}_conf.
  • These files were created by build_graph from IRIS, and reduce-poi, filter-poi from Robotic Brewing.
    • Stage 1: graph_build {rrg_seed} {n} {stage1_data_prefix}
    • Stage 2: reduce-poi {stage1_data_prefix} data/poi/{crisp or drone}_poi.txt -k {10 or 12} -a greedy --seed 1 > {stage2_data_vertex}
    • Stage 3: filger-poi {stage1_data_vertex} {stage2_data_vertex} > {stage3_data_vertex}
    • {graph_prefix}_edge and {graph_prefix}_conf are not affected by stages 2 and 3.
• Run the following command: build/Release/ip-solver -a algebraic -l debug -s 0 -j {num_threads} --seed {seed} --scale {scaling_factor} --algebraic-compact {circuit_type} --algebraic-search {search_strategy} --algebraic-recovery {recovery_strategy} {graph_prefix}
  • {num_threads}: number of threads
  • {seed}: seed 1, 2, 3
  • {scaling_factor}: scaling factor
  • {circuit_type}: circuit type (naive, standard, semicompact, compact)
  • {search_strategy}: search strategy (0: Standard Binary Search, 1: Probabilistic Binary Search, 3: Unified Search)
  • {recovery_strategy}: recovery strategy (mc (Monte Carlo), lv (Las Vegas))
  • {graph_prefix}: path to the input graph instance (e.g. data/alenex25/crisp_n50_k10)
• Example: build/Release/ip-solver -a algebraic -l debug -s 0 -j 8 --seed 1 --scale 50 --algebraic-compact semicompact --algebraic-search 3 --algebraic-recovery lv data/alenex25/crisp_n50_k10
  • This will finish within a few minutes and output a walk with weight 15.6540890000.