otspot-core 0.3.1

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

//! QP presolve step 7: free-variable substitution via singleton Eq rows.

use super::helpers::{apply_fixed_variable, skip_step};
use super::state::{QpPostsolveStep, QpPresolveResult, Workspace};
use crate::qp::QpProblem;
use crate::tolerances::ZERO_TOL;

/// Step 7: free-variable substitution via Eq rows (restricted to Q-zero columns so we
/// don't have to update Q with a rank-1 term).
/// O(n*m) inner scan — caller must respect the deadline.
pub(super) fn step7_free_var(
    prob: &QpProblem,
    ws: &mut Workspace,
    deadline: Option<std::time::Instant>,
) -> Result<(), QpPresolveResult> {
    if skip_step(7) {
        return Ok(());
    }
    let n = prob.num_vars;
    let m = prob.num_constraints;
    for j in 0..n {
        if deadline.is_some_and(|d| std::time::Instant::now() >= d) {
            return Ok(());
        }
        if ws.removed_cols[j] {
            continue;
        }
        let (lb, ub) = ws.bounds[j];
        if lb != f64::NEG_INFINITY || ub != f64::INFINITY {
            continue;
        }

        let q_nnz_j = {
            let start = prob.q.col_ptr[j];
            let end = prob.q.col_ptr[j + 1];
            (start..end).filter(|&k| prob.q.values[k].abs() > ZERO_TOL).count()
        };
        if q_nnz_j > 0 {
            continue;
        }

        // Only Eq singleton rows are eligible.
        let singleton_eq_rows: Vec<usize> = (0..m)
            .filter(|&i| {
                if ws.removed_rows[i] {
                    return false;
                }
                if prob.constraint_types[i] != crate::problem::ConstraintType::Eq {
                    return false;
                }
                let active: Vec<_> = ws.row_entries[i]
                    .iter()
                    .filter(|&&(jj, v)| !ws.removed_cols[jj] && v.abs() > ZERO_TOL)
                    .collect();
                active.len() == 1 && active[0].0 == j
            })
            .collect();

        if singleton_eq_rows.is_empty() {
            continue;
        }

        let i = singleton_eq_rows[0];
        let a_ij = ws.row_entries[i]
            .iter()
            .find(|&&(jj, _)| jj == j)
            .map(|&(_, v)| v)
            .unwrap_or(0.0);
        if a_ij.abs() < ZERO_TOL {
            continue;
        }
        let val = ws.b[i] / a_ij;

        apply_fixed_variable(j, val, prob, ws);
        ws.removed_cols[j] = true;
        ws.removed_rows[i] = true;
        ws.postsolve_stack.push(QpPostsolveStep::SingletonRow { row: i, col: j, val });
    }
    Ok(())
}