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