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 <math.h> 11 12 #include <List.h> 13 #include <OS.h> 14 #include <Referenceable.h> 15 #include <Size.h> 16 #include <String.h> 17 #include <SupportDefs.h> 18 19 #include "Constraint.h" 20 #include "LinearProgrammingTypes.h" 21 #include "Summand.h" 22 #include "Variable.h" 23 24 25 namespace LinearProgramming { 26 27 28 class LinearSpec; 29 30 31 const BSize kMinSize(0, 0); 32 const BSize kMaxSize(B_SIZE_UNLIMITED, B_SIZE_UNLIMITED); 33 34 35 class SolverInterface { 36 public: 37 SolverInterface(LinearSpec* linSpec); 38 39 virtual ~SolverInterface() {} 40 41 virtual ResultType Solve() = 0; 42 43 virtual bool VariableAdded(Variable* variable) = 0; 44 virtual bool VariableRemoved(Variable* variable) = 0; 45 virtual bool VariableRangeChanged(Variable* variable) = 0; 46 47 virtual bool ConstraintAdded(Constraint* constraint) = 0; 48 virtual bool ConstraintRemoved(Constraint* constraint) = 0; 49 virtual bool LeftSideChanged(Constraint* constraint) = 0; 50 virtual bool RightSideChanged(Constraint* constraint) = 0; 51 virtual bool OperatorChanged(Constraint* constraint) = 0; 52 53 virtual bool SaveModel(const char* fileName) = 0; 54 55 virtual BSize MinSize(Variable* width, Variable* height) = 0; 56 virtual BSize MaxSize(Variable* width, Variable* height) = 0; 57 58 virtual ResultType FindMins(const VariableList* variables) = 0; 59 virtual ResultType FindMaxs(const VariableList* variables) = 0; 60 61 virtual void GetRangeConstraints(const Variable* var, 62 const Constraint** _min, 63 const Constraint** _max) const = 0; 64 65 protected: 66 LinearSpec* fLinearSpec; 67 }; 68 69 70 /*! 71 * Specification of a linear programming problem. 72 */ 73 class LinearSpec : public BReferenceable { 74 public: 75 LinearSpec(); 76 virtual ~LinearSpec(); 77 78 Variable* AddVariable(); 79 bool AddVariable(Variable* variable); 80 bool RemoveVariable(Variable* variable, 81 bool deleteVariable = true); 82 int32 IndexOf(const Variable* variable) const; 83 int32 GlobalIndexOf(const Variable* variable) const; 84 bool UpdateRange(Variable* variable); 85 86 bool AddConstraint(Constraint* constraint); 87 bool RemoveConstraint(Constraint* constraint, 88 bool deleteConstraint = true); 89 90 Constraint* AddConstraint(SummandList* summands, 91 OperatorType op, double rightSide); 92 Constraint* AddConstraint(double coeff1, Variable* var1, 93 OperatorType op, double rightSide); 94 Constraint* AddConstraint(double coeff1, Variable* var1, 95 double coeff2, Variable* var2, 96 OperatorType op, double rightSide); 97 Constraint* AddConstraint(double coeff1, Variable* var1, 98 double coeff2, Variable* var2, 99 double coeff3, Variable* var3, 100 OperatorType op, double rightSide); 101 Constraint* AddConstraint(double coeff1, Variable* var1, 102 double coeff2, Variable* var2, 103 double coeff3, Variable* var3, 104 double coeff4, Variable* var4, 105 OperatorType op, double rightSide); 106 107 Constraint* AddConstraint(SummandList* summands, 108 OperatorType op, double rightSide, 109 double penaltyNeg, double penaltyPos); 110 Constraint* AddConstraint(double coeff1, Variable* var1, 111 OperatorType op, double rightSide, 112 double penaltyNeg, double penaltyPos); 113 Constraint* AddConstraint(double coeff1, Variable* var1, 114 double coeff2, Variable* var2, 115 OperatorType op, double rightSide, 116 double penaltyNeg, double penaltyPos); 117 Constraint* AddConstraint(double coeff1, Variable* var1, 118 double coeff2, Variable* var2, 119 double coeff3, Variable* var3, 120 OperatorType op, double rightSide, 121 double penaltyNeg, double penaltyPos); 122 Constraint* AddConstraint(double coeff1, Variable* var1, 123 double coeff2, Variable* var2, 124 double coeff3, Variable* var3, 125 double coeff4, Variable* var4, 126 OperatorType op, double rightSide, 127 double penaltyNeg, double penaltyPos); 128 129 BSize MinSize(Variable* width, Variable* height); 130 BSize MaxSize(Variable* width, Variable* height); 131 132 ResultType FindMins(const VariableList* variables); 133 ResultType FindMaxs(const VariableList* variables); 134 135 ResultType Solve(); 136 bool Save(const char* fileName); 137 138 int32 CountColumns() const; 139 140 ResultType Result() const; 141 bigtime_t SolvingTime() const; 142 143 BString ToString() const; 144 145 void GetRangeConstraints(const Variable*, 146 const Constraint** _min, 147 const Constraint** _max) const; 148 const ConstraintList& Constraints() const; 149 const VariableList& UsedVariables() const; 150 const VariableList& AllVariables() const; 151 152 protected: 153 friend class Constraint; 154 bool UpdateLeftSide(Constraint* constraint); 155 bool UpdateRightSide(Constraint* constraint); 156 bool UpdateOperator(Constraint* constraint); 157 private: 158 /*! Check if all entries != NULL otherwise delete the list and its 159 entries. */ 160 bool _CheckSummandList(SummandList* list); 161 Constraint* _AddConstraint(SummandList* leftSide, 162 OperatorType op, double rightSide, 163 double penaltyNeg, double penaltyPos); 164 165 VariableList fVariables; 166 VariableList fUsedVariables; 167 ConstraintList fConstraints; 168 ResultType fResult; 169 bigtime_t fSolvingTime; 170 171 SolverInterface* fSolver; 172 }; 173 174 } // namespace LinearProgramming 175 176 using LinearProgramming::LinearSpec; 177 178 #endif // LINEAR_SPEC_H 179