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 "LinearSpec.h" 8 9 10 /** 11 * Constructor. 12 * Creates a new specification for a linear programming problem. 13 */ 14 LinearSpec::LinearSpec() 15 : 16 fCountColumns(0), 17 fLpPresolved(NULL), 18 fOptimization(MINIMIZE), 19 fObjFunction(new SummandList()), 20 fResult(ERROR), 21 fObjectiveValue(NAN), 22 fSolvingTime(NAN) 23 { 24 fLP = make_lp(0, 0); 25 if (fLP == NULL) 26 printf("Couldn't construct a new model."); 27 set_verbose(fLP, 1); 28 } 29 30 31 /** 32 * Destructor. 33 * Removes the specification and deletes all constraints, 34 * objective function summands and variables. 35 */ 36 LinearSpec::~LinearSpec() 37 { 38 RemovePresolved(); 39 for (int32 i = 0; i < fConstraints.CountItems(); i++) 40 delete (Constraint*)fConstraints.ItemAt(i); 41 for (int32 i = 0; i < fObjFunction->CountItems(); i++) 42 delete (Summand*)fObjFunction->ItemAt(i); 43 for (int32 i = 0; i < fVariables.CountItems(); i++) 44 delete (Variable*)fVariables.ItemAt(i); 45 delete_lp(fLP); 46 47 delete fObjFunction; 48 } 49 50 51 /** 52 * Adds a new variable to the specification. 53 * 54 * @return the new variable 55 */ 56 Variable* 57 LinearSpec::AddVariable() 58 { 59 return new Variable(this); 60 } 61 62 63 /** 64 * Adds a new hard linear constraint to the specification. 65 * 66 * @param coeffs the constraint's coefficients 67 * @param vars the constraint's variables 68 * @param op the constraint's operand 69 * @param rightSide the constant value on the constraint's right side 70 * @return the new constraint 71 */ 72 Constraint* 73 LinearSpec::AddConstraint(SummandList* summands, OperatorType op, 74 double rightSide) 75 { 76 Constraint* c = new Constraint(this, summands, op, rightSide, 77 INFINITY, INFINITY); 78 RemovePresolved(); 79 return c; 80 } 81 82 83 /** 84 * Adds a new hard linear constraint to the specification with a single summand. 85 * 86 * @param coeff1 the constraint's first coefficient 87 * @param var1 the constraint's first variable 88 * @param op the constraint's operand 89 * @param rightSide the constant value on the constraint's right side 90 * @return the new constraint 91 */ 92 Constraint* 93 LinearSpec::AddConstraint(double coeff1, Variable* var1, 94 OperatorType op, double rightSide) 95 { 96 SummandList* summands = new SummandList(1); 97 summands->AddItem(new Summand(coeff1, var1)); 98 Constraint* c = new Constraint(this, summands, op, rightSide, 99 INFINITY, INFINITY); 100 RemovePresolved(); 101 return c; 102 } 103 104 105 /** 106 * Adds a new hard linear constraint to the specification with two summands. 107 * 108 * @param coeff1 the constraint's first coefficient 109 * @param var1 the constraint's first variable 110 * @param coeff2 the constraint's second coefficient 111 * @param var2 the constraint's second variable 112 * @param op the constraint's operand 113 * @param rightSide the constant value on the constraint's right side 114 * @return the new constraint 115 */ 116 Constraint* 117 LinearSpec::AddConstraint(double coeff1, Variable* var1, 118 double coeff2, Variable* var2, OperatorType op, double rightSide) 119 { 120 SummandList* summands = new SummandList(2); 121 summands->AddItem(new Summand(coeff1, var1)); 122 summands->AddItem(new Summand(coeff2, var2)); 123 Constraint* c = new Constraint(this, summands, op, rightSide, 124 INFINITY, INFINITY); 125 RemovePresolved(); 126 return c; 127 } 128 129 130 /** 131 * Adds a new hard linear constraint to the specification with three summands. 132 * 133 * @param coeff1 the constraint's first coefficient 134 * @param var1 the constraint's first variable 135 * @param coeff2 the constraint's second coefficient 136 * @param var2 the constraint's second variable 137 * @param coeff3 the constraint's third coefficient 138 * @param var3 the constraint's third variable 139 * @param op the constraint's operand 140 * @param rightSide the constant value on the constraint's right side 141 * @return the new constraint 142 */ 143 Constraint* 144 LinearSpec::AddConstraint(double coeff1, Variable* var1, 145 double coeff2, Variable* var2, double coeff3, Variable* var3, 146 OperatorType op, double rightSide) 147 { 148 SummandList* summands = new SummandList(3); 149 summands->AddItem(new Summand(coeff1, var1)); 150 summands->AddItem(new Summand(coeff2, var2)); 151 summands->AddItem(new Summand(coeff3, var3)); 152 Constraint* c = new Constraint(this, summands, op, rightSide, 153 INFINITY, INFINITY); 154 RemovePresolved(); 155 return c; 156 } 157 158 159 /** 160 * Adds a new hard linear constraint to the specification with four summands. 161 * 162 * @param coeff1 the constraint's first coefficient 163 * @param var1 the constraint's first variable 164 * @param coeff2 the constraint's second coefficient 165 * @param var2 the constraint's second variable 166 * @param coeff3 the constraint's third coefficient 167 * @param var3 the constraint's third variable 168 * @param coeff4 the constraint's fourth coefficient 169 * @param var4 the constraint's fourth variable 170 * @param op the constraint's operand 171 * @param rightSide the constant value on the constraint's right side 172 * @return the new constraint 173 */ 174 Constraint* 175 LinearSpec::AddConstraint(double coeff1, Variable* var1, 176 double coeff2, Variable* var2, double coeff3, Variable* var3, 177 double coeff4, Variable* var4, OperatorType op, double rightSide) 178 { 179 SummandList* summands = new SummandList(3); 180 summands->AddItem(new Summand(coeff1, var1)); 181 summands->AddItem(new Summand(coeff2, var2)); 182 summands->AddItem(new Summand(coeff3, var3)); 183 summands->AddItem(new Summand(coeff4, var4)); 184 Constraint* c = new Constraint(this, summands, op, rightSide, 185 INFINITY, INFINITY); 186 RemovePresolved(); 187 return c; 188 } 189 190 191 /** 192 * Adds a new soft linear constraint to the specification. 193 * i.e. a constraint that does not always have to be satisfied. 194 * 195 * @param coeffs the constraint's coefficients 196 * @param vars the constraint's variables 197 * @param op the constraint's operand 198 * @param rightSide the constant value on the constraint's right side 199 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 200 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 201 */ 202 Constraint* 203 LinearSpec::AddConstraint(SummandList* summands, OperatorType op, 204 double rightSide, double penaltyNeg, double penaltyPos) 205 { 206 Constraint* c = new Constraint(this, summands, op, rightSide, 207 penaltyNeg, penaltyPos); 208 RemovePresolved(); 209 return c; 210 } 211 212 213 /** 214 * Adds a new soft linear constraint to the specification with a single summand. 215 * 216 * @param coeff1 the constraint's first coefficient 217 * @param var1 the constraint's first variable 218 * @param op the constraint's operand 219 * @param rightSide the constant value on the constraint's right side 220 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 221 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 222 */ 223 Constraint* 224 LinearSpec::AddConstraint(double coeff1, Variable* var1, 225 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 226 { 227 SummandList* summands = new SummandList(1); 228 summands->AddItem(new Summand(coeff1, var1)); 229 Constraint* c = new Constraint(this, summands, op, rightSide, 230 penaltyNeg, penaltyPos); 231 RemovePresolved(); 232 return c; 233 } 234 235 236 /** 237 * Adds a new soft linear constraint to the specification with two summands. 238 * 239 * @param coeff1 the constraint's first coefficient 240 * @param var1 the constraint's first variable 241 * @param coeff2 the constraint's second coefficient 242 * @param var2 the constraint's second variable 243 * @param op the constraint's operand 244 * @param rightSide the constant value on the constraint's right side 245 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 246 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 247 */ 248 Constraint* 249 LinearSpec::AddConstraint(double coeff1, Variable* var1, 250 double coeff2, Variable* var2, OperatorType op, double rightSide, 251 double penaltyNeg, double penaltyPos) 252 { 253 SummandList* summands = new SummandList(2); 254 summands->AddItem(new Summand(coeff1, var1)); 255 summands->AddItem(new Summand(coeff2, var2)); 256 Constraint* c = new Constraint(this, summands, op, rightSide, 257 penaltyNeg, penaltyPos); 258 RemovePresolved(); 259 return c; 260 } 261 262 263 /** 264 * Adds a new soft linear constraint to the specification with three summands. 265 * 266 * @param coeff1 the constraint's first coefficient 267 * @param var1 the constraint's first variable 268 * @param coeff2 the constraint's second coefficient 269 * @param var2 the constraint's second variable 270 * @param coeff3 the constraint's third coefficient 271 * @param var3 the constraint's third variable 272 * @param op the constraint's operand 273 * @param rightSide the constant value on the constraint's right side 274 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 275 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 276 */ 277 Constraint* 278 LinearSpec::AddConstraint(double coeff1, Variable* var1, 279 double coeff2, Variable* var2, double coeff3, Variable* var3, 280 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 281 { 282 SummandList* summands = new SummandList(2); 283 summands->AddItem(new Summand(coeff1, var1)); 284 summands->AddItem(new Summand(coeff2, var2)); 285 summands->AddItem(new Summand(coeff3, var3)); 286 Constraint* c = new Constraint(this, summands, op, rightSide, 287 penaltyNeg, penaltyPos); 288 RemovePresolved(); 289 return c; 290 } 291 292 293 /** 294 * Adds a new soft linear constraint to the specification with four summands. 295 * 296 * @param coeff1 the constraint's first coefficient 297 * @param var1 the constraint's first variable 298 * @param coeff2 the constraint's second coefficient 299 * @param var2 the constraint's second variable 300 * @param coeff3 the constraint's third coefficient 301 * @param var3 the constraint's third variable 302 * @param coeff4 the constraint's fourth coefficient 303 * @param var4 the constraint's fourth variable 304 * @param op the constraint's operand 305 * @param rightSide the constant value on the constraint's right side 306 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 307 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 308 */ 309 Constraint* 310 LinearSpec::AddConstraint(double coeff1, Variable* var1, 311 double coeff2, Variable* var2, double coeff3, Variable* var3, 312 double coeff4, Variable* var4, OperatorType op, double rightSide, 313 double penaltyNeg, double penaltyPos) 314 { 315 SummandList* summands = new SummandList(2); 316 summands->AddItem(new Summand(coeff1, var1)); 317 summands->AddItem(new Summand(coeff2, var2)); 318 summands->AddItem(new Summand(coeff3, var3)); 319 summands->AddItem(new Summand(coeff4, var4)); 320 Constraint* c = new Constraint(this, summands, op, rightSide, 321 penaltyNeg, penaltyPos); 322 RemovePresolved(); 323 return c; 324 } 325 326 327 /** 328 * Adds a new penalty function to the specification. 329 * 330 * @param var the penalty function's variable 331 * @param xs the penalty function's sampling points 332 * @param gs the penalty function's gradients 333 * @return the new penalty function 334 */ 335 PenaltyFunction* 336 LinearSpec::AddPenaltyFunction(Variable* var, BList* xs, BList* gs) 337 { 338 return new PenaltyFunction(this, var, xs, gs); 339 } 340 341 342 /** 343 * Gets the objective function. 344 * 345 * @return SummandList containing the objective function's summands 346 */ 347 SummandList* 348 LinearSpec::ObjectiveFunction() 349 { 350 return fObjFunction; 351 } 352 353 354 SummandList* 355 LinearSpec::ReplaceObjectiveFunction(SummandList* objFunction) 356 { 357 SummandList* list = fObjFunction; 358 fObjFunction = objFunction; 359 UpdateObjectiveFunction(); 360 return list; 361 } 362 363 364 /** 365 * Sets a new objective function. 366 * 367 * @param summands SummandList containing the objective function's summands 368 */ 369 void 370 LinearSpec::SetObjectiveFunction(SummandList* objFunction) 371 { 372 for (int32 i = 0; i < fObjFunction->CountItems(); i++) 373 delete (Summand*)fObjFunction->ItemAt(i); 374 delete fObjFunction; 375 376 fObjFunction = objFunction; 377 UpdateObjectiveFunction(); 378 } 379 380 381 /** 382 * Updates the internal representation of the objective function. 383 * Must be called whenever the summands of the objective function are changed. 384 */ 385 void 386 LinearSpec::UpdateObjectiveFunction() 387 { 388 int32 size = fObjFunction->CountItems(); 389 double coeffs[size]; 390 int varIndexes[size]; 391 Summand* current; 392 for (int32 i = 0; i < size; i++) { 393 current = (Summand*)fObjFunction->ItemAt(i); 394 coeffs[i] = current->Coeff(); 395 varIndexes[i] = current->Var()->Index(); 396 } 397 398 if (!set_obj_fnex(fLP, size, &coeffs[0], &varIndexes[0])) 399 printf("Error in set_obj_fnex."); 400 401 RemovePresolved(); 402 } 403 404 405 /** 406 * Remove a cached presolved model, if existent. 407 * This is automatically done each time after the model has been changed, 408 * to avoid an old cached presolved model getting out of sync. 409 */ 410 void 411 LinearSpec::RemovePresolved() 412 { 413 if (fLpPresolved == NULL) 414 return; 415 delete_lp(fLpPresolved); 416 fLpPresolved = NULL; 417 } 418 419 420 /** 421 * Creates and caches a simplified version of the linear programming problem, 422 * where redundant rows, columns and constraints are removed, 423 * if it has not been created before. 424 * Then, the simplified problem is solved. 425 * 426 * @return the result of the solving attempt 427 */ 428 ResultType 429 LinearSpec::Presolve() 430 { 431 bigtime_t start, end; 432 start = system_time(); 433 434 if (fLpPresolved == NULL) { 435 fLpPresolved = copy_lp(fLP); 436 set_presolve(fLpPresolved, PRESOLVE_ROWS | PRESOLVE_COLS | PRESOLVE_LINDEP, 437 get_presolveloops(fLpPresolved)); 438 } 439 440 fResult = (ResultType)solve(fLpPresolved); 441 fObjectiveValue = get_objective(fLpPresolved); 442 443 if (fResult == OPTIMAL) { 444 int32 size = fVariables.CountItems(); 445 for (int32 i = 0; i < size; i++) { 446 Variable* current = (Variable*)fVariables.ItemAt(i); 447 current->SetValue(get_var_primalresult(fLpPresolved, 448 get_Norig_rows(fLpPresolved) + current->Index())); 449 } 450 } 451 452 end = system_time(); 453 fSolvingTime = (end - start) / 1000.0; 454 455 return fResult; 456 } 457 458 459 /** 460 * Tries to solve the linear programming problem. 461 * If a cached simplified version of the problem exists, it is used instead. 462 * 463 * @return the result of the solving attempt 464 */ 465 ResultType 466 LinearSpec::Solve() 467 { 468 if (fLpPresolved != NULL) 469 return Presolve(); 470 471 bigtime_t start, end; 472 start = system_time(); 473 474 fResult = (ResultType)solve(fLP); 475 fObjectiveValue = get_objective(fLP); 476 477 if (fResult == OPTIMAL) { 478 int32 size = fVariables.CountItems(); 479 double x[size]; 480 if (!get_variables(fLP, &x[0])) 481 printf("Error in get_variables."); 482 483 int32 i = 0; 484 while (i < size) { 485 ((Variable*)fVariables.ItemAt(i))->SetValue(x[i]); 486 i++; 487 } 488 } 489 490 end = system_time(); 491 fSolvingTime = (end - start) / 1000.0; 492 493 return fResult; 494 } 495 496 497 /** 498 * Writes the specification into a text file. 499 * The file will be overwritten if it exists. 500 * 501 * @param fname the file name 502 */ 503 void 504 LinearSpec::Save(const char* fileName) 505 { 506 // TODO: Constness should be fixed in liblpsolve API. 507 write_lp(fLP, const_cast<char*>(fileName)); 508 } 509 510 511 /** 512 * Gets the number of columns. 513 * 514 * @return the number of columns 515 */ 516 int32 517 LinearSpec::CountColumns() const 518 { 519 return fCountColumns; 520 } 521 522 523 /** 524 * Gets the current optimization. 525 * The default is minimization. 526 * 527 * @return the current optimization 528 */ 529 OptimizationType 530 LinearSpec::Optimization() const 531 { 532 return fOptimization; 533 } 534 535 536 /** 537 * Sets whether the solver should minimize or maximize the objective function. 538 * The default is minimization. 539 * 540 * @param optimization the optimization type 541 */ 542 void 543 LinearSpec::SetOptimization(OptimizationType value) 544 { 545 fOptimization = value; 546 if (fOptimization == MINIMIZE) 547 set_minim(fLP); 548 else 549 set_maxim(fLP); 550 } 551 552 553 /** 554 * Gets the the variables. 555 * 556 * @return the variables 557 */ 558 VariableList* 559 LinearSpec::Variables() const 560 { 561 return const_cast<VariableList*>(&fVariables); 562 } 563 564 565 /** 566 * Gets the constraints. 567 * 568 * @return the constraints 569 */ 570 ConstraintList* 571 LinearSpec::Constraints() const 572 { 573 return const_cast<ConstraintList*>(&fConstraints); 574 } 575 576 577 /** 578 * Gets the result type. 579 * 580 * @return the result type 581 */ 582 ResultType 583 LinearSpec::Result() const 584 { 585 return fResult; 586 } 587 588 589 /** 590 * Gets the objective value. 591 * 592 * @return the objective value 593 */ 594 double 595 LinearSpec::ObjectiveValue() const 596 { 597 return fObjectiveValue; 598 } 599 600 601 /** 602 * Gets the solving time. 603 * 604 * @return the solving time 605 */ 606 double 607 LinearSpec::SolvingTime() const 608 { 609 return fSolvingTime; 610 } 611 612 613 LinearSpec::operator BString() const 614 { 615 BString string; 616 GetString(string); 617 return string; 618 } 619 620 621 void 622 LinearSpec::GetString(BString& string) const 623 { 624 string << "LinearSpec " << (int32)this << ":\n"; 625 for (int i = 0; i < fVariables.CountItems(); i++) { 626 Variable* variable = static_cast<Variable*>(fVariables.ItemAt(i)); 627 variable->GetString(string); 628 string << "=" << (float)variable->Value() << " "; 629 } 630 string << "\n"; 631 for (int i = 0; i < fConstraints.CountItems(); i++) { 632 Constraint* c = static_cast<Constraint*>(fConstraints.ItemAt(i)); 633 string << i << ": "; 634 c->GetString(string); 635 string << "\n"; 636 } 637 string << "Result="; 638 if (fResult==-1) 639 string << "ERROR"; 640 else if (fResult==0) 641 string << "OPTIMAL"; 642 else if (fResult==1) 643 string << "SUBOPTIMAL"; 644 else if (fResult==2) 645 string << "INFEASIBLE"; 646 else if (fResult==3) 647 string << "UNBOUNDED"; 648 else if (fResult==4) 649 string << "DEGENERATE"; 650 else if (fResult==5) 651 string << "NUMFAILURE"; 652 else 653 string << fResult; 654 string << " SolvingTime=" << (float)fSolvingTime << "ms"; 655 } 656 657