|
|
|
dylp is designed to be the
lp module in an lp-based branch-cut-price mixed-integer linear programming
code.
|
|
Very efficient when
reoptimising after small modifications to the problem. (The active system
changes slowly and remains minimal.)
|
|
The dynamic simplex
algorithm is also well suited for column generation algorithms.
|
|
|
|
dylp is designed as a
research code, and can provide copious trace output and extensive consistency
checks.
|
|
It's fast with an optimized
build, and downright paranoid when all consistency checks are enabled.
|
|
|
|
A design goal was that it
should never die before telling you exactly what went wrong, and where.
|
|
|
|
Native C implementation, C++
interface via COIN OSI layer.
|
|
Can be forced to use the
full constraint system and behave like a normal simplex algorithm.
|
|
|
|
The dynamic simplex
algorithm is laid out in Padberg, ``Linear Optimisation and Extensions''
(1991), and likely in lots of other places.
|
|
The basic idea is to always
work with a partial constraint system and dynamically adjust the active
system so that it contains only those
|
|
constraints and variables
that are needed for the current extreme point and immediate surroundings.
|
|
The core of the
implementation is two alternating cycles: purge/add variables and reoptimize
with primal simplex; purge/add
constraints and reoptimise with dual
simplex.
|
|
|
|
|
