relp 0.2.6

Rust Exact Linear Programming
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

//! # Artificial variables in the tableau
//!
//! Representing artificial variables in the tableau "virtually". That is, the values aren't
//! actually stored but instead logic provides the algorithm with the input it needs to drive the
//! artificial variables out of the basis.
use std::collections::HashSet;

use relp_num::Binary;

use crate::algorithm::two_phase::matrix_provider::column::Column;
use crate::algorithm::two_phase::matrix_provider::column::identity::Identity;
use crate::algorithm::two_phase::tableau::inverse_maintenance::{InverseMaintainer, ops as im_ops};
use crate::algorithm::two_phase::tableau::kind::Kind;
use crate::algorithm::two_phase::tableau::Tableau;

pub mod fully;
pub mod partially;

/// Artificial cost elements.
///
/// When artificial variables are in the basis, we minimize a simple sum. That is, all artificial
/// variables have cost `One`. Variables in the artificial tableau that are not artificial (and
/// should not be minimized out of the basis) have artificial cost `Zero` (although they might have
/// a non-artificial cost).
///
/// Artificial cost of the non-artificial variables is zero, artificial cost of the artificial
/// variables is one.
pub type Cost = Binary;

/// Tableaus with artificial variables.
///
/// There are currently two implementations; either all variables are artificial, or not necessarily
/// all variables are. See the two submodules.
pub trait Artificial: Kind<Column: Identity, Cost=Cost> {
    /// How many artificial variables are in the tableau.
    ///
    /// This number varies, because slack variables might have been recognized as practical
    /// candidates for basic feasible solutions by the `MatrixProvider` (the
    /// `positive_slack_indices` method).
    ///
    /// # Return value
    ///
    /// This number can be zero (for non artificial tableaus, represented by the `NonArtificial`
    /// struct), or any number through the number of rows (`self.nr_rows`).
    fn nr_artificial_variables(&self) -> usize;

    /// At which row is the pivot from a specific artificial variable located?
    ///
    /// # Arguments
    ///
    /// * `artificial_index`: Index of artificial variable.
    ///
    /// # Returns
    ///
    /// Row index where the pivot is located.
    fn pivot_row_from_artificial(&self, artificial_index: usize) -> usize;
}

/// Functionality needed only, and for all, artificial tableaus.
///
/// Most of these functions get called in the artificial simplex method, or the method that removes
/// artificial variables from the problem at zero level.
impl<'provider, IM, A> Tableau<IM, A>
where
    IM: InverseMaintainer<F: im_ops::Column<<A::Column as Column>::F> + im_ops::Cost<A::Cost>>,
    A: Artificial,
{
    /// Whether there are any artificial variables in the basis.
    pub fn has_artificial_in_basis(&self) -> bool {
        self.basis_columns.iter().any(|&c| c < self.nr_artificial_variables())
    }

    /// Get the indices of the artificial variables that are still in the basis.
    pub fn artificial_basis_columns(&self) -> Vec<(usize, usize)> {
        (0..self.nr_rows())
            .map(|i| (i, self.inverse_maintainer.basis_column_index_for_row(i)))
            .filter(|&(_, j)| j < self.nr_artificial_variables())
            .collect()
    }

    /// At which row is the pivot from a specific artificial variable located?
    ///
    /// # Arguments
    ///
    /// * `artificial_index`: Index of artificial variable.
    ///
    /// # Returns
    ///
    /// Row index where the pivot is located.
    pub fn pivot_row_from_artificial(&self, artificial_index: usize) -> usize {
        debug_assert!(artificial_index < self.nr_artificial_variables());
        // Only used to remove variables from basis
        debug_assert!(self.is_in_basis(artificial_index));

        self.kind.pivot_row_from_artificial(artificial_index)
    }

    /// Extract information necessary to construct a `NonArtificial` tableau.
    ///
    /// # Returns
    ///
    /// The inverse maintainer (typically contains the inverse of a basis, expensive to redo), the
    /// number of artificial variables that were in the basis (all assumed to have been located at
    /// the lowest indices), and a tuple of which the first element maps rows of the problem (before
    /// any rows were removed, if necessary) to the columns holding the pivots from the current
    /// basis, as well as a set copy of those columns.
    pub fn into_basis(self) -> (IM, usize, HashSet<usize>) {
        let nr_artificial = self.nr_artificial_variables();
        (self.inverse_maintainer, nr_artificial, self.basis_columns)
    }
}

impl<'provider, IM, A> Tableau<IM, A>
where
    A: Artificial,
{
    /// Number of artificial variables in this tableau.
    pub fn nr_artificial_variables(&self) -> usize {
        self.kind.nr_artificial_variables()
    }
}