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 13 #include "LinearSpec.h" 14 #include "Variable.h" 15 16 17 // Toggle debug output 18 //#define DEBUG_CONSTRAINT 19 20 #ifdef DEBUG_CONSTRAINT 21 # define STRACE(x) debug_printf x 22 #else 23 # define STRACE(x) ; 24 #endif 25 26 27 /** 28 * Gets the index of the constraint. 29 * 30 * @return the index of the constraint 31 */ 32 int32 33 Constraint::Index() const 34 { 35 int32 i = fLS->Constraints().IndexOf(this); 36 if (i == -1) { 37 STRACE(("Constraint not part of fLS->Constraints().")); 38 return -1; 39 } 40 return i + 1; 41 } 42 43 44 /** 45 * Gets the left side of the constraint. 46 * 47 * @return pointer to a BList containing the summands on the left side of the constraint 48 */ 49 SummandList* 50 Constraint::LeftSide() 51 { 52 return fLeftSide; 53 } 54 55 56 /** 57 * Sets the summands on the left side of the constraint. 58 * The old summands are NOT deleted. 59 * 60 * @param summands a BList containing the Summand objects that make up the new left side 61 */ 62 void 63 Constraint::SetLeftSide(SummandList* summands) 64 { 65 if (!fIsValid) 66 return; 67 68 fLeftSide = summands; 69 UpdateLeftSide(); 70 } 71 72 73 void 74 Constraint::UpdateLeftSide() 75 { 76 if (!fIsValid) 77 return; 78 79 double coeffs[fLeftSide->CountItems() + 2]; 80 int varIndexes[fLeftSide->CountItems() + 2]; 81 int32 i; 82 for (i = 0; i < fLeftSide->CountItems(); i++) { 83 Summand* s = fLeftSide->ItemAt(i); 84 coeffs[i] = s->Coeff(); 85 varIndexes[i] = s->Var()->Index(); 86 } 87 88 if (fDNegObjSummand != NULL && fOp != OperatorType(LE)) { 89 varIndexes[i] = fDNegObjSummand->Var()->Index(); 90 coeffs[i] = 1.0; 91 i++; 92 } 93 94 if (fDPosObjSummand != NULL && fOp != OperatorType(GE)) { 95 varIndexes[i] = fDPosObjSummand->Var()->Index(); 96 coeffs[i] = -1.0; 97 i++; 98 } 99 100 if (!set_rowex(fLS->fLP, this->Index(), i, &coeffs[0], &varIndexes[0])) 101 STRACE(("Error in set_rowex.")); 102 103 fLS->UpdateObjectiveFunction(); 104 fLS->RemovePresolved(); 105 } 106 107 108 void 109 Constraint::SetLeftSide(double coeff1, Variable* var1) 110 { 111 if (!fIsValid) 112 return; 113 114 for (int i=0; i<fLeftSide->CountItems(); i++) 115 delete fLeftSide->ItemAt(i); 116 fLeftSide->MakeEmpty(); 117 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 118 UpdateLeftSide(); 119 } 120 121 122 void 123 Constraint::SetLeftSide(double coeff1, Variable* var1, 124 double coeff2, Variable* var2) 125 { 126 if (!fIsValid) 127 return; 128 129 for (int i=0; i<fLeftSide->CountItems(); i++) 130 delete fLeftSide->ItemAt(i); 131 fLeftSide->MakeEmpty(); 132 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 133 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 134 UpdateLeftSide(); 135 } 136 137 138 void 139 Constraint::SetLeftSide(double coeff1, Variable* var1, 140 double coeff2, Variable* var2, 141 double coeff3, Variable* var3) 142 { 143 if (!fIsValid) 144 return; 145 146 for (int i=0; i<fLeftSide->CountItems(); i++) 147 delete fLeftSide->ItemAt(i); 148 fLeftSide->MakeEmpty(); 149 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 150 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 151 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 152 UpdateLeftSide(); 153 } 154 155 156 void 157 Constraint::SetLeftSide(double coeff1, Variable* var1, 158 double coeff2, Variable* var2, 159 double coeff3, Variable* var3, 160 double coeff4, Variable* var4) 161 { 162 if (!fIsValid) 163 return; 164 165 for (int i=0; i<fLeftSide->CountItems(); i++) 166 delete fLeftSide->ItemAt(i); 167 fLeftSide->MakeEmpty(); 168 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 169 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 170 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 171 fLeftSide->AddItem(new(std::nothrow) Summand(coeff4, var4)); 172 UpdateLeftSide(); 173 } 174 175 176 /** 177 * Gets the operator used for this constraint. 178 * 179 * @return the operator used for this constraint 180 */ 181 OperatorType 182 Constraint::Op() 183 { 184 return fOp; 185 } 186 187 188 /** 189 * Sets the operator used for this constraint. 190 * 191 * @param value operator 192 */ 193 void 194 Constraint::SetOp(OperatorType value) 195 { 196 if (!fIsValid) 197 return; 198 199 fOp = value; 200 if (!set_constr_type(fLS->fLP, this->Index(), 201 ((fOp == OperatorType(EQ)) ? EQ 202 : (fOp == OperatorType(GE)) ? GE 203 : LE))) 204 STRACE(("Error in set_constr_type.")); 205 206 fLS->RemovePresolved(); 207 } 208 209 210 /** 211 * Gets the constant value that is on the right side of the operator. 212 * 213 * @return the constant value that is on the right side of the operator 214 */ 215 double 216 Constraint::RightSide() const 217 { 218 return fRightSide; 219 } 220 221 222 /** 223 * Sets the constant value that is on the right side of the operator. 224 * 225 * @param value constant value that is on the right side of the operator 226 */ 227 void 228 Constraint::SetRightSide(double value) 229 { 230 if (!fIsValid) 231 return; 232 233 if (fRightSide == value) 234 return; 235 236 fRightSide = value; 237 if (!set_rh(fLS->fLP, Index(), fRightSide)) 238 STRACE(("Error in set_rh.")); 239 240 fLS->RemovePresolved(); 241 } 242 243 244 /** 245 * Gets the penalty coefficient for negative deviations. 246 * 247 * @return the penalty coefficient 248 */ 249 double 250 Constraint::PenaltyNeg() const 251 { 252 if (fDNegObjSummand == NULL) 253 return INFINITY; 254 return fDNegObjSummand->Coeff(); 255 } 256 257 258 /** 259 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 260 * i.e. if the left side is too large. 261 * 262 * @param value coefficient of negative penalty <code>double</code> 263 */ 264 void 265 Constraint::SetPenaltyNeg(double value) 266 { 267 if (!fIsValid) 268 return; 269 270 if (fDNegObjSummand == NULL) { 271 fDNegObjSummand = new(std::nothrow) Summand(value, fLS->AddVariable()); 272 fLS->ObjectiveFunction()->AddItem(fDNegObjSummand); 273 UpdateLeftSide(); 274 fLS->UpdateObjectiveFunction(); 275 return; 276 } 277 278 if (value == fDNegObjSummand->Coeff()) 279 return; 280 281 fDNegObjSummand->SetCoeff(value); 282 fLS->UpdateObjectiveFunction(); 283 } 284 285 286 /** 287 * Gets the penalty coefficient for positive deviations. 288 * 289 * @return the penalty coefficient 290 */ 291 double 292 Constraint::PenaltyPos() const 293 { 294 if (fDPosObjSummand == NULL) 295 return INFINITY; 296 return fDPosObjSummand->Coeff(); 297 } 298 299 300 /** 301 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 302 * i.e. if the left side is too small. 303 * 304 * @param value coefficient of positive penalty <code>double</code> 305 */ 306 void 307 Constraint::SetPenaltyPos(double value) 308 { 309 if (!fIsValid) 310 return; 311 312 if (fDPosObjSummand == NULL) { 313 fDPosObjSummand = new(std::nothrow) Summand(value, fLS->AddVariable()); 314 fLS->ObjectiveFunction()->AddItem(fDPosObjSummand); 315 UpdateLeftSide(); 316 fLS->UpdateObjectiveFunction(); 317 return; 318 } 319 320 if (value == fDPosObjSummand->Coeff()) 321 return; 322 323 fDPosObjSummand->SetCoeff(value); 324 fLS->UpdateObjectiveFunction(); 325 } 326 327 328 const char* 329 Constraint::Label() 330 { 331 return fLabel.String(); 332 } 333 334 335 void 336 Constraint::SetLabel(const char* label) 337 { 338 fLabel = label; 339 } 340 341 342 void 343 Constraint::WriteXML(BFile* file) 344 { 345 if (!file->IsWritable()) 346 return; 347 348 char buffer[200]; 349 350 file->Write(buffer, sprintf(buffer, "\t<constraint>\n")); 351 file->Write(buffer, sprintf(buffer, "\t\t<leftside>\n")); 352 353 Summand* summand; 354 for (int32 i = 0; i < fLeftSide->CountItems(); i++) { 355 summand = (Summand*)fLeftSide->ItemAt(i); 356 file->Write(buffer, sprintf(buffer, "\t\t\t<summand>\n")); 357 file->Write(buffer, sprintf(buffer, "\t\t\t\t<coeff>%f</coeff>\n", 358 summand->Coeff())); 359 BString varStr = *(summand->Var()); 360 file->Write(buffer, sprintf(buffer, "\t\t\t\t<var>%s</var>\n", 361 varStr.String())); 362 file->Write(buffer, sprintf(buffer, "\t\t\t</summand>\n")); 363 } 364 365 file->Write(buffer, sprintf(buffer, "\t\t</leftside>\n")); 366 367 const char* op = "??"; 368 if (fOp == OperatorType(EQ)) 369 op = "EQ"; 370 else if (fOp == OperatorType(LE)) 371 op = "LE"; 372 else if (fOp == OperatorType(GE)) 373 op = "GE"; 374 375 file->Write(buffer, sprintf(buffer, "\t\t<op>%s</op>\n", op)); 376 file->Write(buffer, sprintf(buffer, "\t\t<rightside>%f</rightside>\n", fRightSide)); 377 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltyneg>%s</penaltyneg>\n", PenaltyNeg())); 378 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltypos>%s</penaltypos>\n", PenaltyPos())); 379 file->Write(buffer, sprintf(buffer, "\t</constraint>\n")); 380 } 381 382 383 /** 384 * Gets the slack variable for the negative variations. 385 * 386 * @return the slack variable for the negative variations 387 */ 388 Variable* 389 Constraint::DNeg() const 390 { 391 if (fDNegObjSummand == NULL) 392 return NULL; 393 return fDNegObjSummand->Var(); 394 } 395 396 397 /** 398 * Gets the slack variable for the positive variations. 399 * 400 * @return the slack variable for the positive variations 401 */ 402 Variable* 403 Constraint::DPos() const 404 { 405 if (fDPosObjSummand == NULL) 406 return NULL; 407 return fDPosObjSummand->Var(); 408 } 409 410 411 bool 412 Constraint::IsValid() 413 { 414 return fIsValid; 415 } 416 417 418 void 419 Constraint::Invalidate() 420 { 421 STRACE(("Constraint::Invalidate() on %d\n", this)); 422 423 if (!fIsValid) 424 return; 425 426 fIsValid = false; 427 428 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 429 delete (Summand*)fLeftSide->ItemAt(i); 430 delete fLeftSide; 431 fLeftSide = NULL; 432 433 if (fDNegObjSummand) { 434 fLS->ObjectiveFunction()->RemoveItem(fDNegObjSummand); 435 delete fDNegObjSummand->Var(); 436 delete fDNegObjSummand; 437 fDNegObjSummand = NULL; 438 } 439 if (fDPosObjSummand) { 440 fLS->ObjectiveFunction()->RemoveItem(fDPosObjSummand); 441 delete fDPosObjSummand->Var(); 442 delete fDPosObjSummand; 443 fDPosObjSummand = NULL; 444 } 445 446 del_constraint(fLS->fLP, this->Index()); 447 const_cast<ConstraintList&>(fLS->Constraints()).RemoveItem(this); 448 } 449 450 451 Constraint::operator BString() const 452 { 453 BString string; 454 GetString(string); 455 return string; 456 } 457 458 459 void 460 Constraint::GetString(BString& string) const 461 { 462 string << "Constraint "; 463 string << fLabel; 464 string << "(" << (int32)this << "): "; 465 466 if (fIsValid) { 467 for (int i = 0; i < fLeftSide->CountItems(); i++) { 468 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 469 string << (float)s->Coeff() << "*"; 470 s->Var()->GetString(string); 471 string << " "; 472 } 473 string << ((fOp == OperatorType(EQ)) ? "== " 474 : (fOp == OperatorType(GE)) ? ">= " 475 : (fOp == OperatorType(LE)) ? "<= " 476 : "?? "); 477 string << (float)fRightSide; 478 string << " PenaltyPos=" << (float)PenaltyPos(); 479 string << " PenaltyNeg=" << (float)PenaltyNeg(); 480 } else 481 string << "invalid"; 482 } 483 484 485 /** 486 * Constructor. 487 */ 488 Constraint::Constraint(LinearSpec* ls, SummandList* summands, OperatorType op, 489 double rightSide, double penaltyNeg, double penaltyPos) 490 : 491 fLS(ls), 492 fLeftSide(summands), 493 fOp(op), 494 fRightSide(rightSide), 495 fIsValid(true) 496 { 497 double coeffs[summands->CountItems() + 2]; 498 int varIndexes[summands->CountItems() + 2]; 499 int32 nCoefficient = 0; 500 for (; nCoefficient < summands->CountItems(); nCoefficient++) { 501 Summand* s = summands->ItemAt(nCoefficient); 502 coeffs[nCoefficient] = s->Coeff(); 503 varIndexes[nCoefficient] = s->Var()->Index(); 504 } 505 506 if (penaltyNeg != INFINITY && penaltyNeg != 0. && fOp != OperatorType(LE)) { 507 fDNegObjSummand = new(std::nothrow) Summand(penaltyNeg, 508 ls->AddVariable()); 509 fLS->fObjFunction->AddItem(fDNegObjSummand); 510 varIndexes[nCoefficient] = fDNegObjSummand->Var()->Index(); 511 coeffs[nCoefficient] = 1.0; 512 nCoefficient++; 513 } 514 else 515 fDNegObjSummand = NULL; 516 517 if (penaltyPos != INFINITY && penaltyPos != 0. && fOp != OperatorType(GE)) { 518 fDPosObjSummand = new(std::nothrow) Summand(penaltyPos, 519 ls->AddVariable()); 520 fLS->fObjFunction->AddItem(fDPosObjSummand); 521 varIndexes[nCoefficient] = fDPosObjSummand->Var()->Index(); 522 coeffs[nCoefficient] = -1.0; 523 nCoefficient++; 524 } 525 else 526 fDPosObjSummand = NULL; 527 528 if (!add_constraintex(fLS->fLP, nCoefficient, &coeffs[0], &varIndexes[0], 529 (fOp == OperatorType(EQ) ? EQ : (fOp == OperatorType(GE)) ? GE 530 : LE), rightSide)) 531 STRACE(("Error in add_constraintex.")); 532 533 fLS->UpdateObjectiveFunction(); 534 const_cast<ConstraintList&>(fLS->Constraints()).AddItem(this); 535 } 536 537 538 /** 539 * Destructor. 540 * Removes the constraint from its specification and deletes all the summands. 541 */ 542 Constraint::~Constraint() 543 { 544 Invalidate(); 545 } 546 547