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

//! # Representing linear programs for rapid read access
//!
//! The Simplex method algorithms work on a tableau. Because this tableau is very sparse in
//! practice, we store in a matrix that describes the current basis together with the original
//! (also sparse) matrix data. This module contains structures that can provide a matrix.
use crate::algorithm::two_phase::matrix_provider::column::Column;
use crate::data::linear_algebra::traits::{SparseComparator, SparseElement};
use crate::data::linear_algebra::vector::{DenseVector, SparseVector};
use crate::data::linear_program::elements::BoundDirection;

pub mod column;
pub mod matrix_data;
pub mod filter;
pub mod ops;
pub mod variable;

/// Abstract interface for a matrix and constraint vector.
///
/// This is the data of the "problem relative to the initial basis"; that is, nothing in
/// data structures implementing this trait determines a basis. The implementors of this trait
/// should be primarily read-only, with basis changes, the `Carry` fields of the `Tableau`
/// should change instead.
///
/// Note that a this trait doesn't have to be implemented by a (sparse) matrix data structure per
/// se; it could also be implemented by a graph, which lets itself be represented by data in a
/// matrix.
/// The indexing for the variables and constraints is as follows:
///
/// /                 || Vars of which we want a solution | Constraint slack vars | Bound slack vars |
/// ==================||==================================|=======================|==================|-----
/// Constraints       ||            constants             |       constants       |         0        || b |
/// ------------------||----------------------------------|-----------------------|------------------||---|
///                   ||                                  |                       | +/- 1            |
/// Bound constraints ||    constants (one 1 per row)     |           0           |       +/- 1      |
///                   ||                                  |                       |            +/- 1 |
/// --------------------------------------------------------------------------------------------------
pub trait MatrixProvider {
    /// Representation of a column of the matrix.
    ///
    /// TODO(ARCHITECTURE): When GATs are working, cloning can be avoided in some implementations,
    ///  such as the ones that explicitly store the column data, by giving this associated type a
    ///  lifetime parameter. Keep an eye on <https://github.com/rust-lang/rust/issues/44265>.
    type Column: Column;
    /// Cost row type.
    ///
    /// This type will often be of the form `Option<_>` so to not have to store any zero values, the
    /// inner type would never be zero in that case.
    type Cost<'a>;

    /// Right hand side type.
    type Rhs: ops::Rhs;

    /// Column of the problem.
    ///
    /// # Arguments
    ///
    /// * `j`: Column index.
    ///
    /// # Return value
    ///
    /// A sparse vector.
    fn column(&self, j: usize) -> Self::Column;

    /// Cost of a variable.
    ///
    /// # Arguments
    ///
    /// * `j`: Column index.
    ///
    /// # Return value
    ///
    /// Cost value.
    fn cost_value(&self, j: usize) -> Self::Cost<'_>;

    /// Constraint values.
    ///
    /// Note: constraint values of both the constraints and bounds. Lengths should be
    /// `self.nr_rows()`.
    ///
    /// TODO(OPTIMIZATION): Can this clone be avoided?
    ///
    /// # Return value
    ///
    /// A dense vector of constraint values, often called `b` in mathematical notation.
    fn right_hand_side(&self) -> DenseVector<Self::Rhs>;

    /// Index of the row of a virtual bound, if any.
    ///
    /// TODO(ARCHITECTURE): Currently, the return value is a row index. Make this relative to
    ///  `self.nr_constraints`?
    ///
    /// # Arguments
    ///
    /// * `j`: Variable index for the bound, if it exists.
    /// * `bound_type`: Whether it concerns a lower or upper bound.
    ///
    /// # Return value
    ///
    /// The index of the row in which the bound is virtually represented, if the bound exists.
    fn bound_row_index(&self, j: usize, bound_type: BoundDirection) -> Option<usize>;

    /// The number of constraints in the problem. This excludes simple variable bounds.
    fn nr_constraints(&self) -> usize;

    /// The number of simple variable bounds in the problem. This excludes more complicated
    /// constraints.
    fn nr_variable_bounds(&self) -> usize;

    /// The total number of rows in the provided virtual matrix.
    fn nr_rows(&self) -> usize {
        self.nr_constraints() + self.nr_variable_bounds()
    }

    /// The total number of columns in the provided virtual matrix. This does not include artificial
    /// variables; those are virtually represented by the `Artificial` `TableauType`.
    fn nr_columns(&self) -> usize;

    /// Reconstruct a solution.
    ///
    /// Not all variables that a provider presents to the solution algorithms might be relevant for
    /// the final solution. Free variables that are split, for example, could be recombined here.
    ///
    /// # Arguments
    ///
    /// * `column_values`: A solution for each of the variables that this provider presents.
    ///
    /// # Return value
    ///
    /// A solution that might be smaller than the number of variables in this problem.
    fn reconstruct_solution<G>(&self, column_values: SparseVector<G, G>) -> SparseVector<G, G>
    where
        G: SparseElement<G> + SparseComparator,
    ;
}