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 "LinearSpec.h" 10 11 #include <new> 12 #include <stdio.h> 13 14 #include "ActiveSetSolver.h" 15 16 17 using namespace LinearProgramming; 18 19 20 // #define DEBUG_LINEAR_SPECIFICATIONS 21 22 #ifdef DEBUG_LINEAR_SPECIFICATIONS 23 #include <stdio.h> 24 #define TRACE(x...) printf(x) 25 #else 26 #define TRACE(x...) /* nothing */ 27 #endif 28 29 30 SolverInterface::SolverInterface(LinearSpec* linSpec) 31 : 32 fLinearSpec(linSpec) 33 { 34 35 } 36 37 38 /** 39 * Constructor. 40 * Creates a new specification for a linear programming problem. 41 */ 42 LinearSpec::LinearSpec() 43 : 44 fResult(kError), 45 fSolvingTime(0) 46 { 47 fSolver = new ActiveSetSolver(this); 48 } 49 50 51 /** 52 * Destructor. 53 * Removes the specification and deletes all constraints, 54 * objective function summands and variables. 55 */ 56 LinearSpec::~LinearSpec() 57 { 58 for (int32 i = 0; i < fConstraints.CountItems(); i++) 59 delete (Constraint*)fConstraints.ItemAt(i); 60 while (fVariables.CountItems() > 0) 61 RemoveVariable(fVariables.ItemAt(0)); 62 63 delete fSolver; 64 } 65 66 67 /** 68 * Adds a new variable to the specification. 69 * 70 * @return the new variable 71 */ 72 Variable* 73 LinearSpec::AddVariable() 74 { 75 Variable* variable = new(std::nothrow) Variable(this); 76 if (!variable) 77 return NULL; 78 if (!AddVariable(variable)) { 79 delete variable; 80 return NULL; 81 } 82 83 return variable; 84 } 85 86 87 bool 88 LinearSpec::AddVariable(Variable* variable) 89 { 90 if (variable->IsValid()) 91 return false; 92 93 if (!fVariables.AddItem(variable)) 94 return false; 95 96 if (!fSolver->VariableAdded(variable)) { 97 fVariables.RemoveItem(variable); 98 return false; 99 } 100 variable->fIsValid = true; 101 102 if (!UpdateRange(variable)) { 103 RemoveVariable(variable, false); 104 return false; 105 } 106 return true; 107 } 108 109 110 bool 111 LinearSpec::RemoveVariable(Variable* variable, bool deleteVariable) 112 { 113 // must be called first otherwise the index is invalid 114 if (fSolver->VariableRemoved(variable) == false) 115 return false; 116 117 // do we know the variable? 118 if (fVariables.RemoveItem(variable) == false) 119 return false; 120 fUsedVariables.RemoveItem(variable); 121 122 variable->fIsValid = false; 123 124 // invalidate all constraints that use this variable 125 ConstraintList markedForInvalidation; 126 const ConstraintList& constraints = Constraints(); 127 for (int i = 0; i < constraints.CountItems(); i++) { 128 Constraint* constraint = constraints.ItemAt(i); 129 130 if (!constraint->IsValid()) 131 continue; 132 133 SummandList* summands = constraint->LeftSide(); 134 for (int j = 0; j < summands->CountItems(); j++) { 135 Summand* summand = summands->ItemAt(j); 136 if (summand->Var() == variable) { 137 markedForInvalidation.AddItem(constraint); 138 break; 139 } 140 } 141 } 142 for (int i = 0; i < markedForInvalidation.CountItems(); i++) 143 RemoveConstraint(markedForInvalidation.ItemAt(i)); 144 145 146 if (deleteVariable) 147 delete variable; 148 return true; 149 } 150 151 152 int32 153 LinearSpec::IndexOf(const Variable* variable) const 154 { 155 return fUsedVariables.IndexOf(variable); 156 } 157 158 159 int32 160 LinearSpec::GlobalIndexOf(const Variable* variable) const 161 { 162 return fVariables.IndexOf(variable); 163 } 164 165 166 bool 167 LinearSpec::UpdateRange(Variable* variable) 168 { 169 if (!fSolver->VariableRangeChanged(variable)) 170 return false; 171 return true; 172 } 173 174 175 bool 176 LinearSpec::AddConstraint(Constraint* constraint) 177 { 178 if (!fConstraints.AddItem(constraint)) 179 return false; 180 181 // ref count the used variables 182 SummandList* leftSide = constraint->LeftSide(); 183 for (int i = 0; i < leftSide->CountItems(); i++) { 184 Variable* var = leftSide->ItemAt(i)->Var(); 185 if (var->AddReference() == 1) 186 fUsedVariables.AddItem(var); 187 } 188 189 if (!fSolver->ConstraintAdded(constraint)) { 190 RemoveConstraint(constraint, false); 191 return false; 192 } 193 194 constraint->fIsValid = true; 195 return true; 196 } 197 198 199 bool 200 LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint) 201 { 202 fSolver->ConstraintRemoved(constraint); 203 fConstraints.RemoveItem(constraint); 204 constraint->fIsValid = false; 205 206 SummandList* leftSide = constraint->LeftSide(); 207 for (int i = 0; i < leftSide->CountItems(); i++) { 208 Variable* var = leftSide->ItemAt(i)->Var(); 209 if (var->RemoveReference() == 0) 210 fUsedVariables.RemoveItem(var); 211 } 212 213 if (deleteConstraint) 214 delete constraint; 215 return true; 216 } 217 218 219 bool 220 LinearSpec::UpdateLeftSide(Constraint* constraint) 221 { 222 if (!fSolver->LeftSideChanged(constraint)) 223 return false; 224 return true; 225 } 226 227 228 bool 229 LinearSpec::UpdateRightSide(Constraint* constraint) 230 { 231 if (!fSolver->RightSideChanged(constraint)) 232 return false; 233 return true; 234 } 235 236 237 bool 238 LinearSpec::UpdateOperator(Constraint* constraint) 239 { 240 if (!fSolver->OperatorChanged(constraint)) 241 return false; 242 return true; 243 } 244 245 246 /** 247 * Adds a new hard linear constraint to the specification. 248 * 249 * @param coeffs the constraint's coefficients 250 * @param vars the constraint's variables 251 * @param op the constraint's operand 252 * @param rightSide the constant value on the constraint's right side 253 * @return the new constraint 254 */ 255 Constraint* 256 LinearSpec::AddConstraint(SummandList* summands, OperatorType op, 257 double rightSide) 258 { 259 return AddConstraint(summands, op, rightSide, -1, -1); 260 } 261 262 263 /** 264 * Adds a new hard linear constraint to the specification with a single summand. 265 * 266 * @param coeff1 the constraint's first coefficient 267 * @param var1 the constraint's first variable 268 * @param op the constraint's operand 269 * @param rightSide the constant value on the constraint's right side 270 * @return the new constraint 271 */ 272 Constraint* 273 LinearSpec::AddConstraint(double coeff1, Variable* var1, 274 OperatorType op, double rightSide) 275 { 276 return AddConstraint(coeff1, var1, op, rightSide, -1, -1); 277 } 278 279 280 /** 281 * Adds a new hard linear constraint to the specification with two summands. 282 * 283 * @param coeff1 the constraint's first coefficient 284 * @param var1 the constraint's first variable 285 * @param coeff2 the constraint's second coefficient 286 * @param var2 the constraint's second variable 287 * @param op the constraint's operand 288 * @param rightSide the constant value on the constraint's right side 289 * @return the new constraint 290 */ 291 Constraint* 292 LinearSpec::AddConstraint(double coeff1, Variable* var1, 293 double coeff2, Variable* var2, OperatorType op, double rightSide) 294 { 295 return AddConstraint(coeff1, var1, coeff2, var2, op, rightSide, -1, 296 -1); 297 } 298 299 300 /** 301 * Adds a new hard linear constraint to the specification with three summands. 302 * 303 * @param coeff1 the constraint's first coefficient 304 * @param var1 the constraint's first variable 305 * @param coeff2 the constraint's second coefficient 306 * @param var2 the constraint's second variable 307 * @param coeff3 the constraint's third coefficient 308 * @param var3 the constraint's third variable 309 * @param op the constraint's operand 310 * @param rightSide the constant value on the constraint's right side 311 * @return the new constraint 312 */ 313 Constraint* 314 LinearSpec::AddConstraint(double coeff1, Variable* var1, 315 double coeff2, Variable* var2, double coeff3, Variable* var3, 316 OperatorType op, double rightSide) 317 { 318 return AddConstraint(coeff1, var1, coeff2, var2, coeff3, var3, op, 319 rightSide, -1, -1); 320 } 321 322 323 /** 324 * Adds a new hard linear constraint to the specification with four summands. 325 * 326 * @param coeff1 the constraint's first coefficient 327 * @param var1 the constraint's first variable 328 * @param coeff2 the constraint's second coefficient 329 * @param var2 the constraint's second variable 330 * @param coeff3 the constraint's third coefficient 331 * @param var3 the constraint's third variable 332 * @param coeff4 the constraint's fourth coefficient 333 * @param var4 the constraint's fourth variable 334 * @param op the constraint's operand 335 * @param rightSide the constant value on the constraint's right side 336 * @return the new constraint 337 */ 338 Constraint* 339 LinearSpec::AddConstraint(double coeff1, Variable* var1, 340 double coeff2, Variable* var2, double coeff3, Variable* var3, 341 double coeff4, Variable* var4, OperatorType op, double rightSide) 342 { 343 return AddConstraint(coeff1, var1, coeff2, var2, coeff3, var3, coeff4, var4, 344 op, rightSide, -1, -1); 345 } 346 347 348 /** 349 * Adds a new soft linear constraint to the specification. 350 * i.e. a constraint that does not always have to be satisfied. 351 * 352 * @param coeffs the constraint's coefficients 353 * @param vars the constraint's variables 354 * @param op the constraint's operand 355 * @param rightSide the constant value on the constraint's right side 356 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 357 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 358 */ 359 Constraint* 360 LinearSpec::AddConstraint(SummandList* summands, OperatorType op, 361 double rightSide, double penaltyNeg, double penaltyPos) 362 { 363 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 364 } 365 366 367 /** 368 * Adds a new soft linear constraint to the specification with a single summand. 369 * 370 * @param coeff1 the constraint's first coefficient 371 * @param var1 the constraint's first variable 372 * @param op the constraint's operand 373 * @param rightSide the constant value on the constraint's right side 374 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 375 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 376 */ 377 Constraint* 378 LinearSpec::AddConstraint(double coeff1, Variable* var1, 379 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 380 { 381 SummandList* summands = new(std::nothrow) SummandList(1); 382 if (!summands) 383 return NULL; 384 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 385 if (!_CheckSummandList(summands)) 386 return NULL; 387 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 388 } 389 390 391 /** 392 * Adds a new soft linear constraint to the specification with two summands. 393 * 394 * @param coeff1 the constraint's first coefficient 395 * @param var1 the constraint's first variable 396 * @param coeff2 the constraint's second coefficient 397 * @param var2 the constraint's second variable 398 * @param op the constraint's operand 399 * @param rightSide the constant value on the constraint's right side 400 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 401 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 402 */ 403 Constraint* 404 LinearSpec::AddConstraint(double coeff1, Variable* var1, 405 double coeff2, Variable* var2, OperatorType op, double rightSide, 406 double penaltyNeg, double penaltyPos) 407 { 408 SummandList* summands = new(std::nothrow) SummandList(2); 409 if (!summands) 410 return NULL; 411 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 412 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 413 if (!_CheckSummandList(summands)) 414 return NULL; 415 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 416 } 417 418 419 /** 420 * Adds a new soft linear constraint to the specification with three summands. 421 * 422 * @param coeff1 the constraint's first coefficient 423 * @param var1 the constraint's first variable 424 * @param coeff2 the constraint's second coefficient 425 * @param var2 the constraint's second variable 426 * @param coeff3 the constraint's third coefficient 427 * @param var3 the constraint's third variable 428 * @param op the constraint's operand 429 * @param rightSide the constant value on the constraint's right side 430 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 431 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 432 */ 433 Constraint* 434 LinearSpec::AddConstraint(double coeff1, Variable* var1, 435 double coeff2, Variable* var2, double coeff3, Variable* var3, 436 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 437 { 438 SummandList* summands = new(std::nothrow) SummandList(2); 439 if (!summands) 440 return NULL; 441 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 442 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 443 summands->AddItem(new(std::nothrow) Summand(coeff3, var3)); 444 if (!_CheckSummandList(summands)) 445 return NULL; 446 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 447 } 448 449 450 /** 451 * Adds a new soft linear constraint to the specification with four summands. 452 * 453 * @param coeff1 the constraint's first coefficient 454 * @param var1 the constraint's first variable 455 * @param coeff2 the constraint's second coefficient 456 * @param var2 the constraint's second variable 457 * @param coeff3 the constraint's third coefficient 458 * @param var3 the constraint's third variable 459 * @param coeff4 the constraint's fourth coefficient 460 * @param var4 the constraint's fourth variable 461 * @param op the constraint's operand 462 * @param rightSide the constant value on the constraint's right side 463 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 464 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 465 */ 466 Constraint* 467 LinearSpec::AddConstraint(double coeff1, Variable* var1, 468 double coeff2, Variable* var2, double coeff3, Variable* var3, 469 double coeff4, Variable* var4, OperatorType op, double rightSide, 470 double penaltyNeg, double penaltyPos) 471 { 472 SummandList* summands = new(std::nothrow) SummandList(2); 473 if (!summands) 474 return NULL; 475 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 476 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 477 summands->AddItem(new(std::nothrow) Summand(coeff3, var3)); 478 summands->AddItem(new(std::nothrow) Summand(coeff4, var4)); 479 if (!_CheckSummandList(summands)) 480 return NULL; 481 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 482 } 483 484 485 BSize 486 LinearSpec::MinSize(Variable* width, Variable* height) 487 { 488 return fSolver->MinSize(width, height); 489 } 490 491 492 BSize 493 LinearSpec::MaxSize(Variable* width, Variable* height) 494 { 495 return fSolver->MaxSize(width, height); 496 } 497 498 499 bool 500 LinearSpec::_CheckSummandList(SummandList* list) 501 { 502 bool ok = true; 503 for (int i = 0; i < list->CountItems(); i++) { 504 if (list->ItemAt(i) == NULL) { 505 ok = false; 506 break; 507 } 508 } 509 if (ok) 510 return true; 511 512 for (int i = 0; i < list->CountItems(); i++) 513 delete list->ItemAt(i); 514 delete list; 515 return false; 516 } 517 518 519 Constraint* 520 LinearSpec::_AddConstraint(SummandList* leftSide, OperatorType op, 521 double rightSide, double penaltyNeg, double penaltyPos) 522 { 523 Constraint* constraint = new(std::nothrow) Constraint(this, leftSide, 524 op, rightSide, penaltyNeg, penaltyPos); 525 if (constraint == NULL) 526 return NULL; 527 if (!AddConstraint(constraint)) { 528 delete constraint; 529 return NULL; 530 } 531 return constraint; 532 } 533 534 535 #ifdef DEBUG_LINEAR_SPECIFICATIONS 536 static bigtime_t sAverageSolvingTime = 0; 537 static int32 sSolvedCount = 0; 538 #endif 539 540 541 ResultType 542 LinearSpec::Solve() 543 { 544 bigtime_t startTime = system_time(); 545 546 fResult = fSolver->Solve(); 547 548 fSolvingTime = system_time() - startTime; 549 550 #ifdef DEBUG_LINEAR_SPECIFICATIONS 551 sAverageSolvingTime += fSolvingTime; 552 sSolvedCount++; 553 TRACE("Solving time %i average %i [micro s]\n", (int)fSolvingTime, 554 int(sAverageSolvingTime / sSolvedCount)); 555 #endif 556 557 return fResult; 558 } 559 560 561 /** 562 * Writes the specification into a text file. 563 * The file will be overwritten if it exists. 564 * 565 * @param fname the file name 566 */ 567 bool 568 LinearSpec::Save(const char* fileName) 569 { 570 return fSolver->SaveModel(fileName) == B_OK; 571 } 572 573 574 /** 575 * Gets the constraints. 576 * 577 * @return the constraints 578 */ 579 const ConstraintList& 580 LinearSpec::Constraints() const 581 { 582 return fConstraints; 583 } 584 585 586 const VariableList& 587 LinearSpec::UsedVariables() const 588 { 589 return fUsedVariables; 590 } 591 592 593 const VariableList& 594 LinearSpec::AllVariables() const 595 { 596 return fVariables; 597 } 598 599 600 /** 601 * Gets the result type. 602 * 603 * @return the result type 604 */ 605 ResultType 606 LinearSpec::Result() const 607 { 608 return fResult; 609 } 610 611 612 /** 613 * Gets the solving time. 614 * 615 * @return the solving time 616 */ 617 bigtime_t 618 LinearSpec::SolvingTime() const 619 { 620 return fSolvingTime; 621 } 622 623 624 BString 625 LinearSpec::ToString() const 626 { 627 BString string; 628 string << "LinearSpec " << (int32)this << ":\n"; 629 for (int i = 0; i < fVariables.CountItems(); i++) { 630 Variable* variable = fVariables.ItemAt(i); 631 string += variable->ToString(); 632 string << "=" << (float)variable->Value() << " "; 633 } 634 string << "\n"; 635 for (int i = 0; i < fConstraints.CountItems(); i++) { 636 Constraint* c = fConstraints.ItemAt(i); 637 string << i << ": "; 638 string += c->ToString(); 639 string << "\n"; 640 } 641 string << "Result="; 642 if (fResult == kError) 643 string << "kError"; 644 else if (fResult == kOptimal) 645 string << "kOptimal"; 646 else if (fResult == kSuboptimal) 647 string << "kSuboptimal"; 648 else if (fResult == kInfeasible) 649 string << "kInfeasible"; 650 else if (fResult == kUnbounded) 651 string << "kUnbounded"; 652 else if (fResult == kDegenerate) 653 string << "kDegenerate"; 654 else if (fResult == kNumFailure) 655 string << "kNumFailure"; 656 else 657 string << fResult; 658 string << " SolvingTime=" << fSolvingTime << "micro s"; 659 return string; 660 } 661 662