Skip to content
master
Go to file
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
app
 
 
 
 
 
 
 
 
lib
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README.adoc

Baryonyx

Baryonyx is an integer and binary linear programming solver based on the Dag Wedelin heuristic.

Build Status

Build Status

Coverage Status

Copyright © 2017-2020 INRA

The software is released under the MIT license. See the LICENSE file.

Baryonyx

  • 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 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

About

binary/integer linear programming solver

Topics

Resources

License

Packages

No packages published

Languages

You can’t perform that action at this time.