# MIN REVORDER

A C++ code for the solution of a vertex ordering optimization problem, MIN REVORDER, where vertices have required and desired numbers of adjacent predecessors. The main contribution of this code is in the implementation of the branch-and-bound algorithm described in :

"Jérémy Omer, Antonio Mucherino. Referenced Vertex Ordering Problem: Theory, Applications and Solution Methods. Open Journal of Mathematical Optimization, Centre Mersenne, 2021, 2 (6), ⟨10.5802/ojmo.8⟩" [1]

The code also reproduces solution methods described in 

"J. Omer and D. Gonçalves. An integer programming approach for the search of discretization orders in distance geometry problems. Optimization Letters. 2017." [2], and 

"M. MacNeil, M. Bodur. Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems. 2019. <arXiv:1907.12468>" [3]

## How to install

The code requires CPLEX 12.7 or above and the CPLEX install directory must be exported in the environment variable CPLEX_INSTALL_DIR, e.g.,
 
> export CPLEX_INSTALL_DIR="/Users/yourname/Applications/IBM/ILOG/CPLEX_Studio127"

Then, if using a Linux or OSX distribution, it should be sufficient to open a terminal from the local directory of this repository and type

> mkdir bin
> make


## How to use

The main function is to solve the instances described by some input files. This is done by calling, e.g.:

> ./bin/revorder -d benchmark_article/bb_vs_existent -i random* -a bb -L 3 -U 4

The above command runs the branch-and-bound algorithm with default options, L=3 and U=4 on every instance whose name starts with "random" in the directory benchmark_article/bb_vs_existent. The results are then saved in ./benchmark_article/bb_vs_existent/results_BB_2020-03-17.tex, where the end of the file name will change depending on the date. 

To solve these instances by solving an integer programming (IP) formulation, two arguments must be specified. For instance, the following command

> ./bin/revorder -d benchmark_article/bb_vs_existent -i random* -a ip -f ccg -L 3 -U 4

will solve the same random instances with the cycle cut generation algorithm originally described in "J. Omer and D. Gonçalves. An integer programming approach for the search of discretization orders in distance geometry problems. Optimization Letters, 2017". 

Many other usage examples can be found in the script files shared in the ./bashscipts directory. More details on input arguments can also be found by typing:

> ./bin/revorder -help

## Instances, scripts and options

All the instances used in the experiments section of [1] are included in the ./benchmark_article directory, where they are organized similarly to the presentation of the experiments provided in [1]. 

The scripts included in ./bashscripts can be used to reproduce the experiments. 

The option values corresponding to the versions compared in [1] are given in the ./optionfiles directory. One set of options can be used when solving an instance by specifying an option files with the -o argument.

## Citing the code

If the code is useful to your research, please cite:  

"Jérémy Omer, Antonio Mucherino. Referenced Vertex Ordering Problem: Theory, Applications and Solution Methods. Open Journal of Mathematical Optimization, Centre Mersenne, 2021, 2 (6), ⟨10.5802/ojmo.8⟩"