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

//! # The Simplex algorithm
//!
//! This module contains all data structures and logic specific to the simplex algorithm. The
//! algorithm is implemented as described in chapters 2 and 4 of Combinatorial Optimization, a book
//! by Christos H. Papadimitriou and Kenneth Steiglitz.
use crate::algorithm::{OptimizationResult, SolveRelaxation};
use crate::algorithm::two_phase::matrix_provider::column::{Column, ColumnNumber};
use crate::algorithm::two_phase::matrix_provider::column::identity::Identity;
use crate::algorithm::two_phase::matrix_provider::filter::generic_wrapper::{IntoFilteredColumn, RemoveRows};
use crate::algorithm::two_phase::matrix_provider::MatrixProvider;
use crate::algorithm::two_phase::phase_one::{FeasibilityComputeTrait, FullInitialBasis, Rank, RankedFeasibilityResult};
use crate::algorithm::two_phase::strategy::pivot_rule::SteepestDescentAlongObjective;
use crate::algorithm::two_phase::tableau::inverse_maintenance::{InverseMaintainer, ops as im_ops};
use crate::algorithm::two_phase::tableau::kind::artificial::Cost as ArtificialCost;
use crate::algorithm::two_phase::tableau::kind::non_artificial::NonArtificial;
use crate::algorithm::two_phase::tableau::Tableau;

pub mod phase_one;
pub mod phase_two;

pub mod tableau;
pub mod matrix_provider;
pub mod strategy;

impl<MP> SolveRelaxation for MP
where
    MP: MatrixProvider<Column: Identity + IntoFilteredColumn>,
{
    // TODO(ENHANCEMENT): Specialize for MatrixProviders that can be filtered directly.
    default fn solve_relaxation<'provider, IM>(&'provider self) -> OptimizationResult<IM::F>
    where
        IM: InverseMaintainer<F:
            im_ops::FieldHR +
            im_ops::Column<<<Self as MatrixProvider>::Column as Column>::F> +
            im_ops::Cost<ArtificialCost> +
            im_ops::Cost<MP::Cost<'provider>> +
            im_ops::Rhs<MP::Rhs> +
        >,
    {
        match self.compute_bfs_giving_im::<IM>() {
            RankedFeasibilityResult::Feasible {
                rank,
                nr_artificial_variables,
                basis,
                inverse_maintainer,
            } => match rank {
                Rank::Deficient(rows_to_remove) if !rows_to_remove.is_empty() => {
                    let rows_removed = RemoveRows::new(self, rows_to_remove);
                    let mut non_artificial = Tableau::<_, NonArtificial<_>>::from_artificial_removing_rows(
                        inverse_maintainer,
                        nr_artificial_variables,
                        basis,
                        &rows_removed,
                    );
                    // TODO(ENHANCEMENT): Consider implementing a heuristic to decide these
                    //  strategies dynamically
                    phase_two::primal::<_, _, SteepestDescentAlongObjective<_>>(&mut non_artificial)
                },
                _ => {
                    let mut non_artificial_tableau = Tableau::<_, NonArtificial<_>>::from_artificial(
                        inverse_maintainer,
                        nr_artificial_variables,
                        basis,
                        self,
                    );
                    // TODO(ENHANCEMENT): Consider implementing a heuristic to decide these
                    //  strategies dynamically
                    phase_two::primal::<_, _, SteepestDescentAlongObjective<_>>(&mut non_artificial_tableau)
                },
            },
            RankedFeasibilityResult::Infeasible => OptimizationResult::Infeasible,
        }
    }
}

/// Skipping the entire first phase because a basic feasible solution could be cheaply provided.
///
/// TODO(ARCHITECTURE): If this is true, it's ot really two-phase, now is it? Should this solution
///  be provided elsewhere, or the module be renamed?
impl<MP: FullInitialBasis> SolveRelaxation for MP
where
    // TODO(ARCHITECTURE): The <MP as MatrixProvider>::Column: IdentityColumn bound is needed
    //  because of limitations of the specialization feature; overlap is not (yet) allowed.
    MP: MatrixProvider<Column: Identity + IntoFilteredColumn>,
    MP::Rhs: 'static + ColumnNumber,
{
    fn solve_relaxation<'provider, IM>(&'provider self) -> OptimizationResult<IM::F>
    where
        IM: InverseMaintainer<F:
            im_ops::FieldHR +
            im_ops::Column<<<Self as MatrixProvider>::Column as Column>::F> +
            im_ops::Cost<MP::Cost<'provider>> +
            im_ops::Rhs<Self::Rhs> +
            im_ops::Column<Self::Rhs> +
        >,
    {
        let basis_indices = self.pivot_element_indices();
        // Sorting of identity matrix columns
        let inverse_maintainer = IM::from_basis_pivots(&basis_indices, self);

        let basis_indices = basis_indices.into_iter().map(|(_row, column)| column).collect();
        let mut tableau = Tableau::<_, NonArtificial<_>>::new_with_inverse_maintainer(
            self, inverse_maintainer, basis_indices,
        );
        // TODO(ENHANCEMENT): Consider implementing a heuristic to decide these strategies
        //  dynamically
        phase_two::primal::<_, _, SteepestDescentAlongObjective<_>>(&mut tableau)
    }
}

#[cfg(test)]
mod test;