Baryonyx

Table of Contents

• Baryonyx
  • Requirements and recommended
  • First installation
  • Update installation
• Usage
  • Solver & Optimizer
  • Benchmark
• R
  • Installation
  • API
  • Usage
  • Upgrade

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.

Baryonyx

Requirements and recommended

• cmake (≥ 3.11)

• C++ compiler with C++17 support:

  • gcc ≥ 7 (notes)

  • clang ≥ 5 (notes)

  • visual studio 2019 16.0 (notes)

For recent Debian GNU/Linux and Ubuntu derivatives (remove clang to only use gcc):

apt-get install build-essential cmake clang

For Windows, install the CMake program and Visual Studio 2019 (MSVC). You may also install the vcpkg program to install nlopt and other dependencies.

• nlopt library - optimization library to automatic parametrization of the Baryonyx solver parameters.

First installation

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.

Table 1. Table CMake Command line parameters (cmake -DWITH_LOG=OFF …​)

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.

Update installation

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

Usage

Solver & Optimizer

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

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.

Table 2. Table Command line global parameters

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: none without specific algorithm. manual tries to update parameters to found best solution. nlopt tries to update parameters to found best solution using nlopt library and the Nelder Mead algorithm. branch split recursively original problem to found best solution. branch-manual mix branch and manual algorithm. branch-nlopt mix branch and nlopt algorithm.

To assign parameters to solver or optimizer algorithms, use the -p [name]:value syntax in the command line:

Table 3. Table Command line parameters

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 limit loop and if w is greater than 1, the number of loop without updating kappa
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 none let unmodified costs l1 use the l1-norm function l2 use the l2-norm function random try to avoid equal cost inf (default): use the infinity norm
constraint-order	string	Remaining constraints order. Values are: none (default): use the lp format constraint order reversing: reverse the lp format constraint order random-sorting: random the remaining constraint list infeasibility-decr: compute in-feasibility constraint in decremental order infeasibility-incr: compute in-feasibility constraint in incremental order lagrangian-decr: sort violated constraints according to the Lagrangian multiplier values in decremental order lagrangian-incr: sort violated constraints according to the Lagrangian multiplier values in incremental order pi-sign-change: random the remaining constraint list if the lagrangian multipliers signs have changed cycle: switch the constraint order after each update_row. Starts from none to pi-sign-change.
preprocessing	string	Constraints matrix A order. Values are: none: Use the raw_problem (or lp file) order for constraints and variables. memory: Default, use the raw_problem (or lp file) order for constraints but sort the variables to improve the memory cache efficiency. less_greater_equal: sort constraints according to their type (first less and finally greater then equal) and sort variable to improve the memory cache efficiency. less_equal_greater: sort constraints according to their type (first less and finally equal then greater) and sort variable to improve the memory cache efficiency. greater_less_equal: sort constraints according to their type (first greater then less and finally equal) and sort variable to improve the memory cache efficiency. greater_equal_less: sort constraints according to their type (first greater then equal and finally less) and sort variable to improve the memory cache efficiency. equal_less_greater: sort constraints according to their type (first equal then less and finally greater) and sort variable to improve the memory cache efficiency. equal_greater_less: sort constraints according to their type (first equal then greater and finally less) and sort variable to improve the memory cache efficiency. p1: reserved p2: reserved p3: reserved p4: reserved
observation	string	Select the type of observation mechanism (only in solve mode) none no observation (default). pnm produce picture files for the P matrix (one per loop) and Pi vector (Lagrangian multipliers) each loop file produce CSV files for the P matrix (one per loop) and Pi vector (Lagrangian multipliers) each loop
floating-point_type	string	Select the type of real use internally in the solvers. Values are: float float (32 bits) double double (64 bits) longdouble long double (84 or 128 bits)
print-level	integer	show information if greater than 0
storage-type	string	Change the solution storage policy for the optimizer mode. one (default): stores only the best solution found. bound: stores the best and the bad solution found. five: stores the best five solution found.
init-policy (solver only)	string	Change the initialization and reinitialization policy of the solution vector. Values are: bastert: for each variable (or at init-policy-random rate) use cost values to set or unset variable. pessimistic-solve: found a solution for each (or at init-policy-random rate) constraints. For soft constraints, affect one to strict minimum variables. optimistic-solve: found a solution for each (or or init-policy-random rate) constraints. For soft constraints, affect one to the maximum variables that valid the constraint.
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-policy parameter. If the law returns 1, it uses the init-policy algorithm to initialize X_i, 0 means use a toss up to choose 0 or 1 according to the init-random value.
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 init_kappa_improve_stop equals init-kappa-improve-start then improving is disabled.

For example:

baryonyx -p limit:1000000 lib/test/prevl1.lp
baryonyx -p limit:-1 -p kappa-min:0.2 lib/test/prevl1.lp

Benchmark

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

1. The header: three columns mandatory (file, optimum, status) and one solver per column. In this example, cplex, local solver and baryonyx 0.2.

2. The description part: one line per solver to describe version and parameter for example.

3. Finally, one line per solve: model name (with or without extension), status (optimum/feasible), best solution found and solver’s solution. inf can be use to indicate no solution found.

In benchmark directory, some files are provided and a script to download classical problem.

R

To use rbaryonyx, you must compile and install the baryonyx library. Follow the previous section and install R.

Installation

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)

1. Remove previous installed version of rbaryonyx

2. Install the dependencies of rbaryonyx

3. Build the rbaryonyx package

4. Load the package

5. The help

API

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)

Usage

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)

Upgrade

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

1. Update the baryonyx and rbaryonyx from Git

2. Build and install baryonyx

3. Remove old rbaryonyx package

4. Build and install