1 /* 2 * Copyright 2007-2008, Christof Lutteroth, lutteroth@cs.auckland.ac.nz 3 * Copyright 2007-2008, James Kim, jkim202@ec.auckland.ac.nz 4 * Copyright 2010, Clemens Zeidler, haiku@clemens-zeidler.de 5 * Distributed under the terms of the MIT License. 6 */ 7 #ifndef LINEAR_SPEC_H 8 #define LINEAR_SPEC_H 9 10 #include <ObjectList.h> 11 #include <OS.h> 12 #include <Referenceable.h> 13 #include <Size.h> 14 #include <String.h> 15 #include <SupportDefs.h> 16 17 #include "Constraint.h" 18 #include "LinearProgrammingTypes.h" 19 #include "Summand.h" 20 #include "Variable.h" 21 22 23 namespace LinearProgramming { 24 25 26 class LinearSpec; 27 28 29 const BSize kMinSize(0, 0); 30 const BSize kMaxSize(B_SIZE_UNLIMITED, B_SIZE_UNLIMITED); 31 32 33 class SolverInterface { 34 public: 35 SolverInterface(LinearSpec* linSpec); 36 37 virtual ~SolverInterface(); 38 39 virtual ResultType Solve() = 0; 40 41 virtual bool VariableAdded(Variable* variable) = 0; 42 virtual bool VariableRemoved(Variable* variable) = 0; 43 virtual bool VariableRangeChanged(Variable* variable) = 0; 44 45 virtual bool ConstraintAdded(Constraint* constraint) = 0; 46 virtual bool ConstraintRemoved(Constraint* constraint) = 0; 47 virtual bool LeftSideChanged(Constraint* constraint) = 0; 48 virtual bool RightSideChanged(Constraint* constraint) = 0; 49 virtual bool OperatorChanged(Constraint* constraint) = 0; 50 virtual bool PenaltiesChanged(Constraint* constraint) = 0; 51 52 virtual bool SaveModel(const char* fileName) = 0; 53 54 virtual ResultType FindMins(const VariableList* variables) = 0; 55 virtual ResultType FindMaxs(const VariableList* variables) = 0; 56 57 virtual void GetRangeConstraints(const Variable* var, 58 const Constraint** _min, 59 const Constraint** _max) const = 0; 60 61 protected: 62 bool AddConstraint(Constraint* constraint, 63 bool notifyListener); 64 bool RemoveConstraint(Constraint* constraint, 65 bool deleteConstraint, bool notifyListener); 66 67 LinearSpec* fLinearSpec; 68 }; 69 70 71 class SpecificationListener { 72 public: 73 virtual ~SpecificationListener(); 74 75 virtual void VariableAdded(Variable* variable); 76 virtual void VariableRemoved(Variable* variable); 77 virtual void ConstraintAdded(Constraint* constraint); 78 virtual void ConstraintRemoved(Constraint* constraint); 79 }; 80 81 82 /*! 83 * Specification of a linear programming problem. 84 */ 85 class LinearSpec : public BReferenceable { 86 public: 87 LinearSpec(); 88 virtual ~LinearSpec(); 89 90 /*! Does not takes ownership of the listener. */ 91 bool AddListener(SpecificationListener* listener); 92 bool RemoveListener(SpecificationListener* listener); 93 94 Variable* AddVariable(); 95 bool AddVariable(Variable* variable); 96 bool RemoveVariable(Variable* variable, 97 bool deleteVariable = true); 98 int32 IndexOf(const Variable* variable) const; 99 int32 GlobalIndexOf(const Variable* variable) const; 100 bool UpdateRange(Variable* variable); 101 102 bool AddConstraint(Constraint* constraint); 103 bool RemoveConstraint(Constraint* constraint, 104 bool deleteConstraint = true); 105 106 Constraint* AddConstraint(SummandList* summands, 107 OperatorType op, double rightSide, 108 double penaltyNeg = -1, 109 double penaltyPos = -1); 110 Constraint* AddConstraint(double coeff1, Variable* var1, 111 OperatorType op, double rightSide, 112 double penaltyNeg = -1, 113 double penaltyPos = -1); 114 Constraint* AddConstraint(double coeff1, Variable* var1, 115 double coeff2, Variable* var2, 116 OperatorType op, double rightSide, 117 double penaltyNeg = -1, 118 double penaltyPos = -1); 119 Constraint* AddConstraint(double coeff1, Variable* var1, 120 double coeff2, Variable* var2, 121 double coeff3, Variable* var3, 122 OperatorType op, double rightSide, 123 double penaltyNeg = -1, 124 double penaltyPos = -1); 125 Constraint* AddConstraint(double coeff1, Variable* var1, 126 double coeff2, Variable* var2, 127 double coeff3, Variable* var3, 128 double coeff4, Variable* var4, 129 OperatorType op, double rightSide, 130 double penaltyNeg = -1, 131 double penaltyPos = -1); 132 133 ResultType FindMins(const VariableList* variables); 134 ResultType FindMaxs(const VariableList* variables); 135 136 ResultType Solve(); 137 bool Save(const char* fileName); 138 139 int32 CountColumns() const; 140 141 ResultType Result() const; 142 bigtime_t SolvingTime() const; 143 144 BString ToString() const; 145 146 void GetRangeConstraints(const Variable*, 147 const Constraint** _min, 148 const Constraint** _max) const; 149 const ConstraintList& Constraints() const; 150 const VariableList& UsedVariables() const; 151 const VariableList& AllVariables() const; 152 153 protected: 154 friend class Constraint; 155 friend class SolverInterface; 156 157 bool UpdateLeftSide(Constraint* constraint, 158 const SummandList* oldSummands); 159 bool UpdateRightSide(Constraint* constraint); 160 bool UpdateOperator(Constraint* constraint); 161 bool UpdatePenalties(Constraint* constraint); 162 163 bool AddConstraint(Constraint* constraint, 164 bool notifyListener); 165 bool RemoveConstraint(Constraint* constraint, 166 bool deleteConstraint, bool notifyListener); 167 private: 168 /*! Check if all entries != NULL otherwise delete the list and its 169 entries. */ 170 bool _CheckSummandList(SummandList* list); 171 Constraint* _AddConstraint(SummandList* leftSide, 172 OperatorType op, double rightSide, 173 double penaltyNeg, double penaltyPos); 174 175 void _AddConstraintRef(Variable* var); 176 void _RemoveConstraintRef(Variable* var); 177 178 VariableList fVariables; 179 VariableList fUsedVariables; 180 ConstraintList fConstraints; 181 ResultType fResult; 182 bigtime_t fSolvingTime; 183 184 SolverInterface* fSolver; 185 186 BObjectList<SpecificationListener> fListeners; 187 }; 188 189 } // namespace LinearProgramming 190 191 using LinearProgramming::LinearSpec; 192 193 #endif // LINEAR_SPEC_H 194