| use { | |
| Symbol, | |
| SymbolType, | |
| Constraint, | |
| Variable, | |
| Expression, | |
| Term, | |
| Row, | |
| AddConstraintError, | |
| RemoveConstraintError, | |
| InternalSolverError, | |
| SuggestValueError, | |
| AddEditVariableError, | |
| RemoveEditVariableError, | |
| RelationalOperator, | |
| near_zero | |
| }; | |
| use ::std::rc::Rc; | |
| use ::std::cell::RefCell; | |
| use ::std::collections::{ HashMap, HashSet }; | |
| use ::std::collections::hash_map::Entry; | |
| #[derive(Copy, Clone)] | |
| struct Tag { | |
| marker: Symbol, | |
| other: Symbol | |
| } | |
| #[derive(Clone)] | |
| struct EditInfo { | |
| tag: Tag, | |
| constraint: Constraint, | |
| constant: f64 | |
| } | |
| /// A constraint solver using the Cassowary algorithm. For proper usage please see the top level crate documentation. | |
| pub struct Solver { | |
| cns: HashMap<Constraint, Tag>, | |
| var_data: HashMap<Variable, (f64, Symbol, usize)>, | |
| var_for_symbol: HashMap<Symbol, Variable>, | |
| public_changes: Vec<(Variable, f64)>, | |
| changed: HashSet<Variable>, | |
| should_clear_changes: bool, | |
| rows: HashMap<Symbol, Box<Row>>, | |
| edits: HashMap<Variable, EditInfo>, | |
| infeasible_rows: Vec<Symbol>, // never contains external symbols | |
| objective: Rc<RefCell<Row>>, | |
| artificial: Option<Rc<RefCell<Row>>>, | |
| id_tick: usize | |
| } | |
| impl Solver { | |
| /// Construct a new solver. | |
| pub fn new() -> Solver { | |
| Solver { | |
| cns: HashMap::new(), | |
| var_data: HashMap::new(), | |
| var_for_symbol: HashMap::new(), | |
| public_changes: Vec::new(), | |
| changed: HashSet::new(), | |
| should_clear_changes: false, | |
| rows: HashMap::new(), | |
| edits: HashMap::new(), | |
| infeasible_rows: Vec::new(), | |
| objective: Rc::new(RefCell::new(Row::new(0.0))), | |
| artificial: None, | |
| id_tick: 1 | |
| } | |
| } | |
| pub fn add_constraints<'a, I: IntoIterator<Item = &'a Constraint>>( | |
| &mut self, | |
| constraints: I) -> Result<(), AddConstraintError> | |
| { | |
| for constraint in constraints { | |
| try!(self.add_constraint(constraint.clone())); | |
| } | |
| Ok(()) | |
| } | |
| /// Add a constraint to the solver. | |
| pub fn add_constraint(&mut self, constraint: Constraint) -> Result<(), AddConstraintError> { | |
| if self.cns.contains_key(&constraint) { | |
| return Err(AddConstraintError::DuplicateConstraint); | |
| } | |
| // Creating a row causes symbols to reserved for the variables | |
| // in the constraint. If this method exits with an exception, | |
| // then its possible those variables will linger in the var map. | |
| // Since its likely that those variables will be used in other | |
| // constraints and since exceptional conditions are uncommon, | |
| // i'm not too worried about aggressive cleanup of the var map. | |
| let (mut row, tag) = self.create_row(&constraint); | |
| let mut subject = Solver::choose_subject(&row, &tag); | |
| // If chooseSubject could find a valid entering symbol, one | |
| // last option is available if the entire row is composed of | |
| // dummy variables. If the constant of the row is zero, then | |
| // this represents redundant constraints and the new dummy | |
| // marker can enter the basis. If the constant is non-zero, | |
| // then it represents an unsatisfiable constraint. | |
| if subject.type_() == SymbolType::Invalid && Solver::all_dummies(&row) { | |
| if !near_zero(row.constant) { | |
| return Err(AddConstraintError::UnsatisfiableConstraint); | |
| } else { | |
| subject = tag.marker; | |
| } | |
| } | |
| // If an entering symbol still isn't found, then the row must | |
| // be added using an artificial variable. If that fails, then | |
| // the row represents an unsatisfiable constraint. | |
| if subject.type_() == SymbolType::Invalid { | |
| if !try!(self.add_with_artificial_variable(&row) | |
| .map_err(|e| AddConstraintError::InternalSolverError(e.0))) { | |
| return Err(AddConstraintError::UnsatisfiableConstraint); | |
| } | |
| } else { | |
| row.solve_for_symbol(subject); | |
| self.substitute(subject, &row); | |
| if subject.type_() == SymbolType::External && row.constant != 0.0 { | |
| let v = self.var_for_symbol[&subject]; | |
| self.var_changed(v); | |
| } | |
| self.rows.insert(subject, row); | |
| } | |
| self.cns.insert(constraint, tag); | |
| // Optimizing after each constraint is added performs less | |
| // aggregate work due to a smaller average system size. It | |
| // also ensures the solver remains in a consistent state. | |
| let objective = self.objective.clone(); | |
| try!(self.optimise(&objective).map_err(|e| AddConstraintError::InternalSolverError(e.0))); | |
| Ok(()) | |
| } | |
| /// Remove a constraint from the solver. | |
| pub fn remove_constraint(&mut self, constraint: &Constraint) -> Result<(), RemoveConstraintError> { | |
| let tag = try!(self.cns.remove(constraint).ok_or(RemoveConstraintError::UnknownConstraint)); | |
| // Remove the error effects from the objective function | |
| // *before* pivoting, or substitutions into the objective | |
| // will lead to incorrect solver results. | |
| self.remove_constraint_effects(constraint, &tag); | |
| // If the marker is basic, simply drop the row. Otherwise, | |
| // pivot the marker into the basis and then drop the row. | |
| if let None = self.rows.remove(&tag.marker) { | |
| let (leaving, mut row) = try!(self.get_marker_leaving_row(tag.marker) | |
| .ok_or( | |
| RemoveConstraintError::InternalSolverError( | |
| "Failed to find leaving row."))); | |
| row.solve_for_symbols(leaving, tag.marker); | |
| self.substitute(tag.marker, &row); | |
| } | |
| // Optimizing after each constraint is removed ensures that the | |
| // solver remains consistent. It makes the solver api easier to | |
| // use at a small tradeoff for speed. | |
| let objective = self.objective.clone(); | |
| try!(self.optimise(&objective).map_err(|e| RemoveConstraintError::InternalSolverError(e.0))); | |
| // Check for and decrease the reference count for variables referenced by the constraint | |
| // If the reference count is zero remove the variable from the variable map | |
| for term in &constraint.expr().terms { | |
| if !near_zero(term.coefficient) { | |
| let mut should_remove = false; | |
| if let Some(&mut (_, _, ref mut count)) = self.var_data.get_mut(&term.variable) { | |
| *count -= 1; | |
| should_remove = *count == 0; | |
| } | |
| if should_remove { | |
| self.var_for_symbol.remove(&self.var_data[&term.variable].1); | |
| self.var_data.remove(&term.variable); | |
| } | |
| } | |
| } | |
| Ok(()) | |
| } | |
| /// Test whether a constraint has been added to the solver. | |
| pub fn has_constraint(&self, constraint: &Constraint) -> bool { | |
| self.cns.contains_key(constraint) | |
| } | |
| /// Add an edit variable to the solver. | |
| /// | |
| /// This method should be called before the `suggest_value` method is | |
| /// used to supply a suggested value for the given edit variable. | |
| pub fn add_edit_variable(&mut self, v: Variable, strength: f64) -> Result<(), AddEditVariableError> { | |
| if self.edits.contains_key(&v) { | |
| return Err(AddEditVariableError::DuplicateEditVariable); | |
| } | |
| let strength = ::strength::clip(strength); | |
| if strength == ::strength::REQUIRED { | |
| return Err(AddEditVariableError::BadRequiredStrength); | |
| } | |
| let cn = Constraint::new(Expression::from_term(Term::new(v.clone(), 1.0)), | |
| RelationalOperator::Equal, | |
| strength); | |
| self.add_constraint(cn.clone()).unwrap(); | |
| self.edits.insert(v.clone(), EditInfo { | |
| tag: self.cns[&cn].clone(), | |
| constraint: cn, | |
| constant: 0.0 | |
| }); | |
| Ok(()) | |
| } | |
| /// Remove an edit variable from the solver. | |
| pub fn remove_edit_variable(&mut self, v: Variable) -> Result<(), RemoveEditVariableError> { | |
| if let Some(constraint) = self.edits.remove(&v).map(|e| e.constraint) { | |
| try!(self.remove_constraint(&constraint) | |
| .map_err(|e| match e { | |
| RemoveConstraintError::UnknownConstraint => | |
| RemoveEditVariableError::InternalSolverError("Edit constraint not in system"), | |
| RemoveConstraintError::InternalSolverError(s) => | |
| RemoveEditVariableError::InternalSolverError(s) | |
| })); | |
| Ok(()) | |
| } else { | |
| Err(RemoveEditVariableError::UnknownEditVariable) | |
| } | |
| } | |
| /// Test whether an edit variable has been added to the solver. | |
| pub fn has_edit_variable(&self, v: &Variable) -> bool { | |
| self.edits.contains_key(v) | |
| } | |
| /// Suggest a value for the given edit variable. | |
| /// | |
| /// This method should be used after an edit variable has been added to | |
| /// the solver in order to suggest the value for that variable. | |
| pub fn suggest_value(&mut self, variable: Variable, value: f64) -> Result<(), SuggestValueError> { | |
| let (info_tag_marker, info_tag_other, delta) = { | |
| let info = try!(self.edits.get_mut(&variable).ok_or(SuggestValueError::UnknownEditVariable)); | |
| let delta = value - info.constant; | |
| info.constant = value; | |
| (info.tag.marker, info.tag.other, delta) | |
| }; | |
| // tag.marker and tag.other are never external symbols | |
| // The nice version of the following code runs into non-lexical borrow issues. | |
| // Ideally the `if row...` code would be in the body of the if. Pretend that it is. | |
| { | |
| let infeasible_rows = &mut self.infeasible_rows; | |
| if self.rows.get_mut(&info_tag_marker) | |
| .map(|row| | |
| if row.add(-delta) < 0.0 { | |
| infeasible_rows.push(info_tag_marker); | |
| }).is_some() | |
| { | |
| } else if self.rows.get_mut(&info_tag_other) | |
| .map(|row| | |
| if row.add(delta) < 0.0 { | |
| infeasible_rows.push(info_tag_other); | |
| }).is_some() | |
| { | |
| } else { | |
| for (symbol, row) in &mut self.rows { | |
| let coeff = row.coefficient_for(info_tag_marker); | |
| let diff = delta * coeff; | |
| if diff != 0.0 && symbol.type_() == SymbolType::External { | |
| let v = self.var_for_symbol[symbol]; | |
| // inline var_changed - borrow checker workaround | |
| if self.should_clear_changes { | |
| self.changed.clear(); | |
| self.should_clear_changes = false; | |
| } | |
| self.changed.insert(v); | |
| } | |
| if coeff != 0.0 && | |
| row.add(diff) < 0.0 && | |
| symbol.type_() != SymbolType::External | |
| { | |
| infeasible_rows.push(*symbol); | |
| } | |
| } | |
| } | |
| } | |
| try!(self.dual_optimise().map_err(|e| SuggestValueError::InternalSolverError(e.0))); | |
| return Ok(()); | |
| } | |
| fn var_changed(&mut self, v: Variable) { | |
| if self.should_clear_changes { | |
| self.changed.clear(); | |
| self.should_clear_changes = false; | |
| } | |
| self.changed.insert(v); | |
| } | |
| /// Fetches all changes to the values of variables since the last call to this function. | |
| /// | |
| /// The list of changes returned is not in a specific order. Each change comprises the variable changed and | |
| /// the new value of that variable. | |
| pub fn fetch_changes(&mut self) -> &[(Variable, f64)] { | |
| if self.should_clear_changes { | |
| self.changed.clear(); | |
| self.should_clear_changes = false; | |
| } else { | |
| self.should_clear_changes = true; | |
| } | |
| self.public_changes.clear(); | |
| for &v in &self.changed { | |
| if let Some(var_data) = self.var_data.get_mut(&v) { | |
| let new_value = self.rows.get(&var_data.1).map(|r| r.constant).unwrap_or(0.0); | |
| let old_value = var_data.0; | |
| if old_value != new_value { | |
| self.public_changes.push((v, new_value)); | |
| var_data.0 = new_value; | |
| } | |
| } | |
| } | |
| &self.public_changes | |
| } | |
| /// Reset the solver to the empty starting condition. | |
| /// | |
| /// This method resets the internal solver state to the empty starting | |
| /// condition, as if no constraints or edit variables have been added. | |
| /// This can be faster than deleting the solver and creating a new one | |
| /// when the entire system must change, since it can avoid unnecessary | |
| /// heap (de)allocations. | |
| pub fn reset(&mut self) { | |
| self.rows.clear(); | |
| self.cns.clear(); | |
| self.var_data.clear(); | |
| self.var_for_symbol.clear(); | |
| self.changed.clear(); | |
| self.should_clear_changes = false; | |
| self.edits.clear(); | |
| self.infeasible_rows.clear(); | |
| *self.objective.borrow_mut() = Row::new(0.0); | |
| self.artificial = None; | |
| self.id_tick = 1; | |
| } | |
| /// Get the symbol for the given variable. | |
| /// | |
| /// If a symbol does not exist for the variable, one will be created. | |
| fn get_var_symbol(&mut self, v: Variable) -> Symbol { | |
| let id_tick = &mut self.id_tick; | |
| let var_for_symbol = &mut self.var_for_symbol; | |
| let value = self.var_data.entry(v).or_insert_with(|| { | |
| let s = Symbol(*id_tick, SymbolType::External); | |
| var_for_symbol.insert(s, v); | |
| *id_tick += 1; | |
| (::std::f64::NAN, s, 0) | |
| }); | |
| value.2 += 1; | |
| value.1 | |
| } | |
| /// Create a new Row object for the given constraint. | |
| /// | |
| /// The terms in the constraint will be converted to cells in the row. | |
| /// Any term in the constraint with a coefficient of zero is ignored. | |
| /// This method uses the `getVarSymbol` method to get the symbol for | |
| /// the variables added to the row. If the symbol for a given cell | |
| /// variable is basic, the cell variable will be substituted with the | |
| /// basic row. | |
| /// | |
| /// The necessary slack and error variables will be added to the row. | |
| /// If the constant for the row is negative, the sign for the row | |
| /// will be inverted so the constant becomes positive. | |
| /// | |
| /// The tag will be updated with the marker and error symbols to use | |
| /// for tracking the movement of the constraint in the tableau. | |
| fn create_row(&mut self, constraint: &Constraint) -> (Box<Row>, Tag) { | |
| let expr = constraint.expr(); | |
| let mut row = Row::new(expr.constant); | |
| // Substitute the current basic variables into the row. | |
| for term in &expr.terms { | |
| if !near_zero(term.coefficient) { | |
| let symbol = self.get_var_symbol(term.variable); | |
| if let Some(other_row) = self.rows.get(&symbol) { | |
| row.insert_row(other_row, term.coefficient); | |
| } else { | |
| row.insert_symbol(symbol, term.coefficient); | |
| } | |
| } | |
| } | |
| let mut objective = self.objective.borrow_mut(); | |
| // Add the necessary slack, error, and dummy variables. | |
| let tag = match constraint.op() { | |
| RelationalOperator::GreaterOrEqual | | |
| RelationalOperator::LessOrEqual => { | |
| let coeff = if constraint.op() == RelationalOperator::LessOrEqual { | |
| 1.0 | |
| } else { | |
| -1.0 | |
| }; | |
| let slack = Symbol(self.id_tick, SymbolType::Slack); | |
| self.id_tick += 1; | |
| row.insert_symbol(slack, coeff); | |
| if constraint.strength() < ::strength::REQUIRED { | |
| let error = Symbol(self.id_tick, SymbolType::Error); | |
| self.id_tick += 1; | |
| row.insert_symbol(error, -coeff); | |
| objective.insert_symbol(error, constraint.strength()); | |
| Tag { | |
| marker: slack, | |
| other: error | |
| } | |
| } else { | |
| Tag { | |
| marker: slack, | |
| other: Symbol::invalid() | |
| } | |
| } | |
| } | |
| RelationalOperator::Equal => { | |
| if constraint.strength() < ::strength::REQUIRED { | |
| let errplus = Symbol(self.id_tick, SymbolType::Error); | |
| self.id_tick += 1; | |
| let errminus = Symbol(self.id_tick, SymbolType::Error); | |
| self.id_tick += 1; | |
| row.insert_symbol(errplus, -1.0); // v = eplus - eminus | |
| row.insert_symbol(errminus, 1.0); // v - eplus + eminus = 0 | |
| objective.insert_symbol(errplus, constraint.strength()); | |
| objective.insert_symbol(errminus, constraint.strength()); | |
| Tag { | |
| marker: errplus, | |
| other: errminus | |
| } | |
| } else { | |
| let dummy = Symbol(self.id_tick, SymbolType::Dummy); | |
| self.id_tick += 1; | |
| row.insert_symbol(dummy, 1.0); | |
| Tag { | |
| marker: dummy, | |
| other: Symbol::invalid() | |
| } | |
| } | |
| } | |
| }; | |
| // Ensure the row has a positive constant. | |
| if row.constant < 0.0 { | |
| row.reverse_sign(); | |
| } | |
| (Box::new(row), tag) | |
| } | |
| /// Choose the subject for solving for the row. | |
| /// | |
| /// This method will choose the best subject for using as the solve | |
| /// target for the row. An invalid symbol will be returned if there | |
| /// is no valid target. | |
| /// | |
| /// The symbols are chosen according to the following precedence: | |
| /// | |
| /// 1) The first symbol representing an external variable. | |
| /// 2) A negative slack or error tag variable. | |
| /// | |
| /// If a subject cannot be found, an invalid symbol will be returned. | |
| fn choose_subject(row: &Row, tag: &Tag) -> Symbol { | |
| for s in row.cells.keys() { | |
| if s.type_() == SymbolType::External { | |
| return *s | |
| } | |
| } | |
| if tag.marker.type_() == SymbolType::Slack || tag.marker.type_() == SymbolType::Error { | |
| if row.coefficient_for(tag.marker) < 0.0 { | |
| return tag.marker; | |
| } | |
| } | |
| if tag.other.type_() == SymbolType::Slack || tag.other.type_() == SymbolType::Error { | |
| if row.coefficient_for(tag.other) < 0.0 { | |
| return tag.other; | |
| } | |
| } | |
| Symbol::invalid() | |
| } | |
| /// Add the row to the tableau using an artificial variable. | |
| /// | |
| /// This will return false if the constraint cannot be satisfied. | |
| fn add_with_artificial_variable(&mut self, row: &Row) -> Result<bool, InternalSolverError> { | |
| // Create and add the artificial variable to the tableau | |
| let art = Symbol(self.id_tick, SymbolType::Slack); | |
| self.id_tick += 1; | |
| self.rows.insert(art, Box::new(row.clone())); | |
| self.artificial = Some(Rc::new(RefCell::new(row.clone()))); | |
| // Optimize the artificial objective. This is successful | |
| // only if the artificial objective is optimized to zero. | |
| let artificial = self.artificial.as_ref().unwrap().clone(); | |
| try!(self.optimise(&artificial)); | |
| let success = near_zero(artificial.borrow().constant); | |
| self.artificial = None; | |
| // If the artificial variable is basic, pivot the row so that | |
| // it becomes basic. If the row is constant, exit early. | |
| if let Some(mut row) = self.rows.remove(&art) { | |
| if row.cells.is_empty() { | |
| return Ok(success); | |
| } | |
| let entering = Solver::any_pivotable_symbol(&row); // never External | |
| if entering.type_() == SymbolType::Invalid { | |
| return Ok(false); // unsatisfiable (will this ever happen?) | |
| } | |
| row.solve_for_symbols(art, entering); | |
| self.substitute(entering, &row); | |
| self.rows.insert(entering, row); | |
| } | |
| // Remove the artificial row from the tableau | |
| for (_, row) in &mut self.rows { | |
| row.remove(art); | |
| } | |
| self.objective.borrow_mut().remove(art); | |
| Ok(success) | |
| } | |
| /// Substitute the parametric symbol with the given row. | |
| /// | |
| /// This method will substitute all instances of the parametric symbol | |
| /// in the tableau and the objective function with the given row. | |
| fn substitute(&mut self, symbol: Symbol, row: &Row) { | |
| for (&other_symbol, other_row) in &mut self.rows { | |
| let constant_changed = other_row.substitute(symbol, row); | |
| if other_symbol.type_() == SymbolType::External && constant_changed { | |
| let v = self.var_for_symbol[&other_symbol]; | |
| // inline var_changed | |
| if self.should_clear_changes { | |
| self.changed.clear(); | |
| self.should_clear_changes = false; | |
| } | |
| self.changed.insert(v); | |
| } | |
| if other_symbol.type_() != SymbolType::External && other_row.constant < 0.0 { | |
| self.infeasible_rows.push(other_symbol); | |
| } | |
| } | |
| self.objective.borrow_mut().substitute(symbol, row); | |
| if let Some(artificial) = self.artificial.as_ref() { | |
| artificial.borrow_mut().substitute(symbol, row); | |
| } | |
| } | |
| /// Optimize the system for the given objective function. | |
| /// | |
| /// This method performs iterations of Phase 2 of the simplex method | |
| /// until the objective function reaches a minimum. | |
| fn optimise(&mut self, objective: &RefCell<Row>) -> Result<(), InternalSolverError> { | |
| loop { | |
| let entering = Solver::get_entering_symbol(&objective.borrow()); | |
| if entering.type_() == SymbolType::Invalid { | |
| return Ok(()); | |
| } | |
| let (leaving, mut row) = try!(self.get_leaving_row(entering) | |
| .ok_or(InternalSolverError("The objective is unbounded"))); | |
| // pivot the entering symbol into the basis | |
| row.solve_for_symbols(leaving, entering); | |
| self.substitute(entering, &row); | |
| if entering.type_() == SymbolType::External && row.constant != 0.0 { | |
| let v = self.var_for_symbol[&entering]; | |
| self.var_changed(v); | |
| } | |
| self.rows.insert(entering, row); | |
| } | |
| } | |
| /// Optimize the system using the dual of the simplex method. | |
| /// | |
| /// The current state of the system should be such that the objective | |
| /// function is optimal, but not feasible. This method will perform | |
| /// an iteration of the dual simplex method to make the solution both | |
| /// optimal and feasible. | |
| fn dual_optimise(&mut self) -> Result<(), InternalSolverError> { | |
| while !self.infeasible_rows.is_empty() { | |
| let leaving = self.infeasible_rows.pop().unwrap(); | |
| let row = if let Entry::Occupied(entry) = self.rows.entry(leaving) { | |
| if entry.get().constant < 0.0 { | |
| Some(entry.remove()) | |
| } else { | |
| None | |
| } | |
| } else { | |
| None | |
| }; | |
| if let Some(mut row) = row { | |
| let entering = self.get_dual_entering_symbol(&row); | |
| if entering.type_() == SymbolType::Invalid { | |
| return Err(InternalSolverError("Dual optimise failed.")); | |
| } | |
| // pivot the entering symbol into the basis | |
| row.solve_for_symbols(leaving, entering); | |
| self.substitute(entering, &row); | |
| if entering.type_() == SymbolType::External && row.constant != 0.0 { | |
| let v = self.var_for_symbol[&entering]; | |
| self.var_changed(v); | |
| } | |
| self.rows.insert(entering, row); | |
| } | |
| } | |
| Ok(()) | |
| } | |
| /// Compute the entering variable for a pivot operation. | |
| /// | |
| /// This method will return first symbol in the objective function which | |
| /// is non-dummy and has a coefficient less than zero. If no symbol meets | |
| /// the criteria, it means the objective function is at a minimum, and an | |
| /// invalid symbol is returned. | |
| /// Could return an External symbol | |
| fn get_entering_symbol(objective: &Row) -> Symbol { | |
| for (symbol, value) in &objective.cells { | |
| if symbol.type_() != SymbolType::Dummy && *value < 0.0 { | |
| return *symbol; | |
| } | |
| } | |
| Symbol::invalid() | |
| } | |
| /// Compute the entering symbol for the dual optimize operation. | |
| /// | |
| /// This method will return the symbol in the row which has a positive | |
| /// coefficient and yields the minimum ratio for its respective symbol | |
| /// in the objective function. The provided row *must* be infeasible. | |
| /// If no symbol is found which meats the criteria, an invalid symbol | |
| /// is returned. | |
| /// Could return an External symbol | |
| fn get_dual_entering_symbol(&self, row: &Row) -> Symbol { | |
| let mut entering = Symbol::invalid(); | |
| let mut ratio = ::std::f64::INFINITY; | |
| let objective = self.objective.borrow(); | |
| for (symbol, value) in &row.cells { | |
| if *value > 0.0 && symbol.type_() != SymbolType::Dummy { | |
| let coeff = objective.coefficient_for(*symbol); | |
| let r = coeff / *value; | |
| if r < ratio { | |
| ratio = r; | |
| entering = *symbol; | |
| } | |
| } | |
| } | |
| entering | |
| } | |
| /// Get the first Slack or Error symbol in the row. | |
| /// | |
| /// If no such symbol is present, and Invalid symbol will be returned. | |
| /// Never returns an External symbol | |
| fn any_pivotable_symbol(row: &Row) -> Symbol { | |
| for symbol in row.cells.keys() { | |
| if symbol.type_() == SymbolType::Slack || symbol.type_() == SymbolType::Error { | |
| return *symbol; | |
| } | |
| } | |
| Symbol::invalid() | |
| } | |
| /// Compute the row which holds the exit symbol for a pivot. | |
| /// | |
| /// This method will return an iterator to the row in the row map | |
| /// which holds the exit symbol. If no appropriate exit symbol is | |
| /// found, the end() iterator will be returned. This indicates that | |
| /// the objective function is unbounded. | |
| /// Never returns a row for an External symbol | |
| fn get_leaving_row(&mut self, entering: Symbol) -> Option<(Symbol, Box<Row>)> { | |
| let mut ratio = ::std::f64::INFINITY; | |
| let mut found = None; | |
| for (symbol, row) in &self.rows { | |
| if symbol.type_() != SymbolType::External { | |
| let temp = row.coefficient_for(entering); | |
| if temp < 0.0 { | |
| let temp_ratio = -row.constant / temp; | |
| if temp_ratio < ratio { | |
| ratio = temp_ratio; | |
| found = Some(*symbol); | |
| } | |
| } | |
| } | |
| } | |
| found.map(|s| (s, self.rows.remove(&s).unwrap())) | |
| } | |
| /// Compute the leaving row for a marker variable. | |
| /// | |
| /// This method will return an iterator to the row in the row map | |
| /// which holds the given marker variable. The row will be chosen | |
| /// according to the following precedence: | |
| /// | |
| /// 1) The row with a restricted basic varible and a negative coefficient | |
| /// for the marker with the smallest ratio of -constant / coefficient. | |
| /// | |
| /// 2) The row with a restricted basic variable and the smallest ratio | |
| /// of constant / coefficient. | |
| /// | |
| /// 3) The last unrestricted row which contains the marker. | |
| /// | |
| /// If the marker does not exist in any row, the row map end() iterator | |
| /// will be returned. This indicates an internal solver error since | |
| /// the marker *should* exist somewhere in the tableau. | |
| fn get_marker_leaving_row(&mut self, marker: Symbol) -> Option<(Symbol, Box<Row>)> { | |
| let mut r1 = ::std::f64::INFINITY; | |
| let mut r2 = r1; | |
| let mut first = None; | |
| let mut second = None; | |
| let mut third = None; | |
| for (symbol, row) in &self.rows { | |
| let c = row.coefficient_for(marker); | |
| if c == 0.0 { | |
| continue; | |
| } | |
| if symbol.type_() == SymbolType::External { | |
| third = Some(*symbol); | |
| } else if c < 0.0 { | |
| let r = -row.constant / c; | |
| if r < r1 { | |
| r1 = r; | |
| first = Some(*symbol); | |
| } | |
| } else { | |
| let r = row.constant / c; | |
| if r < r2 { | |
| r2 = r; | |
| second = Some(*symbol); | |
| } | |
| } | |
| } | |
| first | |
| .or(second) | |
| .or(third) | |
| .and_then(|s| { | |
| if s.type_() == SymbolType::External && self.rows[&s].constant != 0.0 { | |
| let v = self.var_for_symbol[&s]; | |
| self.var_changed(v); | |
| } | |
| self.rows | |
| .remove(&s) | |
| .map(|r| (s, r)) | |
| }) | |
| } | |
| /// Remove the effects of a constraint on the objective function. | |
| fn remove_constraint_effects(&mut self, cn: &Constraint, tag: &Tag) { | |
| if tag.marker.type_() == SymbolType::Error { | |
| self.remove_marker_effects(tag.marker, cn.strength()); | |
| } else if tag.other.type_() == SymbolType::Error { | |
| self.remove_marker_effects(tag.other, cn.strength()); | |
| } | |
| } | |
| /// Remove the effects of an error marker on the objective function. | |
| fn remove_marker_effects(&mut self, marker: Symbol, strength: f64) { | |
| if let Some(row) = self.rows.get(&marker) { | |
| self.objective.borrow_mut().insert_row(row, -strength); | |
| } else { | |
| self.objective.borrow_mut().insert_symbol(marker, -strength); | |
| } | |
| } | |
| /// Test whether a row is composed of all dummy variables. | |
| fn all_dummies(row: &Row) -> bool { | |
| for symbol in row.cells.keys() { | |
| if symbol.type_() != SymbolType::Dummy { | |
| return false; | |
| } | |
| } | |
| true | |
| } | |
| /// Get the stored value for a variable. | |
| /// | |
| /// Normally values should be retrieved and updated using `fetch_changes`, but | |
| /// this method can be used for debugging or testing. | |
| pub fn get_value(&self, v: Variable) -> f64 { | |
| self.var_data.get(&v).and_then(|s| { | |
| self.rows.get(&s.1).map(|r| r.constant) | |
| }).unwrap_or(0.0) | |
| } | |
| } |