relp 0.2.1

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

//! # Basis initially completely from artificial variables
//!
//! When no initial pivots can be derived, this module is used. It is slightly quicker than the
//! partially artificial tableau kind.
use crate::algorithm::two_phase::matrix_provider::column::Column;
use crate::algorithm::two_phase::matrix_provider::column::identity::Identity;
use crate::algorithm::two_phase::matrix_provider::MatrixProvider;
use crate::algorithm::two_phase::tableau::inverse_maintenance::{InverseMaintener, ops as im_ops};
use crate::algorithm::two_phase::tableau::kind::artificial::{Artificial, Cost};
use crate::algorithm::two_phase::tableau::kind::Kind;
use crate::algorithm::two_phase::tableau::Tableau;

/// All variables are artificial.
pub struct Fully<'a, MP: MatrixProvider> {
    /// Supplies data about the problem.
    ///
    /// This data doesn't change throughout the lifetime of this `Tableau`, and it is independent of
    /// the current basis as described by the `carry` and `basis_columns` attributes.
    provider: &'a MP,
}

impl<'provider, MP> Kind for Fully<'provider, MP>
where
    MP: MatrixProvider<Column: Column + Identity>,
{
    type Column = MP::Column;
    type Cost = Cost;

    fn initial_cost_value(&self, j: usize) -> Self::Cost {
        if j < self.nr_artificial_variables() {
            Cost::One
        } else {
            Cost::Zero
        }
    }

    fn original_column(&self, j: usize) -> Self::Column {
        if j < self.nr_rows() {
            // TODO(ENHANCEMENT): Would it be possible to specialize the code where this identity
            //  column is used?
            <Self::Column as Identity>::identity(j, self.nr_rows())
        } else {
            self.provider.column(j - self.nr_rows())
        }
    }

    fn nr_rows(&self) -> usize {
        self.provider.nr_rows()
    }

    fn nr_columns(&self) -> usize {
        self.nr_rows() + self.provider.nr_columns()
    }
}

impl<'provider, MP> Artificial for Fully<'provider, MP>
where
    MP: MatrixProvider<Column: Identity>,
{
    fn nr_artificial_variables(&self) -> usize {
        self.nr_rows()
    }

    fn pivot_row_from_artificial(&self, artificial_index: usize) -> usize {
        debug_assert!(artificial_index < self.nr_artificial_variables());

        artificial_index
    }
}

impl<'provider, IM, MP> Tableau<IM, Fully<'provider, MP>>
where
    IM: InverseMaintener<F: im_ops::Rhs<MP::Rhs>>,
    MP: MatrixProvider,
{
    /// Create a `Tableau` augmented with artificial variables.
    ///
    /// The tableau is then in a basic feasible solution having only the artificial variables in the
    /// basis.
    ///
    /// # Arguments
    ///
    /// * `provider`: Provides the problem to find a basic feasible solution for.
    ///
    /// # Return value
    ///
    /// The tableau.
    pub(crate) fn new(provider: &'provider MP) -> Self {
        let m = provider.nr_rows();

        Tableau {
            inverse_maintainer: IM::create_for_fully_artificial(provider.right_hand_side()),
            basis_columns: (0..m).collect(),

            kind: Fully { provider },
        }
    }
}