275 return (c >= '0' && c <= '9') || c == '.'; |
391 return (c >= '0' && c <= '9') || c == '.'; |
276 } |
392 } |
277 |
393 |
278 static bool varChar(char c) { |
394 static bool varChar(char c) { |
279 return (c >= '0' && c <= '9') || |
395 return (c >= '0' && c <= '9') || |
280 (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); |
396 (c >= 'a' && c <= 'z') || |
281 } |
397 (c >= 'A' && c <= 'Z') || |
282 |
398 c == '[' || c == ']'; |
283 |
|
284 void addConstraint(const LpSolverBase::Constr& constr) { |
|
285 if (constr.expr().size() != 1) { |
|
286 lp.addRow(constr); |
|
287 } else { |
|
288 Lp::Expr e = constr.expr(); |
|
289 LpSolverBase::Col col = e.begin()->first; |
|
290 double coeff = e.begin()->second; |
|
291 double lb = LpSolverBase::NaN; |
|
292 double ub = LpSolverBase::NaN; |
|
293 if (coeff > 0) { |
|
294 if (constr.upperBounded()) { |
|
295 lb = (constr.lowerBound() - e.constComp()) / coeff; |
|
296 } |
|
297 if (constr.lowerBounded()) { |
|
298 ub = (constr.upperBound() - e.constComp()) / coeff; |
|
299 } |
|
300 } else if (coeff < 0) { |
|
301 if (constr.upperBounded()) { |
|
302 lb = (constr.upperBound() - e.constComp()) / coeff; |
|
303 } |
|
304 if (constr.lowerBounded()) { |
|
305 ub = (constr.lowerBound() - e.constComp()) / coeff; |
|
306 } |
|
307 } else { |
|
308 lb = -LpSolverBase::INF; |
|
309 ub = LpSolverBase::INF; |
|
310 } |
|
311 lp.colLowerBound(col, lb); |
|
312 lp.colUpperBound(col, ub); |
|
313 } |
|
314 } |
399 } |
315 |
400 |
316 protected: |
401 protected: |
317 |
402 |
318 /// \brief Reader function of the section. |
403 /// \brief Reader function of the section. |
319 /// |
404 /// |
320 /// It reads the content of the section. |
405 /// It reads the content of the section. |
321 virtual void read(std::istream& is) { |
406 virtual void read(std::istream& is) { |
322 std::string line; |
407 std::string line; |
|
408 SubSection sub = CONSTRAINTS; |
323 while (getline(is, line)) { |
409 while (getline(is, line)) { |
324 std::istringstream ls(line); |
410 std::istringstream ls(line); |
325 std::string sense; |
411 std::string type; |
326 ls >> sense; |
412 ls >> type; |
327 if (sense == "min" || sense == "max") { |
413 if (type == "constraints") { |
328 LpSolverBase::Expr expr; |
414 sub = CONSTRAINTS; |
329 ls >> std::ws; |
415 } else if (type == "bounds") { |
330 readExpression(ls, expr); |
416 sub = BOUNDS; |
331 lp.setObj(expr); |
417 } else if (type == "objective") { |
332 if (sense == "min") { |
418 sub = OBJECTIVE; |
333 lp.min(); |
|
334 } else { |
|
335 lp.max(); |
|
336 } |
|
337 } else { |
419 } else { |
338 ls.str(line); |
420 ls.str(line); |
339 LpSolverBase::Constr constr; |
421 switch (sub) { |
340 ls >> std::ws; |
422 case CONSTRAINTS: |
341 readConstraint(ls, constr); |
423 readConstraint(ls); |
342 addConstraint(constr); |
424 break; |
|
425 case BOUNDS: |
|
426 readBounds(ls); |
|
427 break; |
|
428 case OBJECTIVE: |
|
429 readObjective(ls); |
|
430 break; |
|
431 } |
343 } |
432 } |
344 } |
433 } |
345 } |
434 } |
346 |
435 |
347 virtual void missing() { |
436 virtual void missing() { |
358 std::string name; |
447 std::string name; |
359 ColMap cols; |
448 ColMap cols; |
360 }; |
449 }; |
361 |
450 |
362 |
451 |
363 // class LpWriter : public LemonWriter::SectionWriter { |
452 class LpWriter : public LemonWriter::SectionWriter { |
364 // typedef LemonWriter::SectionWriter Parent; |
453 typedef LemonWriter::SectionWriter Parent; |
365 // public: |
454 public: |
366 |
455 |
367 |
456 |
368 // /// \brief Constructor. |
457 /// \brief Constructor. |
369 // /// |
458 /// |
370 // /// Constructor for LpWriter. It creates the LpWriter and attach |
459 /// Constructor for LpWriter. It creates the LpWriter and attach |
371 // /// it into the given LemonWriter. The lp writer will add |
460 /// it into the given LemonWriter. The lp writer will add |
372 // /// variables, constraints and objective function to the |
461 /// variables, constraints and objective function to the |
373 // /// given lp solver. |
462 /// given lp solver. |
374 // LpWriter(LemonWriter& _writer, LpSolverBase& _lp, |
463 LpWriter(LemonWriter& _writer, LpSolverBase& _lp, |
375 // const std::string& _name = std::string()) |
464 const std::string& _name = std::string()) |
376 // : Parent(_writer), lp(_lp), name(_name) {} |
465 : Parent(_writer), lp(_lp), name(_name) {} |
377 |
466 |
378 |
467 |
379 // /// \brief Destructor. |
468 /// \brief Destructor. |
380 // /// |
469 /// |
381 // /// Destructor for NodeSetWriter. |
470 /// Destructor for NodeSetWriter. |
382 // virtual ~LpWriter() {} |
471 virtual ~LpWriter() {} |
383 |
472 |
384 // private: |
473 private: |
385 // LpWriter(const LpWriter&); |
474 LpWriter(const LpWriter&); |
386 // void operator=(const LpWriter&); |
475 void operator=(const LpWriter&); |
387 |
476 |
388 // protected: |
477 protected: |
389 |
478 |
390 // /// \brief Gives back true when the SectionWriter can process |
479 /// \brief Gives back true when the SectionWriter can process |
391 // /// the section with the given header line. |
480 /// the section with the given header line. |
392 // /// |
481 /// |
393 // /// It gives back the header line of the \c \@lp section. |
482 /// It gives back the header line of the \c \@lp section. |
394 // virtual std::string header() { |
483 virtual std::string header() { |
395 // std::ostringstream ls(line); |
484 std::ostringstream ls; |
396 // ls << "@lp " << name; |
485 ls << "@lp " << name; |
397 // return ls.str(); |
486 return ls.str(); |
398 // } |
487 } |
399 |
488 |
400 // private: |
489 private: |
401 |
490 |
402 // std::ostream& writeConstraint(std::ostream& is, LpSolverBase::Constr& c) { |
491 void createCols() { |
403 // char x; |
492 int num = 1; |
404 |
493 |
|
494 std::map<std::string, LpSolverBase::Col> inverse; |
|
495 |
|
496 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) { |
|
497 std::string name = lp.colName(it); |
|
498 if (!name.empty() && inverse.find(name) == inverse.end()) { |
|
499 cols.insert(std::make_pair(it, name)); |
|
500 inverse.insert(std::make_pair(name, it)); |
|
501 } else { |
|
502 std::ostringstream ls; |
|
503 ls << "var" << num; |
|
504 ++num; |
|
505 cols.insert(std::make_pair(it, ls.str())); |
|
506 inverse.insert(std::make_pair(ls.str(), it)); |
|
507 } |
|
508 } |
|
509 } |
|
510 |
|
511 void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) { |
|
512 bool first = true; |
|
513 for (LpSolverBase::Expr::const_iterator jt = e.begin(); |
|
514 jt != e.end(); ++jt) { |
|
515 if (jt->second < 0.0) { |
|
516 os << "- "; |
|
517 if (jt->second != -1.0) { |
|
518 os << -jt->second << " * "; |
|
519 } |
|
520 } else if (jt->second > 0.0) { |
|
521 if (!first) { |
|
522 os << "+ "; |
|
523 } |
|
524 if (jt->second != 1.0) { |
|
525 os << jt->second << " * "; |
|
526 } |
|
527 } |
|
528 first = false; |
|
529 os << cols[jt->first] << " "; |
|
530 } |
|
531 if (e.constComp() < 0.0) { |
|
532 os << "- " << -e.constComp() << " "; |
|
533 } else if (e.constComp() > 0.0) { |
|
534 if (!first) { |
|
535 os << "+ "; |
|
536 } |
|
537 os << e.constComp() << " "; |
|
538 } |
|
539 } |
|
540 |
|
541 protected: |
|
542 |
|
543 /// \brief Writer function of the section. |
|
544 /// |
|
545 /// It writes the content of the section. |
|
546 virtual void write(std::ostream& os) { |
|
547 createCols(); |
|
548 |
|
549 os << "constraints" << std::endl; |
405 |
550 |
406 // LpSolverBase::Expr e1, e2; |
551 for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) { |
407 // Relation op1; |
552 double lower, upper; |
408 // is >> std::ws; |
553 lp.getRowBounds(it, lower, upper); |
409 // writexpression(is, e1); |
554 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) |
410 // is >> std::ws; |
555 continue; |
411 // writeRelation(is, op1); |
556 os << " "; |
412 // is >> std::ws; |
557 |
413 // writexpression(is, e2); |
558 if (lower != upper) { |
414 // if (!is.get(x)) { |
559 if (lower != -LpSolverBase::INF) { |
415 // if (op1 == LE) { |
560 os << lower << " <= "; |
416 // c = e1 <= e2; |
561 } |
417 // } else if (op1 == GE) { |
562 |
418 // c = e1 >= e2; |
563 writeExpression(os, lp.row(it)); |
419 // } else { |
564 |
420 // c = e1 == e2; |
565 if (upper != LpSolverBase::INF) { |
421 // } |
566 os << "<= " << upper << " "; |
422 // } else { |
567 } |
423 // is.putback(x); |
568 } else { |
424 // LpSolverBase::Expr e3; |
569 |
425 // Relation op2; |
570 writeExpression(os, lp.row(it)); |
426 // writeRelation(is, op2); |
571 os << "== " << upper << " "; |
427 // is >> std::ws; |
572 |
428 // writexpression(is, e3); |
573 } |
429 // if (!e1.empty() || !e3.empty()) { |
574 |
430 // throw DataFormatError("Wrong range format"); |
575 os << std::endl; |
431 // } |
576 } |
432 // if (op2 != op1 || op1 == EQ) { |
577 |
433 // throw DataFormatError("Wrong range format"); |
578 os << "bounds" << std::endl; |
434 // } |
|
435 // if (op1 == LE) { |
|
436 // c = e1.constComp() <= e2 <= e3.constComp(); |
|
437 // } else { |
|
438 // c = e1.constComp() >= e2 >= e3.constComp(); |
|
439 // } |
|
440 // } |
|
441 // } |
|
442 |
|
443 // std::ostream& writexpression(std::ostream& is, LpSolverBase::Expr& e) { |
|
444 // LpSolverBase::Col c; |
|
445 // double d; |
|
446 // char x; |
|
447 // writelement(is, c, d); |
|
448 // if (c != INVALID) { |
|
449 // e += d * c; |
|
450 // } else { |
|
451 // e += d; |
|
452 // } |
|
453 // is >> std::ws; |
|
454 // while (is.get(x) && (x == '+' || x == '-')) { |
|
455 // is >> std::ws; |
|
456 // writelement(is, c, d); |
|
457 // if (c != INVALID) { |
|
458 // e += (x == '+' ? d : -d) * c; |
|
459 // } else { |
|
460 // e += (x == '+' ? d : -d); |
|
461 // } |
|
462 // is >> std::ws; |
|
463 // } |
|
464 // if (!is) { |
|
465 // is.clear(); |
|
466 // } else { |
|
467 // is.putback(x); |
|
468 // } |
|
469 // return is; |
|
470 // } |
|
471 |
|
472 // std::ostream& writelement(std::ostream& is, |
|
473 // LpSolverBase::Col& c, double& d) { |
|
474 // d = 1.0; |
|
475 // c = INVALID; |
|
476 // char x, y; |
|
477 // if (!is.get(x)) throw DataFormatError("Cannot find lp element"); |
|
478 // if (x == '+' || x == '-') { |
|
479 // is >> std::ws; |
|
480 // d *= x == '-' ? -1 : 1; |
|
481 // while (is.get(x) && (x == '+' || x == '-')) { |
|
482 // d *= x == '-' ? -1 : 1; |
|
483 // is >> std::ws; |
|
484 // } |
|
485 // if (!is) throw DataFormatError("Cannot find lp element"); |
|
486 // } |
|
487 // if (numFirstChar(x)) { |
|
488 // is.putback(x); |
|
489 // double e; |
|
490 // writeNum(is, e); |
|
491 // d *= e; |
|
492 // } else if (varFirstChar(x)) { |
|
493 // is.putback(x); |
|
494 // LpSolverBase::Col f; |
|
495 // writeCol(is, f); |
|
496 // c = f; |
|
497 // } else { |
|
498 // throw DataFormatError("Invalid expression format"); |
|
499 // } |
|
500 // is >> std::ws; |
|
501 // while (is.get(y) && (y == '*' || y == '/')) { |
|
502 // is >> std::ws; |
|
503 // if (!is.get(x)) throw DataFormatError("Cannot find lp element"); |
|
504 // if (x == '+' || x == '-') { |
|
505 // is >> std::ws; |
|
506 // d *= x == '-' ? -1 : 1; |
|
507 // while (is.get(x) && (x == '+' || x == '-')) { |
|
508 // d *= x == '-' ? -1 : 1; |
|
509 // is >> std::ws; |
|
510 // } |
|
511 // if (!is) throw DataFormatError("Cannot find lp element"); |
|
512 // } |
|
513 // if (numFirstChar(x)) { |
|
514 // is.putback(x); |
|
515 // double e; |
|
516 // writeNum(is, e); |
|
517 // if (y == '*') { |
|
518 // d *= e; |
|
519 // } else { |
|
520 // d /= e; |
|
521 // } |
|
522 // } else if (varFirstChar(x)) { |
|
523 // is.putback(x); |
|
524 // LpSolverBase::Col f; |
|
525 // writeCol(is, f); |
|
526 // if (y == '*') { |
|
527 // if (c == INVALID) { |
|
528 // c = f; |
|
529 // } else { |
|
530 // throw DataFormatError("Quadratic element in expression"); |
|
531 // } |
|
532 // } else { |
|
533 // throw DataFormatError("Division by variable"); |
|
534 // } |
|
535 // } else { |
|
536 // throw DataFormatError("Invalid expression format"); |
|
537 // } |
|
538 // is >> std::ws; |
|
539 // } |
|
540 // if (!is) { |
|
541 // is.clear(); |
|
542 // } else { |
|
543 // is.putback(y); |
|
544 // } |
|
545 // return is; |
|
546 // } |
|
547 |
|
548 // std::ostream& writeCol(std::ostream& is, LpSolverBase::Col& c) { |
|
549 // char x; |
|
550 // std::string var; |
|
551 // while (is.get(x) && varChar(x)) { |
|
552 // var += x; |
|
553 // } |
|
554 // if (!is) { |
|
555 // is.clear(); |
|
556 // } else { |
|
557 // is.putback(x); |
|
558 // } |
|
559 // ColMap::const_iterator it = cols.find(var); |
|
560 // if (cols.find(var) != cols.end()) { |
|
561 // c = it->second; |
|
562 // } else { |
|
563 // c = lp.addCol(); |
|
564 // cols.insert(std::make_pair(var, c)); |
|
565 // lp.colName(c, var); |
|
566 // } |
|
567 // return is; |
|
568 // } |
|
569 |
|
570 // std::ostream& writeNum(std::ostream& is, double& d) { |
|
571 // is >> d; |
|
572 // if (!is) throw DataFormatError("Wrong number format"); |
|
573 // return is; |
|
574 // } |
|
575 |
|
576 // std::ostream& writeRelation(std::ostream& is, Relation& op) { |
|
577 // char x, y; |
|
578 // if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) { |
|
579 // throw DataFormatError("Wrong relation operator"); |
|
580 // } |
|
581 // if (!is.get(y) || y != '=') { |
|
582 // throw DataFormatError("Wrong relation operator"); |
|
583 // } |
|
584 // switch (x) { |
|
585 // case '<': op = LE; |
|
586 // break; |
|
587 // case '=': op = EQ; |
|
588 // break; |
|
589 // case '>': op = GE; |
|
590 // break; |
|
591 // } |
|
592 // return is; |
|
593 // } |
|
594 |
|
595 // static bool relationFirstChar(char c) { |
|
596 // return c == '<' || c == '=' || c == '>'; |
|
597 // } |
|
598 |
|
599 // static bool varFirstChar(char c) { |
|
600 // return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); |
|
601 // } |
|
602 |
|
603 // static bool numFirstChar(char c) { |
|
604 // return (c >= '0' && c <= '9') || c == '.'; |
|
605 // } |
|
606 |
|
607 // static bool varChar(char c) { |
|
608 // return (c >= '0' && c <= '9') || |
|
609 // (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); |
|
610 // } |
|
611 |
|
612 |
|
613 // void addConstraint(const LpSolverBase::Constr& constr) { |
|
614 // if (constr.expr().size() != 1) { |
|
615 // lp.addRow(constr); |
|
616 // } else { |
|
617 // Lp::Expr e = constr.expr(); |
|
618 // LpSolverBase::Col col = e.begin()->first; |
|
619 // double coeff = e.begin()->second; |
|
620 // double lb = LpSolverBase::NaN; |
|
621 // double ub = LpSolverBase::NaN; |
|
622 // if (coeff > 0) { |
|
623 // if (constr.upperBounded()) { |
|
624 // lb = (constr.lowerBound() - e.constComp()) / coeff; |
|
625 // } |
|
626 // if (constr.lowerBounded()) { |
|
627 // ub = (constr.upperBound() - e.constComp()) / coeff; |
|
628 // } |
|
629 // } else if (coeff < 0) { |
|
630 // if (constr.upperBounded()) { |
|
631 // lb = (constr.upperBound() - e.constComp()) / coeff; |
|
632 // } |
|
633 // if (constr.lowerBounded()) { |
|
634 // ub = (constr.lowerBound() - e.constComp()) / coeff; |
|
635 // } |
|
636 // } else { |
|
637 // lb = -LpSolverBase::INF; |
|
638 // ub = LpSolverBase::INF; |
|
639 // } |
|
640 // lp.colLowerBound(col, lb); |
|
641 // lp.colUpperBound(col, ub); |
|
642 // } |
|
643 // } |
|
644 |
|
645 // protected: |
|
646 |
|
647 // /// \brief Writer function of the section. |
|
648 // /// |
|
649 // /// It writes the content of the section. |
|
650 // virtual void write(std::ostream& is) { |
|
651 // std::string line; |
|
652 // std::map<std::string, LpSolverBase::Col> vars; |
|
653 // while (getline(is, line)) { |
|
654 // std::istringstream ls(line); |
|
655 // std::string sense; |
|
656 // ls >> sense; |
|
657 // if (sense == "min" || sense == "max") { |
|
658 // LpSolverBase::Expr expr; |
|
659 // ls >> std::ws; |
|
660 // writeExpression(ls, expr); |
|
661 // lp.setObj(expr); |
|
662 // if (sense == "min") { |
|
663 // lp.min(); |
|
664 // } else { |
|
665 // lp.max(); |
|
666 // } |
|
667 // } else { |
|
668 // ls.str(line); |
|
669 // LpSolverBase::Constr constr; |
|
670 // ls >> std::ws; |
|
671 // writeConstraint(ls, constr); |
|
672 // addConstraint(constr); |
|
673 // } |
|
674 // } |
|
675 // } |
|
676 |
579 |
677 // virtual void missing() { |
580 for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) { |
678 // ErrorMessage msg; |
581 double lower = lp.colLowerBound(it); |
679 // msg << "Lp section not found in file: @lp " << name; |
582 double upper = lp.colUpperBound(it); |
680 // throw IoParameterError(msg.message()); |
583 if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF) |
681 // } |
584 continue; |
682 |
585 os << " "; |
683 // private: |
586 |
684 |
587 if (lower != upper) { |
685 // typedef std::map<std::string, LpSolverBase::Col> ColMap; |
588 if (lower != -LpSolverBase::INF) { |
|
589 os << lower << " <= "; |
|
590 } |
|
591 |
|
592 os << cols[it] << " "; |
|
593 |
|
594 if (upper != LpSolverBase::INF) { |
|
595 os << "<= " << upper << " "; |
|
596 } |
|
597 } else { |
|
598 os << cols[it] << " == " << upper << " "; |
|
599 } |
|
600 os << std::endl; |
|
601 } |
|
602 |
|
603 os << "objective" << std::endl; |
|
604 os << " "; |
|
605 if (lp.is_min()) { |
|
606 os << "min "; |
|
607 } else { |
|
608 os << "max "; |
|
609 } |
|
610 writeExpression(os, lp.obj()); |
|
611 os << std::endl; |
|
612 } |
686 |
613 |
687 // LpSolverBase& lp; |
614 |
688 // std::string name; |
615 private: |
689 // ColMap cols; |
616 |
690 // }; |
617 typedef std::map<LpSolverBase::Col, std::string> ColMap; |
|
618 |
|
619 LpSolverBase& lp; |
|
620 std::string name; |
|
621 ColMap cols; |
|
622 }; |
691 |
623 |
692 } |
624 } |
693 |
625 |
694 #endif |
626 #endif |