Baryonyx is an integer and binary linear programming solver based on the Dag Wedelin heuristic.
Copyright © 2017-2020 INRA
The software is released under the MIT license. See the LICENSE file.
-
cmake(≥ 3.11) -
C++ compiler with C++17 support:
For recent Debian GNU/Linux and Ubuntu derivatives (remove clang to only use gcc):
apt-get install build-essential cmake clangFor Windows, install the CMake program and Visual Studio 2019 (MSVC). You may also install the vcpkg program to install nlopt and other dependencies.
-
nloptlibrary - optimization library to automatic parametrization of the Baryonyx solver parameters.
First, we clone Baryonyx git repository and the submodule.
git clone https://github.com/quesnel/baryonyx.git cd baryonyx git submodule update --init --recursive
Default, Baryonyx provides a shared library libbaryonyx-0.5.so (with
hidden symbol), a static library libbaryonyx-0.5.a (all symbols are
public) and an executable baryonyx-0.5. To compile and install in
the default CMake install directory:
cd baryonyx mkdir build cd build cmake -DCMAKE_BUILD_TYPE=Release .. make install
Previous command line install Baryonyx program and library into the
/usr/local prefix. If you install into another directory, you need
to define three environment variables (into your .bashrc or
equivalent). If you install into $HOME/usr for example, you need to
define in your .bashrc:
export PATH=$PATH:$HOME/usr/bin export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$HOME/usr/lib export PKG_CONFIG_PATH=$PKG_CONFIX_PATH:$HOME/usr/lib/pkgconfig
Then run the following commands:
cd baryonyx mkdir build cd build cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=$HOME/usr .. make install
To override the default build flags, remove the CMAKE_BUILD_TYPE
parameter and override the CXXFLAGS as follow:
export CXX=g++-8 export CXXFLAGS='-Wall -Wextra -Werror -ftree-vectorize -mmmx -msse -msse2 -msse3 -O3' cmake -DCMAKE_INSTALL_PREFIX=$HOME/usr ..
The CMake script provide parameters to control debug, log facility and optimization.
| name | default | summary |
|---|---|---|
WITH_LOG |
ON |
Enable log message on standard output. |
WITH_DEBUG |
ON |
Enable maximum debug function and add more log message. Be careful, this mode slow down computation. |
WITH_FULL_OPTIMIZATION |
OFF |
Enable optimal computation but remove some control on float and control. |
First, we need to update the Git repository with the following commands:
cd baryonyx git pull -r git submodule update --recursive
Then go to the build directory and restart compilation and installation :
cd baryonyx mkdir build cd build cmake -DCMAKE_BUILD_TYPE=Release .. make install
To run Baryonyx in solver mode (i trying to valid all constraints):
baryonyx-0.5 file.lp
To run baryonyx into the heuristic model (i trying to valid all
constraints and optimize the solution), add a -o or --optimize
option to the command line:
baryonyx-0.5 -o file.lp
The Baryonyx solver have many parameters. Some parameters are global, some specific for the optimization algorithms.
| name | type | summary |
|---|---|---|
--help -h |
Show help message |
|
--quiet -q |
Remove many console output |
|
--bench [name] |
Start benchmark. Need csv input files |
|
--optimize -O |
Start Baryonyx in optimization mode, default is to use the solve mode |
|
--limit -l -plimit |
integer |
number of loop to stop algorithm |
--verbose -v |
integer |
verbose level from 0 (very very verbose in debug mode) to 7 (quiet) |
--disable-preprocessing -np |
disable the use of preprocessing |
|
--random |
use the pure random solver (for benchmark) instead of the Bastert/Wedelin algorithm. |
|
--auto[:= ]value |
string |
Select the type of optimizer meta-heuristic. Values are:
|
To assign parameters to solver or optimizer algorithms, use the -p
[name]:value syntax in the command line:
| name | type | summary |
|---|---|---|
time-limit |
real |
time in second to stop algorithm or stop the optimize mode |
limit |
integer |
number of loop to stop algorithm |
w |
double |
warmup-iterator [0, 1] A percentage of |
theta |
real |
history parameters [0, 1[ |
delta |
real |
influence parameters [0, +oo[ |
kappa-min |
real |
kappa minimal value [0, kappa-max |
kappa-step |
real |
kappa updater [0, +oo[ |
kappa-max |
real |
kappa maximal value ]kappa-min, +oo[ to stop algorithm |
alpha |
real |
adaptiveness parameter |
pushing-k-factor |
integer |
use to lower the kappa using the push system |
pushes-limit |
integer |
number of push before stopping the algorithm |
pushing-objective-amplifier |
real |
use to make r more similar to costs |
pushing-iteration-limit |
integer |
number of loop before trying a new push |
norm |
string |
Select the cost normalization function
|
constraint-order |
string |
Remaining constraints order. Values are:
|
preprocessing |
string |
Constraints matrix A order. Values are:
|
observation |
string |
Select the type of observation mechanism (only in solve mode)
|
floating-point_type |
string |
Select the type of real use internally in the solvers. Values are:
|
print-level |
integer |
show information if greater than 0 |
storage-type |
string |
Change the solution storage policy for the optimizer mode.
|
init-policy (solver only) |
string |
Change the initialization and reinitialization policy of the solution vector. Values are:
|
init-policy-random (solver only) |
real |
[0-1] (default, 0.5) parameter of the bernoulli’s law to be used in
conjunction with the |
init-population-size (optimizer only) |
integer |
[25-+oo] Defines the size of the population for the evolutionary algorithm. |
init-crossover-bastert-insertion (optimizer only) |
real |
[0-1] Probability to insert a bastert solution during the crossover operation. |
init-crossover-solution-selection-mean (optimizer only) |
real |
[0-1] Probability to select a solution to do the crossover operation. This parameter allows the selection of solution in the population. 0 means best solution, 1 means the worst in mean. |
init-crossover-solution-selection-stddev (optimizer only) |
real |
[0-1] Probability to select a solution to do the crossover operation. This parameter allows the selection of solution in the population. The standard deviation for the normal probability law. |
init-mutation-variable-mean (optimizer only) |
real |
[0-1] Probability to mutate the solution after the crossover operation. This parameter defines the number of variables to change. The mean for the normal probability law. |
init-mutation-variable-stddev (optimizer only) |
real |
[0-1] Probability to mutate the solution after the crossover operation. This parameter defines the number of variables to change. The standard deviation for the normal probability law. |
init-mutation-value-mean (optimizer only) |
real |
[0-1] Probability to mutate the solution after the crossover operation. This parameter defines the value of the variable. The mean for the normal probability law. |
init-mutation-value-stddev (optimizer only) |
real |
[0-1] Probability to mutate the solution after the crossover operation. This parameter defines the value of the variable. The standard deviation for the normal probability law. |
init-kappa-improve-start (optimizer only) |
real |
[0-1] The start value of kappa for the improve mode. |
init-kappa-improve-increase (optimizer only) |
real |
[0-1] The start value of kappa for the improve mode. |
init-kappa-improve-stop (optimizer only) |
real |
[init-kappa-improve-start - 1.0] The stop value of kappa for the improve mode. When the optimizer kappa exceeds this value, a new crossover and mutation will run. If |
For example:
baryonyx -p limit:1000000 lib/test/prevl1.lp baryonyx -p limit:-1 -p kappa-min:0.2 lib/test/prevl1.lp
Baryonyx permits to run benchmark on a set of problems described in a csv
files. This option is available using the --bench [name] option and csv
files. All Baryonyx parameters are available to perform the benchmark.
For example:
baryonyx --bench bx-0.5 -pdelta:0.01 -ptime-limit:60 spp.csv
The benchmark mode updates the csv file with results of computation. The
csv format is:
file optimum status cplex lsp bx-0.2 (1) cplex: lsp: (2) bx-0.2: scp410 optimum 514 514 514 804 (3) scp41 optimum 429 429 429 627 scp42 optimum 512 512 512 934
-
The header: three columns mandatory (
file,optimum,status) and one solver per column. In this example, cplex, local solver and baryonyx 0.2. -
The description part: one line per solver to describe version and parameter for example.
-
Finally, one line per solve: model name (with or without extension), status (optimum/feasible), best solution found and solver’s solution.
infcan be use to indicate no solution found.
In benchmark directory, some files are provided and a script to download classical problem.
To use rbaryonyx, you must compile and install the baryonyx library. Follow the previous section and install R.
The R rbaryonyx package requires several packages. Then, under a R terminal:
cd baryonyx/rbaryonyx
R CMD REMOVE rbaryonyx (1)
install.packages("roxygen2") (2)
install.packages("Rcpp")
install.packages("devtools")
library(Rcpp) (3)
compileAttributes(".")
library(devtools)
devtools::document()
devtools::build()
devtools::install()
library(rbaryonyx) (4)
?rbaryonyx (5)
-
Remove previous installed version of rbaryonyx
-
Install the dependencies of rbaryonyx
-
Build the rbaryonyx package
-
Load the package
-
The help
Two functions are provided to solve or optimize 01 linear programming
problem. Parameters are the same as C++ API. These function returns a
scalar:
-
If a solution is found:
-
if the problem is a minimization: the value of the solution found.
-
if the problem is a maximization: the inverse of the solution found.
-
-
If no solution is found, we use the limits of the objective function (minimal and maximal value possible.
-
if the problem is a minimization: the maximal value possible + the remaining constraints.
-
if the problem is a maximization: the inverse of the minimal value possible + the remaining constraints.
-
-
If a error occurred (not enough memory, problem error etc.):
-
if the problem is a minimization: the maximal value possible + the number of constraints .
-
if the problem is a maximization: the inverse of the minimal value possible + the number of constraints.
-
solve_01lp_problem <- function(file_path, limit = 1000L, theta = 0.5,
delta = 1e-4, constraint_order = 0L, kappa_min = 0.1, kappa_step = 1e-4,
kappa_max = 1.0, alpha = 1.0, w = 500L, time_limit = 10.0, seed = -1L,
thread = 1L, norm = 4L, pushing_k_factor = 0.9,
pushing_objective_amplifier = 5.0, pushes_limit = 10L,
pushing_iteration_limit = 20L, init_policy = 0L, init_random = 0.5,
float_type = 1L, verbose = TRUE)
optimize_01lp_problem <- function(file_path, limit = 1000L, theta = 0.5,
delta = 1e-4, constraint_order = 0L, kappa_min = 0.1, kappa_step = 1e-4,
kappa_max = 1.0, alpha = 1.0, w = 500L, time_limit = 10.0, seed = -1L,
thread = 1L, norm = 4L, pushing_k_factor = 0.9,
pushing_objective_amplifier = 5.0, pushes_limit = 10L,
pushing_iteration_limit = 20L, init_policy = 0L, init_random = 0.5,
float_type = 1L, verbose = TRUE)Apply morris method to found useful parameters:
library(rbaryonyx)
library(sensitivity)
factors = c("theta", "delta", "constraint_order", "kappa_min", "kappa_step",
"kappa_max", "alpha", "w", "norm", "pushing_k_factor",
"pushing_objective_amplifier", "pushes_limit", "pushing_iteration_limit",
"float_type")
bounds = data.frame(
min=c(
0, # theta
0, # delta
0, # constraint_order
0, # kappa_min
1e-16, # kappa_step
1.0, # kappa_max
0.0, # alpha
50, # w
0, # norm
0.1, # pushing_k_factor
1.0, # pushing_objective_amplifier
10, # pushes_limit
20, # pushing_iteration_limit
0, # init_policy
0.0, # init_random
0
), # float_type
max=c(
1, # theta
0, # delta
4, # constraint_order
0.1, # kappa_min
1e-1, # kappa_step
1.0, # kappa_max
2.0, # alpha
500, # w
4, # norm
1, # pushing_k_factor
10.0, # pushing_objective_amplifier
100, # pushes_limit
200, # pushing_iteration_limit
2, # init_policy
1.0, # init_random
2)) # float_type
rownames(bounds) <- factors
morrisDesign <- morris(model = NULL,
factors = factors,
r = 10,
design=list(type="oat", levels=10, grid.jump=5),
binf = bounds$min,
bsup = bounds$max,
scale=TRUE)
solve_lp <- function(x, file_path, limit=10000, time_limit=10, seed=123456789, thread=1) {
r <- rbaryonyx::solve_01lp_problem(file_path = file_path,
limit = limit,
theta = x["theta"],
delta = x["delta"],
constraint_order = x["constraint_order"],
kappa_min = x["kappa_min"],
kappa_step = x["kappa_step"],
kappa_max = x["kappa_max"],
alpha = x["alpha"],
w = x["w"],
time_limit = time_limit,
seed = seed,
thread = thread,
norm = x["norm"],
pushing_k_factor = x["pushing_k_factor"],
pushing_objective_amplifier = x["pushing_objective_amplifier,"],
pushes_limit = x["pushes_limit"],
pushing_iteration_limit = x["pushing_iteration_limit"],
init_policy = x["init_policy"],
init_random = x["init_random"],
float_type = x["float_type"])
return(r)
}
r = apply(morrisDesign$X, 1, solve_lp, file_path="verger_5_5.lp", thread=1, limit=10000, time_limit=10, seed=123456789)
morrisDesign$Y <- r
mu <- apply(morrisDesign$X,2,mean)
mu.star <- apply(morrisDesign$X, 2, function(x) mean(abs(x)))
sigma <- apply(morrisDesign$ee, 2, sd)
apply(morrisDesign$X, 2, function(v) plot(factor(v), r))Use RGenoud method to found best paramter values:
library(rgenoud)
library(rbaryonyx)
library(parallel)
optim_gen_lp <- function(x) {
r <- rbaryonyx::optimize_01lp_problem(
file_path = "rail507pre.lp",
limit = -1,
theta = x[1],
delta = x[2],
constraint_order = 0,
kappa_min = x[3],
kappa_step = x[4],
kappa_max = 1.0,
alpha = 1.0,
w = 60,
time_limit = 10,
seed = 123654785,
thread = 4,
norm = 0,
pushing_k_factor = 1,
pushing_objective_amplifier = 10,
pushes_limit = 20,
pushing_iteration_limit = 50,
init_policy = 0,
init_random = 0.5,
float_type = 1,
verbose = FALSE)
return(r)
}
d = matrix(c(0.0, 0.00001, 0.0, 1e-10,
1.0, 0.001, 0.2, 1e-4),
nrow=4, ncol=2)
s = c(0.5, 0.003226, 0.1, 1e-8)
no_cores <- detectCores() - 1
cl <- makeCluster(no_cores, outfile="debug.txt")
claw1 <- genoud(optim_gen_lp, nvars=4,
Domains=d,
starting.values=s,
cluster=cl,
boundary.enforcement=1,
max=FALSE, pop.size=10)To upgrade to the latest version of rbaryonyx, under bash (or equivalent):
cd baryonyx
git pull -r (1)
cd build
make -j4 (2)
make install
R CMD REMOVE rbaryonyx (3)
cd rbaryonyx
Rscript -e 'library(Rcpp); compileAttributes(".")'
Rscript -e 'library(devtools); devtools::document()'
cd ..
R CMD build rbaryonyx (4)
R CMD INSTALL rbaryonyx_1.0.tar.gz-
Update the baryonyx and rbaryonyx from Git
-
Build and install baryonyx
-
Remove old rbaryonyx package
-
Build and install