headers/libs/linprog/LinearSpec.h

   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