README- TSolution
- ::defaultSolveOptions::default
- ::newSolveOptions::new
- ::with_max_nodesSolveOptions::with_max_nodes
- TSolveStatus
- Vrelaxation
- Vsolve
- Vsolve_with
Freon793/moonopt/simplex does not have a README file
KernelProblem
pub struct KernelProblem {
nrows : Int
ncols : Int
structural : Int
matrix : SparseMatrix
rhs : Array[Double]
upper : Array[Double]
cost : Array[Double]
is_artificial : Array[Bool]
var_columns : Array[Array[(Int, Double)]]
var_offset : Array[Double]
objective_constant : Double
model_sign : Double
initial_basis : Array[Int]
row_source : Array[Int]
row_dual_factor : Array[Double]
row_sign : Array[Double]
row_relation : Array[Rel]
model_cost : Array[Double]
model_lower : Array[Double]
model_upper : Array[Double]
model_rhs : Array[Double]
} derive(Debug)The standard-form problem handed to the kernel.
KernelProblem::from_model
Builds the kernel problem for a model, applying the transformations listed in
the package comment. Returns the reason when the model uses something the
kernel deliberately does not accept (integer variables until the branch and
bound stage).
KernelProblem::from_standard
fn KernelProblem::from_standard(num_vars : Int, cost : Array[Double], rows : Array[(Array[Double], Rel, Double)]) -> KernelProblemBuilds the kernel problem for min cᵀx subject to rows and x ≥ 0.
This is the shape the reference solver in oracle accepts as well, which is
what makes differential testing between the two possible.
KernelProblem::slack_row_map
Column index of the slack (or surplus, for ≥ rows) of row i. Used by the
kernel to pick a starting basis.
KernelProblem::solution
Convenience view of the kernel solution for the first structural columns.
Pricing
Which rule picks the entering column.
Pricing decides the path a run takes, never its answer: the same model solved
under any of these rules has to reach the same optimum, and the tests assert it.
What changes is the cost per iteration and the number of pivots — which is
exactly why the default is the rule that measured best on the corpus rather than
the one that sounds most modern, and why the others stay reachable.
SimplexBasis
A basis, in the form a later run can start from.
basis[row] is the column that is basic in that row and at_upper[column] says
whether a non-basic column rests at its upper bound instead of at zero. The row and
column counts travel with it because a basis only means anything for the problem it
came from: a warm start whose shape does not match is refused and the run falls back
to a cold start, rather than pivoting on columns that are not there.
layout is the finer contract the counts cannot express: which columns the
indices refer to. The kernel's column set is decided per solve from the model's
bounds — a row's right hand side is the model's own minus Σ aⱼ·lⱼ, so tightening a
lower bound moves it, and a right hand side that crosses zero turns the row's
normalisation over (≤ with a negative side becomes ≥), which replaces its slack
with a surplus and an artificial and renumbers every extra column after it. Two such
layouts can agree on both counts, and the shape check alone would load a basis whose
indices now name different columns. Measured on MIPLIB's noswot, one 30 000-node
run handed 155 such bases to new_with_basis: every one of them contained two unit
columns of the same row — a basis that is exactly singular, which is what a column
set reinterpreted against a different numbering looks like. The fingerprint is taken
from everything that decides the layout (the starting column of each row, each
variable's column split, the rows' relations and normalisation signs) and a mismatch
refuses the warm start exactly as a shape mismatch does.
SimplexOptions
pub(all) struct SimplexOptions {
max_iterations : Int
refactorize_every : Int
feasibility_tolerance : Double
pivot_tolerance : Double
pivot_relative_tolerance : Double
start_with_bland : Bool
stall_window : Int
gain_candidates : Int
pricing : Pricing
degeneracy_perturbation : Double
max_factor_entries : Int
reduced_cost_tolerance : Double
relax_integrality : Bool
max_kernel_rows : Int
} derive(Debug)Tuning knobs for a kernel run.
The tolerances are the ones the algorithm actually consults, so they can be
tightened when hunting a numerical failure instead of guessing.
max_kernel_rows is a hard ceiling on the size the kernel will attempt. It
exists because the basis inverse used to be dense — m rows cost m² doubles,
and a bound expressed as a row could turn a model with a few hundred rows into a
kernel problem of tens of thousands of rows, where the allocation that follows is
not a slow solve but a dead process. A refused run is a fact the caller can act
on; a crash is not. Bounds are bounds now, so the ceiling mostly guards against
runs that cannot be honoured rather than against allocation.
SimplexOptions::default
Defaults: generous iteration budget, refactorization every 500 pivots (the
product-form updates are cheap, so the expensive rebuild can wait longer), and
tolerances in the range real LP codes use.
The row ceiling is a coarse guard, not the memory bound it once was: the basis
is factored sparsely now, so a run of tens of thousands of rows costs
O(nnz + fill) rather than m². max_factor_entries is what protects the
allocation, and time is what decides in practice.
SimplexOptions::limit_iterations
Options with an explicit iteration cap, keeping everything else.
with_max_iterations starts from the defaults, which is the wrong tool when a
caller has already chosen a relaxation: this one copies every field, so a
bounded run stays the run that was asked for.
SimplexOptions::relaxed
Options that treat integer variables as continuous: the LP relaxation.
SimplexOptions::with_gain_candidates
Options with an explicit gain-pricing budget. Used by the tests to pin that the
pricing rule is a control on the run: which column enters changes the path, and
the answer has to be the same whether the gain is measured or not.
SimplexOptions::with_max_iterations
Options with an explicit iteration cap, keeping the default tolerances.
SimplexOptions::with_max_kernel_rows
Options with an explicit kernel row ceiling. Used by the tests to reach the
TooLarge path with a model that is small enough to build instantly.
SimplexOptions::with_pricing
The same options with a different pricing rule, keeping every other field.
Used by the tests, and by callers who want to trade the per-iteration cost of a rule
against the number of pivots it needs: which column enters changes the path a run
takes, and the answer must not change with it.
SimplexOptions::with_stall_window
Options with an explicit stall window. Used by the tests to drive the Bland
fallback on a problem small enough to solve instantly: the window is a control
on the run, and the run's answer has to be the same whether the fallback fires
at the first stall or never.
SimplexResult
pub struct SimplexResult {
status : SimplexStatus
values : Array[Double]
objective : Double
iterations : Int
message : String
duals : Array[Double]
ray : Array[Double]
basis : SimplexBasis?
} derive(Debug)What a kernel run produced.
values is empty unless the status is Optimal or Unbounded (where it is the
feasible point a recession direction starts from); objective is in the caller's
own sense (a maximisation comes back as a maximised value) and is only meaningful
for Optimal.
duals and ray are the run's certificate — the numbers an independent
checker needs to confirm the verdict instead of taking its word for it:
- Optimal: values plus duals (row multipliers) is an optimality proof.
- Infeasible: duals is a Farkas ray, which proves no point can satisfy the rows — a measured residual says how infeasible the best attempt was, which is not the same statement.
- Unbounded: values is a feasible point and ray a direction that improves the objective forever from it.
Both arrays are in the convention verify documents, are stated against the
model the kernel was handed (not the kernel's internal normal form), and are
empty when the run has nothing to prove.
SimplexStatus
Outcome of a kernel run.
TableauRow
One tableau row, as the combination of model rows that produced it.
from_model_with
Same as from_model, with the option of treating integer variables as
continuous: the LP relaxation of a mixed integer model.
solve_model
Solves a model with default options.
Err carries the reason the model cannot be handed to the linear kernel
(integer variables, for now); a model that is merely hard comes back as a
result whose status says so.
solve_model_with
Same as solve_model with explicit options.
solve_model_with_basis
fn solve_model_with_basis(model : Model, options : SimplexOptions, basis : SimplexBasis) -> Result[SimplexResult, String]Solves a model starting from a basis a previous run left behind.
This is the reoptimization path a branch and bound tree needs. A bound change
leaves every reduced cost alone (they depend on the basis and the objective, not on
the bounds) and takes the basic values out of their bounds, so the previous optimal
basis is still dual feasible and no longer primal feasible — which is exactly the
state the dual simplex repairs. Rebuilding Phase I from scratch instead costs the
part of a solve that a bound change did not invalidate.
A warm start is only ever a speedup. The basis has to match this problem's shape and
has to be dual feasible, and whatever the dual simplex finishes with goes through the
same self-check as a cold run; anything short of that falls back to the cold path, so
the answer cannot depend on which path was taken.
solve_standard
fn solve_standard(num_vars : Int, cost : Array[Double], rows : Array[(Array[Double], Rel, Double)]) -> SimplexResultSolves min cᵀx subject to rows (a·x {≤, ≥, =} b) and x ≥ 0.
This is the same problem shape the reference solver in oracle accepts, so
the two can be compared directly.
solve_standard_with
fn solve_standard_with(num_vars : Int, cost : Array[Double], rows : Array[(Array[Double], Rel, Double)], options : SimplexOptions) -> SimplexResultSame as solve_standard with explicit options.
solve_standard_with_basis
fn solve_standard_with_basis(num_vars : Int, cost : Array[Double], rows : Array[(Array[Double], Rel, Double)], options : SimplexOptions, basis : SimplexBasis) -> SimplexResultSame as solve_standard_with, starting from a basis a previous run left behind.
tableau_rows
fn tableau_rows(model : Model, options : SimplexOptions, basis : SimplexBasis) -> Result[Array[TableauRow], String]The tableau rows of a solved problem, one per basic model variable.
The basis has to be one this problem's kernel version produced (SimplexResult::basis
is the intended source): the rows are read through the basis inverse, and a basis of
the wrong shape is refused rather than factored.
Install
Download zipOptimization kernels for MoonBit: MPS/LP model interop, a sparse revised simplex with presolve and a dual simplex warm start, branch and bound for models with integer variables, and independently checkable optimality, infeasibility and unboundedness certificates.
optimizationlinear-programmingmixed-integer-programmingsimplexmps
Apache-2.0
Updated 5 days ago
79 downloads