src/libs/linprog/Constraint.cpp

   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
   8
   9 #include "Constraint.h"
  10
  11 #include <new>
  12 #include <stdio.h>
  13
  14 #include "LinearSpec.h"
  15 #include "Variable.h"
  16
  17
  18 // Toggle debug output
  19 //#define DEBUG_CONSTRAINT
  20
  21 #ifdef DEBUG_CONSTRAINT
  22 #       define STRACE(x) debug_printf x
  23 #else
  24 #       define STRACE(x) ;
  25 #endif
  26
  27
  28 Constraint::Constraint()
  29         :
  30         fLS(NULL),
  31         fLeftSide(new SummandList),
  32         fOp(kEQ),
  33         fRightSide(0),
  34         fPenaltyNeg(-1),
  35         fPenaltyPos(-1)
  36 {
  37 }
  38
  39
  40 Constraint::Constraint(Constraint* constraint)
  41         :
  42         fLS(NULL),
  43         fLeftSide(new SummandList),
  44         fOp(constraint->Op()),
  45         fRightSide(constraint->RightSide()),
  46         fPenaltyNeg(constraint->PenaltyNeg()),
  47         fPenaltyPos(constraint->PenaltyPos()),
  48         fLabel(constraint->Label())
  49 {
  50         SummandList* orgSummands = constraint->LeftSide();
  51         for (int32 i = 0; i < orgSummands->CountItems(); i++) {
  52                 Summand* summand = orgSummands->ItemAt(i);
  53                 fLeftSide->AddItem(new Summand(summand));
  54         }
  55 }
  56
  57
  58 /**
  59  * Gets the index of the constraint.
  60  *
  61  * @return the index of the constraint
  62  */
  63 int32
  64 Constraint::Index() const
  65 {
  66         if (fLS == NULL)
  67                 return -1;
  68         int32 i = fLS->Constraints().IndexOf(this);
  69         if (i == -1)
  70                 STRACE(("Constraint not part of fLS->Constraints()."));
  71
  72         return i;
  73 }
  74
  75
  76 /**
  77  * Gets the left side of the constraint.
  78  *
  79  * @return pointer to a BList containing the summands on the left side of the constraint
  80  */
  81 SummandList*
  82 Constraint::LeftSide()
  83 {
  84         return fLeftSide;
  85 }
  86
  87
  88 /**
  89  * Sets the summands on the left side of the constraint.
  90  * The old summands are NOT deleted.
  91  *
  92  * @param summands      a BList containing the Summand objects that make up the new left side
  93  */
  94 bool
  95 Constraint::SetLeftSide(SummandList* summands, bool deleteOldSummands)
  96 {
  97         if (summands == NULL)
  98                 debugger("Invalid summands");
  99
 100         // check left side
 101         for (int32 i = 0; i < summands->CountItems(); i++) {
 102                 Summand* summand = summands->ItemAt(i);
 103                 for (int32 a = i + 1; a < summands->CountItems(); a++) {
 104                         Summand* nextSummand = summands->ItemAt(a);
 105                         if (summand->Var() == nextSummand->Var()) {
 106                                 summand->SetCoeff(summand->Coeff() + nextSummand->Coeff());
 107                                 summands->RemoveItem(nextSummand);
 108                                 delete nextSummand;
 109                                 a--;
 110                         }
 111                 }
 112         }
 113
 114         if (fLS == NULL) {
 115                 if (deleteOldSummands)
 116                         delete fLeftSide;
 117                 fLeftSide = summands;
 118                 return true;
 119         }
 120
 121         // notify the solver
 122         SummandList oldSummands;
 123         if (fLeftSide != NULL)
 124                 oldSummands = *fLeftSide;
 125         if (deleteOldSummands)
 126                 delete fLeftSide;
 127         fLeftSide = summands;
 128         if (fLS != NULL)
 129                 fLS->UpdateLeftSide(this, &oldSummands);
 130
 131         if (deleteOldSummands) {
 132                 for (int32 i = 0; i < oldSummands.CountItems(); i++)
 133                         delete oldSummands.ItemAt(i);
 134         }
 135         return true;
 136 }
 137
 138
 139 bool
 140 Constraint::SetLeftSide(double coeff1, Variable* var1)
 141 {
 142         SummandList* list = new SummandList;
 143         list->AddItem(new(std::nothrow) Summand(coeff1, var1));
 144         return SetLeftSide(list, true);
 145 }
 146
 147
 148 bool
 149 Constraint::SetLeftSide(double coeff1, Variable* var1,
 150         double coeff2, Variable* var2)
 151 {
 152         SummandList* list = new SummandList;
 153         list->AddItem(new(std::nothrow) Summand(coeff1, var1));
 154         list->AddItem(new(std::nothrow) Summand(coeff2, var2));
 155         return SetLeftSide(list, true);
 156 }
 157
 158
 159 bool
 160 Constraint::SetLeftSide(double coeff1, Variable* var1,
 161         double coeff2, Variable* var2,
 162         double coeff3, Variable* var3)
 163 {
 164         SummandList* list = new SummandList;
 165         list->AddItem(new(std::nothrow) Summand(coeff1, var1));
 166         list->AddItem(new(std::nothrow) Summand(coeff2, var2));
 167         list->AddItem(new(std::nothrow) Summand(coeff3, var3));
 168         return SetLeftSide(list, true);
 169 }
 170
 171
 172 bool
 173 Constraint::SetLeftSide(double coeff1, Variable* var1,
 174         double coeff2, Variable* var2,
 175         double coeff3, Variable* var3,
 176         double coeff4, Variable* var4)
 177 {
 178         SummandList* list = new SummandList;
 179         list->AddItem(new(std::nothrow) Summand(coeff1, var1));
 180         list->AddItem(new(std::nothrow) Summand(coeff2, var2));
 181         list->AddItem(new(std::nothrow) Summand(coeff3, var3));
 182         list->AddItem(new(std::nothrow) Summand(coeff4, var4));
 183         return SetLeftSide(list, true);
 184 }
 185
 186
 187 /**
 188  * Gets the operator used for this constraint.
 189  *
 190  * @return the operator used for this constraint
 191  */
 192 OperatorType
 193 Constraint::Op()
 194 {
 195         return fOp;
 196 }
 197
 198
 199 /**
 200  * Sets the operator used for this constraint.
 201  *
 202  * @param value operator
 203  */
 204 void
 205 Constraint::SetOp(OperatorType value)
 206 {
 207         fOp = value;
 208         if (fLS != NULL)
 209                 fLS->UpdateOperator(this);
 210 }
 211
 212
 213 /**
 214  * Gets the constant value that is on the right side of the operator.
 215  *
 216  * @return the constant value that is on the right side of the operator
 217  */
 218 double
 219 Constraint::RightSide() const
 220 {
 221         return fRightSide;
 222 }
 223
 224
 225 /**
 226  * Sets the constant value that is on the right side of the operator.
 227  *
 228  * @param value constant value that is on the right side of the operator
 229  */
 230 void
 231 Constraint::SetRightSide(double value)
 232 {
 233         if (fRightSide == value)
 234                 return;
 235
 236         fRightSide = value;
 237
 238         if (fLS != NULL)
 239                 fLS->UpdateRightSide(this);
 240 }
 241
 242
 243 /**
 244  * Gets the penalty coefficient for negative deviations.
 245  *
 246  * @return the penalty coefficient
 247  */
 248 double
 249 Constraint::PenaltyNeg() const
 250 {
 251         return fPenaltyNeg;
 252 }
 253
 254
 255 /**
 256  * The penalty coefficient for negative deviations from the soft constraint's exact solution,&nbsp;
 257  * i.e. if the left side is too large.
 258  *
 259  * @param value coefficient of negative penalty <code>double</code>
 260  */
 261 void
 262 Constraint::SetPenaltyNeg(double value)
 263 {
 264         fPenaltyNeg = value;
 265
 266         if (fLS != NULL)
 267                 fLS->UpdatePenalties(this);
 268 }
 269
 270
 271 /**
 272  * Gets the penalty coefficient for positive deviations.
 273  *
 274  * @return the penalty coefficient
 275  */
 276 double
 277 Constraint::PenaltyPos() const
 278 {
 279         return fPenaltyPos;
 280 }
 281
 282
 283 /**
 284  * The penalty coefficient for negative deviations from the soft constraint's
 285  * exact solution, i.e. if the left side is too small.
 286  * @param value coefficient of positive penalty <code>double</code>
 287  */
 288 void
 289 Constraint::SetPenaltyPos(double value)
 290 {
 291         fPenaltyPos = value;
 292
 293         if (fLS != NULL)
 294                 fLS->UpdatePenalties(this);
 295 }
 296
 297
 298 const char*
 299 Constraint::Label()
 300 {
 301         return fLabel.String();
 302 }
 303
 304
 305 void
 306 Constraint::SetLabel(const char* label)
 307 {
 308         fLabel = label;
 309 }
 310
 311
 312 bool
 313 Constraint::IsValid()
 314 {
 315         return fLS != NULL;
 316 }
 317
 318
 319 void
 320 Constraint::Invalidate()
 321 {
 322         STRACE(("Constraint::Invalidate() on %d\n", this));
 323
 324         if (fLS == NULL)
 325                 return;
 326
 327         fLS->RemoveConstraint(this, false);
 328         fLS = NULL;
 329 }
 330
 331
 332 BString
 333 Constraint::ToString() const
 334 {
 335         BString string;
 336         string << "Constraint ";
 337         string << fLabel;
 338         string << "(" << (addr_t)this << "): ";
 339
 340         for (int i = 0; i < fLeftSide->CountItems(); i++) {
 341                 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i));
 342                 if (i != 0 && s->Coeff() >= 0)
 343                         string << " + ";
 344                 string << (float)s->Coeff() << "*";
 345                 string << "x";
 346                 string << s->Var()->Index();
 347                 string << " ";
 348         }
 349         string << ((fOp == kEQ) ? "== "
 350                 : (fOp == kGE) ? ">= "
 351                 : (fOp == kLE) ? "<= "
 352                 : "?? ");
 353         string << (float)fRightSide;
 354         string << " PenaltyPos=" << (float)PenaltyPos();
 355         string << " PenaltyNeg=" << (float)PenaltyNeg();
 356
 357         return string;
 358 }
 359
 360
 361 void
 362 Constraint::PrintToStream()
 363 {
 364         BString string = ToString();
 365         printf("%s\n", string.String());
 366 }
 367
 368
 369 /**
 370  * Constructor.
 371  */
 372 Constraint::Constraint(LinearSpec* ls, SummandList* summands, OperatorType op,
 373         double rightSide, double penaltyNeg, double penaltyPos)
 374         :
 375         fLS(ls),
 376         fLeftSide(NULL),
 377         fOp(op),
 378         fRightSide(rightSide),
 379         fPenaltyNeg(penaltyNeg),
 380         fPenaltyPos(penaltyPos)
 381 {
 382         SetLeftSide(summands, false);
 383 }
 384
 385
 386 /**
 387  * Destructor.
 388  * Removes the constraint from its specification and deletes all the summands.
 389  */
 390 Constraint::~Constraint()
 391 {
 392         Invalidate();
 393
 394         for (int32 i = 0; i < fLeftSide->CountItems(); i++)
 395                 delete fLeftSide->ItemAt(i);
 396         delete fLeftSide;
 397         fLeftSide = NULL;
 398 }
 399