1 /* 2 * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de> 3 * Distributed under the terms of the MIT License. 4 */ 5 #ifndef ACTICE_SET_SOLVER_H 6 #define ACTICE_SET_SOLVER_H 7 8 9 #include "LinearSpec.h" 10 11 12 class EquationSystem { 13 public: 14 EquationSystem(int32 rows, int32 columns); 15 ~EquationSystem(); 16 17 void SetRows(int32 rows); 18 int32 Rows(); 19 int32 Columns(); 20 21 //! Debug function: check bounds 22 bool InRange(int32 row, int32 column); 23 inline double& A(int32 row, int32 column); 24 inline double& B(int32 row); 25 /*! Copy the solved variables into results, keeping the original 26 variable order. */ 27 inline void Results(double* results, int32 size); 28 29 inline void SwapColumn(int32 i, int32 j); 30 inline void SwapRow(int32 i, int32 j); 31 32 bool GaussianElimination(); 33 bool GaussJordan(); 34 /*! Gauss Jordan elimination just for one column, the diagonal 35 element must be none zero. */ 36 void GaussJordan(int32 column); 37 38 void RemoveLinearlyDependentRows(); 39 void RemoveUnusedVariables(); 40 41 void MoveColumnRight(int32 i, int32 target); 42 43 void Print(); 44 private: 45 inline void _EliminateColumn(int32 column, int32 startRow, 46 int32 endRow); 47 48 int32* fRowIndices; 49 int32* fColumnIndices; 50 double** fMatrix; 51 double* fB; 52 int32 fRows; 53 int32 fColumns; 54 }; 55 56 57 class ActiveSetSolver : public LinearProgramming::SolverInterface { 58 public: 59 ActiveSetSolver(LinearSpec* linearSpec); 60 ~ActiveSetSolver(); 61 62 ResultType Solve(); 63 64 bool VariableAdded(Variable* variable); 65 bool VariableRemoved(Variable* variable); 66 bool VariableRangeChanged(Variable* variable); 67 68 bool ConstraintAdded(Constraint* constraint); 69 bool ConstraintRemoved(Constraint* constraint); 70 bool LeftSideChanged(Constraint* constraint); 71 bool RightSideChanged(Constraint* constraint); 72 bool OperatorChanged(Constraint* constraint); 73 bool PenaltiesChanged(Constraint* constraint); 74 75 bool SaveModel(const char* fileName); 76 77 ResultType FindMaxs(const VariableList* variables); 78 ResultType FindMins(const VariableList* variables); 79 80 void GetRangeConstraints(const Variable* var, 81 const Constraint** _min, 82 const Constraint** _max) const; 83 84 private: 85 void _RemoveSoftConstraint(ConstraintList& list); 86 void _AddSoftConstraint(const ConstraintList& list); 87 88 typedef Constraint* (*AddConstraintFunc)(LinearSpec* spec, Variable* var); 89 90 ResultType _FindWithConstraintsNoSoft( 91 const VariableList* variables, 92 AddConstraintFunc constraintFunc); 93 94 const VariableList& fVariables; 95 const ConstraintList& fConstraints; 96 97 ConstraintList fVariableGEConstraints; 98 ConstraintList fVariableLEConstraints; 99 }; 100 101 102 #endif // ACTICE_SET_SOLVER_H 103