MIP formulations for Deletefree AI Planning

Version: 2.4.2

Refer to the Changelog for info about versions.

Abstract

We investigate existing Mixed Integer Programming (MIP) formulations for cost-optimal delete-free STRIPS Planning: these models are built by enforcing acyclicity in the underlying causal relation graphs using time labeling and vertex elimination methods. We then propose two new approaches to modeling acyclicity, one based on dynamically identifying subtour elimination constraints, and the other based on disjunctive landmark constraints. In addition, we propose to warm start the models with the landmarks computed by the LM-cut heuristic, and describe a simple greedy primal heuristic to provide a starting feasible solution to the MIP solver. Our results demonstrate that the proposed techniques outperform the current state of the art, both in space and time efficiency.

Publications associated to this code

Master thesis in Computer Engineering: [pdf]
IJOO MIP Workshop 2025: Work in progress

Index

• Requirements
• Build/Run
• Parameters
  • CMake
  • Make
  • Execution

Requirements

• UNIX based OS
• cmake 3.20 +
• This software requires as input the SAS file produced by the Fast Downward translator (this software was produced with version 3 of the FDW translator as a reference)

Build/Run instructions

While inside the root folder of this repo:

# to build
mkdir code/build
cd code/build
cmake <build_options> ..
make <target_option>

# to run the code on an instance
./hplus <input_file> <parameters>

Build options (CMake parameters)

• -DCPLEX_PATH=<path_to_cplex>: (absolute path), specify a custom path to the CPLEX installation (see the CMakeLists.txt to see which are the default ones (CPLEX_POSSIBLE_PATHS) or append your to that list to avoid specifying it every time)
• -DENABLE_WARNINGS= 1: enable all types of compile warnings (default is 0)

Target options (Make parameters)

• <target_option> : specify the target build
  • none : no flag added (default build)
  • opt : optimization flags added (optimized build)
  • debug : debugging flags added (debug build)
  • clear : removes all files inside the code/build folder

Run options

See the help page:

# to view commands available
./hplus --h