relp/algorithm/two_phase/
phase_two.rs

1//! # Phase two: improving a basic feasible solution
2use crate::algorithm::OptimizationResult;
3use crate::algorithm::two_phase::matrix_provider::column::Column;
4use crate::algorithm::two_phase::matrix_provider::MatrixProvider;
5use crate::algorithm::two_phase::strategy::pivot_rule::PivotRule;
6use crate::algorithm::two_phase::tableau::{debug_assert_in_basic_feasible_solution_state, Tableau};
7use crate::algorithm::two_phase::tableau::inverse_maintenance::{ColumnComputationInfo, InverseMaintainer, ops as im_ops};
8use crate::algorithm::two_phase::tableau::kind::non_artificial::NonArtificial;
9
10/// Reduces the cost of the basic feasible solution to the minimum.
11///
12/// While calling this method, a number of requirements should be satisfied:
13/// - There should be a valid basis (not necessarily optimal <=> dual feasible <=> c >= 0)
14/// - All constraint values need to be positive (primary feasibility)
15///
16/// TODO(CORRECTNESS): Write debug tests for these requirements
17///
18/// # Return value
19///
20/// An `OptimizationResult` indicating whether or not the problem has a finite optimum. It cannot be
21/// infeasible, as a feasible solution is needed to start using this method.
22pub fn primal<'provider, IM, MP, PR>(
23    tableau: &mut Tableau<IM, NonArtificial<'provider, MP>>,
24) -> OptimizationResult<IM::F>
25where
26    IM: InverseMaintainer<F:
27        im_ops::FieldHR +
28        im_ops::Column<<MP::Column as Column>::F> +
29        im_ops::Cost<MP::Cost<'provider>> +
30    >,
31    MP: MatrixProvider,
32    PR: PivotRule<IM::F>,
33{
34    let mut rule = PR::new(tableau);
35
36    loop {
37        debug_assert!({
38            debug_assert_in_basic_feasible_solution_state(&tableau);
39            true
40        });
41
42        match rule.select_primal_pivot_column(tableau) {
43            Some((pivot_column_index, cost)) => {
44                let column_with_info = tableau.generate_column(pivot_column_index);
45                match tableau.select_primal_pivot_row(column_with_info.column()) {
46                    Some(pivot_row_index) => {
47                        let basis_change_computation_info = tableau.bring_into_basis(
48                            pivot_column_index, pivot_row_index,
49                            column_with_info, cost,
50                        );
51                        rule.after_basis_update(basis_change_computation_info,&tableau);
52                    }
53                    None => break OptimizationResult::Unbounded,
54                }
55            }
56            None => break OptimizationResult::FiniteOptimum(tableau.current_bfs()),
57        }
58    }
59}
relp/algorithm/two_phase/phase_two.rs

relp/algorithm/two_phase/
phase_two.rs
