quesnel / baryonyx Goto Github PK
View Code? Open in Web Editor NEWbinary/integer linear programming solver
License: MIT License
binary/integer linear programming solver
License: MIT License
Remove constraints and affects variables:
x + y + z = 0
x + y + z = 3
x + y + z >= 3
x + y + z <= 0
Remove constraints:
x + y + z >= 0
x + y + z <= 3
The serialize option needs:
compute()
compute()
update_row()
As defined in LP format, acceptable sense indicators are <, <=, =<, >, >=, =>, and =. These are interpreted as ≤, ≤, ≤, ≥, ≥, ≥, and =, respectively.
Since all major compilers support C++17, Baryonyx will switch to the new standard:
For each solution found:
Instead of using variable index in console or dump, use the variables and constraints names.
The parser fails to read lp file if a variable exists in objective function and in bound but not in the binaries sections. Example:
Minimize
... + 123 t
s.t.
...
bound
t = 1
binaries
...
Testing a fresh build baryonyx uses too much time and memory:
/usr/bin/time baryonyx -O -p init-population-size=10 easy.lp
problem reads from file `easy.lp'
- output file: easy.lp-9319.sol
- objective: minimize
- mode: linear
- variables: 497/331/0 (real/general/binary)
- constraints: 434/21/0 (equal/greater/less)
- Preprocessing starts (size: 1.06 MB)
- Preprocessor finish. Removed variables 12 (size: 1.06 MB)
- Preprocessing finishes (size: 1.06 MB)
- optimize_inequalities_Z
Solver starts
...
- Constraints remaining: 124 (loop: 0 t: 0.0s reinit: 0)
- Constraints remaining: 124 (loop: 0 t: 0.0s reinit: 0)
^CCommand terminated by signal 2
42.71user 81.03system 0:22.64elapsed 546%CPU (0avgtext+0avgdata 14772872maxresident)k
19920inputs+80outputs (343506major+8946333minor)pagefaults 0swaps
The same with glpsol:
/usr/bin/time glpsol --lp easy.lp
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
--lp easy.lp
Reading problem data from 'easy.lp'...
455 rows, 827 columns, 1633 non-zeros
331 integer variables, all of which are binary
2237 lines were read
GLPK Integer Optimizer, v4.65
455 rows, 827 columns, 1633 non-zeros
331 integer variables, all of which are binary
Preprocessing...
10 constraint coefficient(s) were reduced
444 rows, 816 columns, 1622 non-zeros
320 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 3.100e+01 ratio = 3.100e+01
GM: min|aij| = 8.781e-01 max|aij| = 1.139e+00 ratio = 1.297e+00
EQ: min|aij| = 8.052e-01 max|aij| = 1.000e+00 ratio = 1.242e+00
2N: min|aij| = 5.000e-01 max|aij| = 1.000e+00 ratio = 2.000e+00
Constructing initial basis...
Size of triangular part is 444
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
444 rows, 816 columns, 1622 non-zeros
0: obj = 3.100000000e+02 inf = 6.200e+01 (3)
3: obj = 3.120000000e+02 inf = 0.000e+00 (0)
* 7: obj = 3.120000000e+02 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 7: mip = not found yet >= -inf (1; 0)
+ 50: >>>>> 3.120000000e+02 >= 3.120000000e+02 0.0% (3; 0)
+ 50: mip = 3.120000000e+02 >= tree is empty 0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 1.0 Mb (1085290 bytes)
0.01user 0.00system 0:00.02elapsed 70%CPU (0avgtext+0avgdata 4404maxresident)k
1984inputs+0outputs (10major+414minor)pagefaults 0swaps
Also there is a bug that prevents reading this "lp" file in parser.cpp with this possible fix:
raw_problem_status
parse([[maybe_unused]] const baryonyx::context& ctx,
stream_buffer& buf,
problem_parser& p) noexcept
{
...
if (auto elem =
read_function_element(buf.first(), buf.second(), buf.third());
elem) {
if (!p.append_to_objective(*elem))
return baryonyx::file_format_error_tag::too_many_variables;
if(elem->read) buf.pop_front(elem->read); //fix for elm->read == 0
else buf.pop_front();
continue;
}
...
And also another bug when trying to load an lp file without any other arguments:
cd lib/test
baryonyx general.lp
problem reads from file `general.lp'
- output file: general.lp-10013.sol
- objective: minimize
- mode: linear
- variables: 0/3/0 (real/general/binary)
- constraints: 2/0/0 (equal/greater/less)
- Preprocessing starts (size: 1.00 MB)
- Preprocessor finish. Removed variables 3 (size: 1.00 MB)
- Preprocessing finishes (size: 1.00 MB)
- solve_equalities_01
Solver starts
* Global parameters:
- limit: 1000
- time-limit: infs
- floating-point-type: double
- print-level: 0
- auto-tune: disabled
- observation: none
* In The Middle parameters:
- preprocessing: none
- constraint-order: none
- theta: 0.5
- delta: -1
- kappa: 0 0.001 0.6
- alpha: 1
- w: 50
- norm: loo
* Pushes system parameters:
- pushes-limit: 100
- pushing-objective-amplifier: 5
- pushing-iteration-limit: 50
- pushing-k-factor: 0.9
* Solver initialization parameters:
- init-policy: bastert
- init-policy-random: 0.5
* Optimizer initialization parameters:
- init-population-size: 100
- init-crossover-bastert-insertion: 0.01
- init-crossover-solution-selection-mean: 0.0
- init-crossover-solution-selection-stddev: 0.3
- init-mutation-variable-mean: 0.0001
- init-mutation-variable-stddev: 0.001
- init-mutation-value-mean: 0.5
- init-mutation-value-stddev: 0.2
- init-kappa-improve-start: 0.0
- init-kappa-improve-increase: 0.02
- init-kappa-improve-stop: 0.2
- merge constraint according to the `none` algorithm
- merged constraints removed: 0
- problem memory used: 1.00 MB
Solver finished
Segmentation fault (core dumped)
update the r[] vector instead of C
This function gives two problems (var at True or False)
To improve use in command line interface, graphical user interface or R, we replace, only for computation output (ex.: remaining constraint message, new solution found, etc.), the output message stream using private functions debug(ctx, ...), info(ctx, ...), warning(ctx, ...)
interface with callback mechanism in the baryonyx::context
class.
List of callback function can be:
using solver_started_callback std::function<void(baryonyx::context, baryonyx::parameter)>;
using solver_finished_callback std::function<void(baryonyx::context, baryonyx::result)>;
using solver_advance_callback std::function<void(baryonyx::context, baryonyx::result)>;
using solver_found_solution_callback std::function<void(baryonyx::context, baryonyx::result)>;
Use 0.01 by default
Negative means automatic parameter
Parse can not read lp file with subject to[:]
.
The int
or std::int32_t
type to reference array index, variable index seems to be sufficient for all source code.
Negative value means automatic
Positive value must define discrete optimization
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.