otspot-core 0.5.0

Core implementation for otspot (LP/QP/MIP solver) — published as a dependency of the otspot facade
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

use super::*;
use crate::options::{SimplexMethod, SolverOptions};
use crate::problem::{LpProblem, SolveStatus};
use crate::sparse::CscMatrix;
use crate::test_kkt::assert_solver_invariants_lp;

fn make_lp(
    c: Vec<f64>,
    rows: &[usize],
    cols: &[usize],
    vals: &[f64],
    nrows: usize,
    ncols: usize,
    b: Vec<f64>,
) -> LpProblem {
    let a = CscMatrix::from_triplets(rows, cols, vals, nrows, ncols).unwrap();
    LpProblem::new(c, a, b).unwrap()
}

/// LP1 (obj=-7) → reuse basis on LP2 with RHS=[5,3,3] (obj=-8).
#[test]
fn test_dual_advanced_warm_start_rhs_change() {
    let lp1 = make_lp(
        vec![-1.0, -2.0],
        &[0, 0, 1, 2],
        &[0, 1, 0, 1],
        &[1.0, 1.0, 1.0, 1.0],
        3,
        2,
        vec![4.0, 3.0, 3.0],
    );

    // LP1 を default solver で解いて warm_start_basis を取得
    let result1 = solve_with(&lp1, &SolverOptions::default());
    assert_eq!(result1.status, SolveStatus::Optimal);
    assert_solver_invariants_lp(&result1, &lp1);
    assert!(
        result1.warm_start_basis.is_some(),
        "LP1 は warm_start_basis を返すべき"
    );

    // LP2: RHS のみ変更 b=[5, 3, 3]
    let lp2 = make_lp(
        vec![-1.0, -2.0],
        &[0, 0, 1, 2],
        &[0, 1, 0, 1],
        &[1.0, 1.0, 1.0, 1.0],
        3,
        2,
        vec![5.0, 3.0, 3.0],
    );

    // cold-start で正解を確認
    let result2_cold = solve_with(&lp2, &SolverOptions::default());
    assert_eq!(result2_cold.status, SolveStatus::Optimal);
    assert_solver_invariants_lp(&result2_cold, &lp2);

    // DualAdvanced warm-start で解く → warm-start 経路を通す
    let opts_warm = SolverOptions {
        warm_start: result1.warm_start_basis.clone(),
        simplex_method: SimplexMethod::DualAdvanced,
        ..SolverOptions::default()
    };
    let result2_warm = solve_with(&lp2, &opts_warm);

    assert_eq!(
        result2_warm.status,
        SolveStatus::Optimal,
        "DualAdvanced warm-start は Optimal を返すべき"
    );
    assert_solver_invariants_lp(&result2_warm, &lp2);
    assert!(
        (result2_warm.objective - result2_cold.objective).abs() < 1e-6,
        "DualAdvanced warm-start obj={}, cold-start obj={}",
        result2_warm.objective,
        result2_cold.objective
    );
}

/// LP1 (obj=-4) → reuse basis on LP2 with RHS=[6,4,4] (obj=-8).
#[test]
fn test_dual_advanced_warm_start_larger_rhs() {
    let lp1 = make_lp(
        vec![-1.0, -1.0],
        &[0, 0, 1, 2],
        &[0, 1, 0, 1],
        &[1.0, 1.0, 1.0, 1.0],
        3,
        2,
        vec![4.0, 3.0, 3.0],
    );

    let result1 = solve_with(&lp1, &SolverOptions::default());
    assert_eq!(result1.status, SolveStatus::Optimal);
    assert_solver_invariants_lp(&result1, &lp1);
    assert!(
        result1.warm_start_basis.is_some(),
        "LP1 は warm_start_basis を返すべき"
    );

    // LP2: RHS 拡大 b=[6, 4, 4] → 最適解 x1+x2=8, obj=-8
    let lp2 = make_lp(
        vec![-1.0, -1.0],
        &[0, 0, 1, 2],
        &[0, 1, 0, 1],
        &[1.0, 1.0, 1.0, 1.0],
        3,
        2,
        vec![6.0, 4.0, 4.0],
    );

    // cold-start で正解を確認
    let result2_cold = solve_with(&lp2, &SolverOptions::default());
    assert_eq!(result2_cold.status, SolveStatus::Optimal);
    assert_solver_invariants_lp(&result2_cold, &lp2);

    // DualAdvanced warm-start で解く
    let opts_warm = SolverOptions {
        warm_start: result1.warm_start_basis.clone(),
        simplex_method: SimplexMethod::DualAdvanced,
        ..SolverOptions::default()
    };
    let result2_warm = solve_with(&lp2, &opts_warm);

    assert_eq!(
        result2_warm.status,
        SolveStatus::Optimal,
        "DualAdvanced warm-start (larger RHS) は Optimal を返すべき"
    );
    assert!(
        (result2_warm.objective - result2_cold.objective).abs() < 1e-6,
        "DualAdvanced warm-start obj={}, cold-start obj={}",
        result2_warm.objective,
        result2_cold.objective
    );
}