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 fRightSide = value; 231 if (!set_rh(fLS->fLP, Index(), fRightSide)) 232 STRACE(("Error in set_rh.")); 233 234 fLS->RemovePresolved(); 235 } 236 237 238 /** 239 * Gets the penalty coefficient for negative deviations. 240 * 241 * @return the penalty coefficient 242 */ 243 double 244 Constraint::PenaltyNeg() const 245 { 246 if (fDNegObjSummand == NULL) 247 return INFINITY; 248 return fDNegObjSummand->Coeff(); 249 } 250 251 252 /** 253 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 254 * i.e. if the left side is too large. 255 * 256 * @param value coefficient of negative penalty <code>double</code> 257 */ 258 void 259 Constraint::SetPenaltyNeg(double value) 260 { 261 if (!fIsValid) 262 return; 263 264 if (fDNegObjSummand == NULL) { 265 fDNegObjSummand = new Summand(value, new Variable(fLS)); 266 fLS->ObjFunction()->AddItem(fDNegObjSummand); 267 UpdateLeftSide(); 268 fLS->UpdateObjFunction(); 269 return; 270 } 271 272 if (value == fDNegObjSummand->Coeff()) 273 return; 274 275 fDNegObjSummand->SetCoeff(value); 276 fLS->UpdateObjFunction(); 277 } 278 279 280 /** 281 * Gets the penalty coefficient for positive deviations. 282 * 283 * @return the penalty coefficient 284 */ 285 double 286 Constraint::PenaltyPos() const 287 { 288 if (fDPosObjSummand == NULL) 289 return INFINITY; 290 return fDPosObjSummand->Coeff(); 291 } 292 293 294 /** 295 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 296 * i.e. if the left side is too small. 297 * 298 * @param value coefficient of positive penalty <code>double</code> 299 */ 300 void 301 Constraint::SetPenaltyPos(double value) 302 { 303 if (!fIsValid) 304 return; 305 306 if (fDPosObjSummand == NULL) { 307 fDPosObjSummand = new Summand(value, new Variable(fLS)); 308 fLS->ObjFunction()->AddItem(fDPosObjSummand); 309 UpdateLeftSide(); 310 fLS->UpdateObjFunction(); 311 return; 312 } 313 314 if (value == fDPosObjSummand->Coeff()) 315 return; 316 317 fDPosObjSummand->SetCoeff(value); 318 fLS->UpdateObjFunction(); 319 } 320 321 322 const char* 323 Constraint::Label() 324 { 325 return fLabel; 326 } 327 328 329 void 330 Constraint::SetLabel(const char* label) 331 { 332 fLabel = (char*) malloc(strlen(label) + 1); 333 strcpy(fLabel, label); 334 } 335 336 337 void 338 Constraint::WriteXML(BFile* file) 339 { 340 if (file->IsWritable() && fOwner == NULL) { 341 char buffer[200]; 342 343 file->Write(buffer, sprintf(buffer, "\t<constraint>\n")); 344 file->Write(buffer, sprintf(buffer, "\t\t<leftside>\n")); 345 346 Summand* summand; 347 for (int32 i = 0; i < fLeftSide->CountItems(); i++) { 348 summand = (Summand*)fLeftSide->ItemAt(i); 349 file->Write(buffer, sprintf(buffer, "\t\t\t<summand>\n")); 350 file->Write(buffer, sprintf(buffer, "\t\t\t\t<coeff>%f</coeff>\n", 351 summand->Coeff())); 352 BString varStr = *(summand->Var()); 353 file->Write(buffer, sprintf(buffer, "\t\t\t\t<var>%s</var>\n", 354 varStr.String())); 355 file->Write(buffer, sprintf(buffer, "\t\t\t</summand>\n")); 356 } 357 358 file->Write(buffer, sprintf(buffer, "\t\t</leftside>\n")); 359 360 const char* op = "??"; 361 if (fOp == OperatorType(EQ)) 362 op = "EQ"; 363 else if (fOp == OperatorType(LE)) 364 op = "LE"; 365 else if (fOp == OperatorType(GE)) 366 op = "GE"; 367 368 file->Write(buffer, sprintf(buffer, "\t\t<op>%s</op>\n", op)); 369 file->Write(buffer, sprintf(buffer, "\t\t<rightside>%f</rightside>\n", fRightSide)); 370 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltyneg>%s</penaltyneg>\n", PenaltyNeg())); 371 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltypos>%s</penaltypos>\n", PenaltyPos())); 372 file->Write(buffer, sprintf(buffer, "\t</constraint>\n")); 373 } 374 } 375 376 377 /** 378 * Gets the slack variable for the negative variations. 379 * 380 * @return the slack variable for the negative variations 381 */ 382 Variable* 383 Constraint::DNeg() const 384 { 385 if (fDNegObjSummand == NULL) 386 return NULL; 387 return fDNegObjSummand->Var(); 388 } 389 390 391 /** 392 * Gets the slack variable for the positive variations. 393 * 394 * @return the slack variable for the positive variations 395 */ 396 Variable* 397 Constraint::DPos() const 398 { 399 if (fDPosObjSummand == NULL) 400 return NULL; 401 return fDPosObjSummand->Var(); 402 } 403 404 405 void 406 Constraint::SetOwner(void* owner) 407 { 408 fOwner = owner; 409 } 410 411 412 void* 413 Constraint::Owner() const 414 { 415 return fOwner; 416 } 417 418 419 bool 420 Constraint::IsValid() 421 { 422 return fIsValid; 423 } 424 425 426 void 427 Constraint::Invalidate() 428 { 429 STRACE(("Constraint::Invalidate() on %d\n", this)); 430 431 if (!fIsValid) 432 return; 433 434 fIsValid = false; 435 436 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 437 delete (Summand*)fLeftSide->ItemAt(i); 438 delete fLeftSide; 439 fLeftSide = NULL; 440 441 if (fDNegObjSummand) { 442 fLS->ObjFunction()->RemoveItem(fDNegObjSummand); 443 delete fDNegObjSummand->Var(); 444 delete fDNegObjSummand; 445 fDNegObjSummand = NULL; 446 } 447 if (fDPosObjSummand) { 448 fLS->ObjFunction()->RemoveItem(fDPosObjSummand); 449 delete fDPosObjSummand->Var(); 450 delete fDPosObjSummand; 451 fDPosObjSummand = NULL; 452 } 453 454 del_constraint(fLS->fLP, this->Index()); 455 fLS->Constraints()->RemoveItem(this); 456 } 457 458 459 Constraint::operator BString() const 460 { 461 BString string; 462 GetString(string); 463 return string; 464 } 465 466 467 void 468 Constraint::GetString(BString& string) const 469 { 470 string << "Constraint "; 471 if (fLabel) 472 string << fLabel; 473 string << "(" << (int32)this << "): "; 474 475 if (fIsValid) { 476 for (int i = 0; i < fLeftSide->CountItems(); i++) { 477 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 478 string << (float)s->Coeff() << "*"; 479 s->Var()->GetString(string); 480 string << " "; 481 } 482 string << ((fOp == OperatorType(EQ)) ? "== " 483 : (fOp == OperatorType(GE)) ? ">= " 484 : (fOp == OperatorType(LE)) ? "<= " 485 : "?? "); 486 string << (float)fRightSide; 487 string << " PenaltyPos=" << (float)PenaltyPos(); 488 string << " PenaltyNeg=" << (float)PenaltyNeg(); 489 } else 490 string << "invalid"; 491 } 492 493 494 /** 495 * Constructor. 496 */ 497 Constraint::Constraint(LinearSpec* ls, BList* summands, OperatorType op, 498 double rightSide, double penaltyNeg, double penaltyPos) 499 : fLS(ls), 500 fLeftSide(summands), 501 fOp(op), 502 fRightSide(rightSide), 503 fOwner(NULL), 504 fLabel(NULL), 505 fIsValid(true) 506 { 507 double coeffs[summands->CountItems() + 2]; 508 int varIndexes[summands->CountItems() + 2]; 509 int32 i; 510 for (i = 0; i < summands->CountItems(); i++) { 511 Summand* s = (Summand*)summands->ItemAt(i); 512 coeffs[i] = s->Coeff(); 513 varIndexes[i] = s->Var()->Index(); 514 } 515 516 if (penaltyNeg != INFINITY 517 && fOp != OperatorType(LE)) { 518 fDNegObjSummand = new Summand(penaltyNeg, new Variable(fLS)); 519 fLS->fObjFunction->AddItem(fDNegObjSummand); 520 varIndexes[i] = fDNegObjSummand->Var()->Index(); 521 coeffs[i] = 1.0; 522 i++; 523 } 524 else 525 fDNegObjSummand = NULL; 526 527 if (penaltyPos != INFINITY 528 && fOp != OperatorType(GE)) { 529 fDPosObjSummand = new Summand(penaltyPos, new Variable(fLS)); 530 fLS->fObjFunction->AddItem(fDPosObjSummand); 531 varIndexes[i] = fDPosObjSummand->Var()->Index(); 532 coeffs[i] = -1.0; 533 i++; 534 } 535 else 536 fDPosObjSummand = NULL; 537 538 if (!add_constraintex(fLS->fLP, i, &coeffs[0], &varIndexes[0], 539 ((fOp == OperatorType(EQ)) ? EQ 540 : (fOp == OperatorType(GE)) ? GE 541 : LE), rightSide)) 542 STRACE(("Error in add_constraintex.")); 543 544 fLS->UpdateObjFunction(); 545 fLS->Constraints()->AddItem(this); 546 } 547 548 549 /** 550 * Destructor. 551 * Removes the constraint from its specification and deletes all the summands. 552 */ 553 Constraint::~Constraint() 554 { 555 Invalidate(); 556 } 557 558