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