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