RL4Presolve

This is the Clp version of our code for paper RL4Presolve: Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning published on IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI).

Installation

The installation for Clp-based training environment is relatively complex. Please be patient for the installation.

Clp Installation

The installation process is mostly the same as the official instructions of Clp here. Specifically, we modified the LP solver Clp and the dependency CoinUtils. Thus, we have to build them from the source codes manually.

Step1: Download Clp and Dependencies

There are several dependencies required by Clp. We use the official scrip coinbrew to download the source codes.

# create new directory
mkdir clp_install
cd clp_install
# download all source codes
wget https://raw.githubusercontent.com/coin-or/coinbrew/master/coinbrew
chmod u+x coinbrew
./coinbrew fetch Clp@master

Step2: Apply Patch to CoinUtils

We only add a C++ inline function in the header file CoinPresolveMatrix.hpp to record the current number of non-zero elements. Apply the patch file in this repository by:

# apply the patch to CoinUtils
cd CoinUtils
git reset --hard aae9b0b
patch -p1 < ../../clp_patch/coin_utils.patch

Step3: Apply Patch to Clp

We made some modifications on the original Clp codes to support ML modules and detailed logs for presolve. Install the modified Clp by:

# apply the patch to Clp
cd ../Clp
git reset --hard 0b977de
patch -p1 < ../../clp_patch/clp.patch

Step4: Install Clp

Use the coinbrew to install the modified Clp:

# install Clp
cd ..
./coinbrew build Clp

Generally, coinbrew will install Clp and its header files and libraries at ./clp_install/dist/ , where the path "." is the directory of this repository.

Note: If the installation fails, the most possible reason is that some system packages are misssing (e.g., pkg-config for Linux). Please check the output of coinbrew first.

Python Environment

The python environment requires:

• A GPU equipped machine
• Python 3.9
• Pytorch 1.13.1
• (*) PyTorch Geometric 2.0.4 (see explanations below)
• See requirements.txt for all required packages

Note: Generally, different versions of required packages might not influence much. However, we observe that the interface of the function global_add_pool in the package torch_geometric changed slightly in the latest version, making it incompatible to that used in our codes. Thus, we have to specify the versions of torch_geometric. Other versions may also work, but we have not tested.

This python environment can be installed easily and thus we omit the detailed instructional codes.

Python Clp Interface

The official python interface CyLP requires Cbc to be installed, whose installation requires additional efforts. To simplify the installation, we implement a more lightweight interface using the shared object (i.e., the dynamic link library) of Clp.

To install that:

# (*) Step1: set CLP_INSTALL_DIR to the installation directory of Clp.
# Generally, the installation directory is /<path\_to\_rl4presolve>/clp_install/dist/ as mentioned above.

# (*) Step2: set LD_LIBRARY_PATH to the directory of shared object of Clp.
# This directory usually is /<path\_to\_rl4presolve>/clp_install/dist/lib.

# Step3: python Clp interface installation
cd ../clp_interface
python -m pip install --compile .

Data Generation

Here we provide data generation scripts of the benchmarks 4-8 mentioned in our paper. We will further open source the benchmark Production Planning once the manuscript is accepted (as mentioned in our paper).

Some scripts modified from previous work generate instance files in .lp form, which are incompatible to Clp that reads .mps files. Thus, the scripts use gurobipy to convert the files.

For example, to generate the benchmark multicommodity network flow:

cd ../data_generation_scripts
python generate_multicommodity_network_flow.py

The above codes will generate 1000, 16, and 64 instances for training, valid, and test.

Note: The python script for generating generalized network flow instances requires AMPL and gnetgen to be installed. You are required to install them following their official instructions and then set their installation paths to the python script.

Training and Evaluation

Training

There are mainly two python scripts to launch our codes:

• 01_train_default.py: This code is used to train presolve agents.
• 02_test_network.py: This code is used to evaluate the trained agents.

For example, to train a presolve agent on multicommodity network flow:

cd ../rl4presolve
python 01_train_default.py

Then it will train the agent with one GPU and one processing. All hyperparameters used for training are set in the config file /path_to_rl4presolve/rl4presolve/settings/train_defaults.yaml, e.g.,

• experiment name and repeated times (with different seeds)
• number of instances for training, number of processings and GPU devices
• evaluation interval, number of instances for evaluation, and the max solving time before timeout
• types of networks and input features
• hyperparameters used for PPO algorithms

By default, the logdir for training is /<path_to_rl4presolve>/data/results/clp/train/<instance_name>/<exp_name>/<exp_time>_<git_sha>. The logs include:

• configs.json file records all the configs used in this experiment.
• progress.csv file records detailed information at each evaluation step:
  • current environment steps and train iterations;
  • current improvement over default presolve rule;
  • number of executed presolvers & presolve sequences;
  • number of reduced rows & columns & non-zero elements;
  • time of total solving & presolve & LP algorithm (dual simplex by default) & post-solve;
  • time of state generation & feature extraction & agent decision.
• log.txt file records detailed outputs for Clp and our training codes.
• best.txt file records the best performed rl agent on valid set.
• tb folder records more detailed information at each training step (by default, we execute ten training steps between two evaluation steps):
  • most information recorded in progress.csv for each training step;
  • the ratio of clipped probabilities;
  • the KL divergence of the original policy and the policy after one training step;
  • the training loss of the actor, the critic, and the entropy term.
• state_dict folder records the state dict of the pytorch neural network at each evaluation step.
• details folder records the detailed presolve processes of each LP instance in the valid set at each evaluation step, which includes:
  • the total number of executed presolvers;
  • the list recording all the executed presolvers;
  • the number of rows & columns & non-zero elements after each presolver executed;
  • the time cost (millisecond) for each presolver.

Evaluation

To compare the trained presolve agent with the default rule, you have to specify the logdir of the above training experiment for the evaluation script:

python 02_test_network.py +logdir=</log_dir/to/training/experiment>

To further test the generalization ability:

# generalization ability to larger instances
python 02_test_network.py test_type=transfer_benchmark +instance_type=<name_of_the_larger_benchmark> +logdir=</log_dir/to/training/experiment>
# generalization ability to the primal simplex and the interior point methods
python 02_test_network.py test_type=transfer_lp +logdir=</log_dir/to/training/experiment>

Similar to that for training, the logdir for evaluation is /<path_to_rl4presolve>/data/results/clp/test_network/<instance_name>/<exp_name>/<exp_time>_<git_sha>_<test_type>_<training_log_name>. The logs for evaluation here are similar to that for training described above.