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 protected: 62 LinearSpec* fLinearSpec; 63 }; 64 65 66 /*! 67 * Specification of a linear programming problem. 68 */ 69 class LinearSpec : public BReferenceable { 70 public: 71 LinearSpec(); 72 virtual ~LinearSpec(); 73 74 Variable* AddVariable(); 75 bool AddVariable(Variable* variable); 76 bool RemoveVariable(Variable* variable, 77 bool deleteVariable = true); 78 int32 IndexOf(const Variable* variable) const; 79 int32 GlobalIndexOf(const Variable* variable) const; 80 bool UpdateRange(Variable* variable); 81 82 bool AddConstraint(Constraint* constraint); 83 bool RemoveConstraint(Constraint* constraint, 84 bool deleteConstraint = true); 85 86 Constraint* AddConstraint(SummandList* summands, 87 OperatorType op, double rightSide); 88 Constraint* AddConstraint(double coeff1, Variable* var1, 89 OperatorType op, double rightSide); 90 Constraint* AddConstraint(double coeff1, Variable* var1, 91 double coeff2, Variable* var2, 92 OperatorType op, double rightSide); 93 Constraint* AddConstraint(double coeff1, Variable* var1, 94 double coeff2, Variable* var2, 95 double coeff3, Variable* var3, 96 OperatorType op, double rightSide); 97 Constraint* AddConstraint(double coeff1, Variable* var1, 98 double coeff2, Variable* var2, 99 double coeff3, Variable* var3, 100 double coeff4, Variable* var4, 101 OperatorType op, double rightSide); 102 103 Constraint* AddConstraint(SummandList* summands, 104 OperatorType op, double rightSide, 105 double penaltyNeg, double penaltyPos); 106 Constraint* AddConstraint(double coeff1, Variable* var1, 107 OperatorType op, double rightSide, 108 double penaltyNeg, double penaltyPos); 109 Constraint* AddConstraint(double coeff1, Variable* var1, 110 double coeff2, Variable* var2, 111 OperatorType op, double rightSide, 112 double penaltyNeg, double penaltyPos); 113 Constraint* AddConstraint(double coeff1, Variable* var1, 114 double coeff2, Variable* var2, 115 double coeff3, Variable* var3, 116 OperatorType op, double rightSide, 117 double penaltyNeg, double penaltyPos); 118 Constraint* AddConstraint(double coeff1, Variable* var1, 119 double coeff2, Variable* var2, 120 double coeff3, Variable* var3, 121 double coeff4, Variable* var4, 122 OperatorType op, double rightSide, 123 double penaltyNeg, double penaltyPos); 124 125 BSize MinSize(Variable* width, Variable* height); 126 BSize MaxSize(Variable* width, Variable* height); 127 128 ResultType FindMins(const VariableList* variables); 129 ResultType FindMaxs(const VariableList* variables); 130 131 ResultType Solve(); 132 bool Save(const char* fileName); 133 134 int32 CountColumns() const; 135 136 ResultType Result() const; 137 bigtime_t SolvingTime() const; 138 139 BString ToString() const; 140 141 const ConstraintList& Constraints() const; 142 const VariableList& UsedVariables() const; 143 const VariableList& AllVariables() const; 144 145 protected: 146 friend class Constraint; 147 bool UpdateLeftSide(Constraint* constraint); 148 bool UpdateRightSide(Constraint* constraint); 149 bool UpdateOperator(Constraint* constraint); 150 private: 151 /*! Check if all entries != NULL otherwise delete the list and its 152 entries. */ 153 bool _CheckSummandList(SummandList* list); 154 Constraint* _AddConstraint(SummandList* leftSide, 155 OperatorType op, double rightSide, 156 double penaltyNeg, double penaltyPos); 157 158 VariableList fVariables; 159 VariableList fUsedVariables; 160 ConstraintList fConstraints; 161 ResultType fResult; 162 bigtime_t fSolvingTime; 163 164 SolverInterface* fSolver; 165 }; 166 167 } // namespace LinearProgramming 168 169 using LinearProgramming::LinearSpec; 170 171 #endif // LINEAR_SPEC_H 172