README.md 3.29 KB
Newer Older
Omer Jeremy's avatar
Omer Jeremy committed
1
2
# MIN REVORDER

Jérémy's avatar
Jérémy committed
3
4
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 :

Omer Jeremy's avatar
Omer Jeremy committed
5
"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]
6

Omer Jeremy's avatar
Omer Jeremy committed
7
The code also reproduces solution methods described in 
Jérémy's avatar
Jérémy committed
8

9
"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 
Jérémy's avatar
Jérémy committed
10

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"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:  

Omer Jeremy's avatar
Omer Jeremy committed
55
"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⟩"
56

Omer Jeremy's avatar
Omer Jeremy committed
57