You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
84 lines
2.8 KiB
84 lines
2.8 KiB
[](https://doi.org/10.5281/zenodo.1064311)
|
|
|
|
Intersection Cuts for Single Row Relaxations
|
|
============================================
|
|
|
|
This package contains the source code for the wedge cut generator
|
|
described in the paper **Intersection Cuts for Single Row Relaxations**,
|
|
by Ricardo Fukasawa, Laurent Poirrier and Álinson S. Xavier.
|
|
|
|
|
|
Required Tools and Libraries
|
|
----------------------------
|
|
|
|
To produce the tables in the paper, the following tools and libraries were
|
|
used. Different versions may produce slightly different outputs.
|
|
|
|
- GNU Make, version 3.81
|
|
- CMake, version 3.5.1
|
|
- GCC, the GNU Compiler Collection, version 4.8.4
|
|
- GMP, the GNU Multiple Precision Arithmetic Library, version 6.1.0
|
|
- Ruby, version 1.9.3
|
|
- IBM® ILOG® CPLEX®, version 12.6.2
|
|
|
|
|
|
Build instructions
|
|
------------------
|
|
|
|
1. Make sure that CPLEX is correctly installed in your system and that
|
|
the paths in `cmake/FindCPLEX.cmake` point to the correct install location.
|
|
2. Navigate to the folder `build` and run `cmake ..` followed by `make`
|
|
3. After the compilation is finished, two binaries will be generated inside
|
|
the `build` folder: a library `libonerow.a`, which can be used
|
|
independently to generate wedge cuts, and an executable
|
|
`onerow-benchmark.run`, which can be used to run the experiments presented
|
|
in the paper.
|
|
|
|
Running the experiments
|
|
-----------------------
|
|
|
|
1. Navigate to the folder `onerow/benchmark`.
|
|
2. To run the computational experiments for all instances, run:
|
|
|
|
./make
|
|
|
|
3. To run the computational experiments for a particular instance, give the
|
|
filename as argument. For example:
|
|
|
|
./make instances/30n20b8.pre.done
|
|
|
|
4. To run the computational experiments for multiple instances in parallel,
|
|
the option -j can be used. For example, to run four instances simultaneously,
|
|
run:
|
|
|
|
./make -j4
|
|
|
|
5. Two files will be generated per instance, inside the folder `out`. One file
|
|
contains the log, which was printed to the terminal during the execution,
|
|
while the other file (ending in .yaml), contains the experiment results.
|
|
|
|
|
|
Generating the tables
|
|
---------------------
|
|
|
|
1. Navigate to the folder `onerow/benchmark`.
|
|
2. Run the computational experiments, as describe above.
|
|
2. After the experiments are finished, run `./generate_tables`.
|
|
3. Extended versions of Table 1 and 2 will be printed, in CSV format. A
|
|
copy will also be saved in `onerow/benchmark/tables`.
|
|
|
|
Heuristics
|
|
----------
|
|
|
|
Many parameters for the cut generator can be specified by modifying the
|
|
file `params.hpp`, located in `onerow/library/include/onerow/`.
|
|
For example, the three heuristics described in the paper can be achieved
|
|
by setting:
|
|
|
|
MAX_CUT_DEPTH = 5
|
|
MAX_R1_RAYS = 100
|
|
MAX_GOOD_ROWS = 100
|
|
|
|
After changing these parameters, it will be necessary to recompile the
|
|
project.
|