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