Incorporating Bounds from Decision Diagrams into Integer Programming

This is the implementation used to produce the computational results in the following paper:

• C. Tjandraatmadja and W.-J. van Hoeve, Incorporating Bounds from Decision Diagrams into Integer Programming. To appear.

In this paper and implementation, we generate dual bounds from relaxed decision diagrams with the goal of improving pruning throughout the branch-and-bound tree of a MIP solver. We use Lagrangian relaxation and constraint propagation to take into account constraints that are more difficult to tackle with decision diagrams. We test this approach on the independent set problem with and without knapsack side constraints.

The main requirements are SCIP 5.0.1, ConicBundle 0.3.11, Boost, and a C++ compiler in a Linux environment. Python 2.7 with numpy and matplotlib is required to process data and plot graphs.

Please be aware that the code quality is at research level and this repository will not be maintained or supported. Its main purpose is to allow and facilitate the reproducibility of the results contained in the above paper. However, you are free to adapt it to your own purposes; see LICENSE.md for more details.

Along with the code and the scripts for reproducing the experiments, we include instances from the runs done for the paper. Full output files are not included as they are too large.

Instructions for reproducing the experiments in the paper are below. For information about the options supported by the program, see OPTIONS.md.

Instructions

In order to reproduce the results, you need to perform the following three steps after downloading the package and unpacking it:

1. Compile the code;
2. Run the test scripts; and
3. Run the plotting scripts.

The test scripts are Bash scripts that run all experiments involved in the paper. The plotting scripts are Python scripts that process the output and plot the graphs shown in the paper.

You should unpack the package in the machine you will run the experiments; however, the plotting scripts support remote access via ssh and can be used in a different machine. See further below for more details.

Compiling the code

The code is in the directory ddopt. To compile it, follow these steps:

1. Ensure you have all dependencies: SCIP 5.0.1 (other versions may work), ConicBundle, Boost, and a C++ compiler.

By default, the include and lib directories for ConicBundle are expected to be in ddopt/ConicBundle. SCIP is expected to be in ddopt/scip-5.0.1. These can be changed by modifying the CONICBUNDLEDIR and SCIPDIR variables in the Makefile.

2. Run make to compile the code.

Running the test scripts

The test scripts are in the directory experiments. You must have compiled the code to perform this step. The Makefile will automatically copy the binary to the experiments/bin directory, which will be used by the test scripts.

Note: If you want to run a smaller test, run ./reduce_instance_set.sh in order to keep only the first 3 numbered instances for each set of instances.

There are five sets of experiments, which will run the experiments with appropriate flags for each set of instances. The scripts with the "parallel" suffixes are trivial parallel versions.

Running the plotting scripts

The plotting scripts are in the directory experiments. You must have run the experiments to completion to perform this step, which may take days if performed on the full set of instances. The scripts require numpy, matplotlib, and optionally paramiko if used remotely. Make sure that you use Python 2.7.

1. Configure the plotting settings. These are at the top of settings.py and there are four options that can be configured:

   • USERHOST: If the files are available locally, leave this as is (as an empty string ""). If the files are in a remote server, this is the address of the server in the format "[username]@[hostname]". The server is accessed via ssh (port 22).

   • PATH: This is the path of the output files, whether locally or on a server.

   • OUTPUT_DIR: This is the directory where the plots will be created.

   • PLOT_COLOR: Set this to True if plots should be colored.

2. Run python plot_results.py all.

This will process the output files and generate all plots. Specific plots can be generated by providing different arguments; run python plot_results.py without arguments to obtain a list.

Other files

Other than the code and the scripts included above, we include:

• Instances: The directory experiments/instances contains all instances used for the experiments.

Code structure

• bdd/: Basic structure for binary decision diagrams. bdd.hpp and bdd_node.hpp contain the decision diagram structure itself, including functions to manipulate it. bdd_pass.hpp contains generic functions to perform top-down or bottom-up computations on the decision diagram.

• core/: Functions for constructing decision diagrams, including relaxed decision diagrams. The functions in solver.hpp are responsible for the construction, with callback functionality as defined in solver_callback.hpp. The possible orderings for decision diagrams are in orderings.hpp, managed by order.hpp. Relaxed decision diagrams require mergers, in mergers.hpp, handled by merge.hpp.

• ip/: Functions to build and solve the MIP model and generate bounds from decision diagrams. This includes a SCIP relaxator in relax_dd.h which builds decision diagrams and generates bounds. ip_scip.hpp contains the main function that solves the MIP.

• lagrangian/: Functions related to generating bounds via Lagrangian relaxation. There are a number of different implementations. For the paper, we highlight the following files. lagrangian_cb.hpp handles the Lagrangian relaxation itself with the ConicBundle library. lg_dd_selector_ct_scip.hpp is responsible for selecting the Lagrangian constraints for the clique table (see also lg_constraint.hpp and lg_constraint_scip.hpp). Lagrangian subproblems are in lg_subprob_*.hpp, which include optimizing over the decision diagram (lg_subprob_bdd.hpp) and checking for feasibility to obtain a primal bound (lg_subprob_feas.hpp).

• problem/: Problem-dependent structure, such as instances, domains, mergers, orderings, states (including transition function), etc. There are three available problems: bp, cliquetable, and indepset. For the paper, we only use cliquetable (conflict graph). The problem definition and DP formulation are in cliquetable_problem.hpp, cliquetable_instance.hpp, and cliquetable_state.hpp. The propagation of linear inequalities is in ct_prop_linearcons.hpp.

• util/: Data structures (graph, set), options, timing, macros.

Acknowledgments

This implementation has early origins in the code from the following paper:

• D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker. Optimization Bounds from Binary Decision Diagrams. INFORMS Journal on Computing, 26(2):253--268.

It was very heavily modified since then. Their original code is available here. A similar derived code for cutting planes from decision diagrams is available in the ddopt-cut repository.

All work (except minor edits) was done while C. Tjandraatmadja was at Carnegie Mellon University.