1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file spxlpbase_rational.hpp
17 * @brief Saving LPs with Rational values in a form suitable for SoPlex.
18 */
19
20 #include <assert.h>
21 #include <stdio.h>
22 #include <ctype.h>
23 #include <iostream>
24
25 #include "soplex/spxdefines.h"
|
(1) Event include_recursion: |
#include file "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scipoptsuite-8.0.1/soplex/src/soplex/spxlpbase.h" includes itself: spxlpbase.h -> spxlpbase_rational.hpp -> spxlpbase.h |
|
(2) Event caretline: |
^ |
26 #include "soplex/spxlpbase.h"
27 #include "soplex/spxout.h"
28 #include "soplex/mpsinput.h"
29 #include "soplex/exceptions.h"
30 #include "soplex/rational.h"
31
32 #define MAX_LINE_WRITE_LEN 65536 ///< maximum length allowed for writing lines
33
34 namespace soplex
35 {
36 template<> inline
37 void SPxLPBase<Rational>::computePrimalActivity(const VectorBase<Rational>& primal,
38 VectorBase<Rational>& activity, const bool unscaled) const
39 {
40 if(primal.dim() != nCols())
41 {
42 throw SPxInternalCodeException("XSPXLP01 Primal vector for computing row activity has wrong dimension");
43 }
44
45 if(activity.dim() != nRows())
46 {
47 throw SPxInternalCodeException("XSPXLP03 Activity vector computing row activity has wrong dimension");
48 }
49
50 int c;
51
52 for(c = 0; c < nCols() && primal[c] == 0; c++)
53 ;
54
55 if(c >= nCols())
56 {
57 activity.clear();
58 return;
59 }
60
61 activity = colVector(c);
62
63 activity *= primal[c];
64 c++;
65
66 for(; c < nCols(); c++)
67 {
68 if(primal[c] != 0)
69 {
70 activity.multAdd(primal[c], colVector(c));
71 }
72 }
73 }
74
75 template<> inline
76 void SPxLPBase<Rational>::computeDualActivity(const VectorBase<Rational>& dual,
77 VectorBase<Rational>& activity, const bool unscaled) const
78 {
79 if(dual.dim() != nRows())
80 {
81 throw SPxInternalCodeException("XSPXLP02 Dual vector for computing dual activity has wrong dimension");
82 }
83
84 if(activity.dim() != nCols())
85 {
86 throw SPxInternalCodeException("XSPXLP04 Activity vector computing dual activity has wrong dimension");
87 }
88
89 int r;
90
91 for(r = 0; r < nRows() && dual[r] == 0; r++)
92 ;
93
94 if(r >= nRows())
95 {
96 activity.clear();
97 return;
98 }
99
100 activity = rowVector(r);
101
102 activity *= dual[r];
103 r++;
104
105 for(; r < nRows(); r++)
106 {
107 if(dual[r] != 0)
108 {
109 activity.multAdd(dual[r], rowVector(r));
110 }
111 }
112 }
113
114 template<> inline
115 Rational SPxLPBase<Rational>::maxAbsNzo(bool /* unscaled */) const
116 {
117 Rational maxi = Rational(0);
118
119 for(int i = 0; i < nCols(); ++i)
120 {
121 Rational m = colVector(i).maxAbs();
122
123 if(m > maxi)
124 maxi = m;
125 }
126
127 assert(maxi >= Rational(0));
128
129 return maxi;
130 }
131
132 template<> inline
133 Rational SPxLPBase<Rational>::minAbsNzo(bool /* unscaled */) const
134 {
135 Rational mini = infinity;
136
137 for(int i = 0; i < nCols(); ++i)
138 {
139 Rational m = colVector(i).minAbs();
140
141 if(m < mini)
142 mini = m;
143 }
144
145 assert(mini >= Rational(0));
146
147 return mini;
148 }
149
150 // ---------------------------------------------------------------------------------------------------------------------
151 // Specialization for reading LP format
152 // ---------------------------------------------------------------------------------------------------------------------
153
154 #define LPF_MAX_LINE_LEN 8192 ///< maximum length of a line (8190 + \\n + \\0)
155
156 /// Read the next number and advance \p pos.
157 /** If only a sign is encountered, the number is assumed to be \c sign * 1. This routine will not catch malformatted
158 * numbers like .e10 !
159 */
160 static Rational LPFreadValue(char*& pos, SPxOut* spxout, const int lineno = -1)
161 {
162 assert(LPFisValue(pos));
163
164 char tmp[LPF_MAX_LINE_LEN];
165 const char* s = pos;
166 char* t;
167 Rational value = 1;
168 bool has_digits = false;
169 bool has_emptyexponent = false;
170 bool has_dot = false;
171 bool has_exponent = false;
172 bool has_emptydivisor = false;
173
174 // 1. sign
175 if((*s == '+') || (*s == '-'))
176 s++;
177
178 // 2. Digits before the decimal dot
179 while((*s >= '0') && (*s <= '9'))
180 {
181 has_digits = true;
182 s++;
183 }
184
185 // 3. Decimal dot
186 if(*s == '.')
187 {
188 has_dot = true;
189 s++;
190
191 // 4. If there was a dot, possible digit behind it
192 while((*s >= '0') && (*s <= '9'))
193 {
194 has_digits = true;
195 s++;
196 }
197 }
198
199 // 5. Exponent
200 if(tolower(*s) == 'e')
201 {
202 has_exponent = true;
203 has_emptyexponent = true;
204 s++;
205
206 // 6. Exponent sign
207 if((*s == '+') || (*s == '-'))
208 s++;
209
210 // 7. Exponent digits
211 while((*s >= '0') && (*s <= '9'))
212 {
213 has_emptyexponent = false;
214 s++;
215 }
216 }
217
218 // 8. Division
219 if(*s == '/')
220 {
221 s++;
222 has_emptydivisor = true;
223
224 while((*s >= '0') && (*s <= '9'))
225 {
226 has_emptydivisor = false;
227 s++;
228 }
229
230 if(has_dot || has_exponent || has_emptydivisor ||
231 (*s == '.') || (*s == '+') || (*s == '-') || (tolower(*s) == 'e'))
232 {
233 MSG_WARNING((*spxout), (*spxout) << "WLPFRD03 Warning: In line " << lineno <<
234 ": malformed rational value in LP file\n";)
235 }
236 }
237
238
239 assert(s != pos);
240
241 if(has_emptyexponent)
242 {
243 MSG_WARNING((*spxout), (*spxout) << "WLPFRD01 Warning: In line " << lineno <<
244 ": found empty exponent in LP file - check for forbidden variable names with initial 'e' or 'E'\n");
245 }
246
247 if(!has_digits)
248 value = (*pos == '-') ? -1 : 1;
249 else
250 {
251 for(t = tmp; pos != s; pos++)
252 *t++ = *pos;
253
254 *t = '\0';
255
256 try
257 {
258 value = ratFromString(tmp);
259 }
260 catch(const std::exception& e)
261 {
262 MSG_WARNING((*spxout), (*spxout) << "WLPFRD04 Warning: In line " << lineno <<
263 ": malformed rational value in LP file\n");
264 std::cerr << e.what() << '\n';
265 }
266 }
267
268 pos += s - pos;
269
270 assert(pos == s);
271
272 MSG_DEBUG(std::cout << "DLPFRD01 LPFreadValue = " << value << std::endl;)
273
274 if(LPFisSpace(*pos))
275 pos++;
276
277 return value;
278 }
279
280
281
282 /// Read the next column name from the input.
283 /** The name read is looked up and if not found \p emptycol
284 * is added to \p colset. \p pos is advanced behind the name.
285 * @return The Index of the named column.
286 */
287 static int LPFreadColName(char*& pos, NameSet* colnames, LPColSetBase<Rational>& colset,
288 const LPColBase<Rational>* emptycol, SPxOut* spxout)
289 {
290 assert(LPFisColName(pos));
291 assert(colnames != 0);
292
293 char name[LPF_MAX_LINE_LEN];
294 const char* s = pos;
295 int i;
296 int colidx;
297
298 // These are the characters that are not allowed in a column name.
299 while((strchr("+-.<>= ", *s) == 0) && (*s != '\0'))
300 s++;
301
302 for(i = 0; pos != s; i++, pos++)
303 name[i] = *pos;
304
305 name[i] = '\0';
306
307 if((colidx = colnames->number(name)) < 0)
308 {
309 // We only add the name if we got an empty column.
310 if(emptycol == 0)
311 MSG_WARNING((*spxout), (*spxout) << "WLPFRD02 Unknown variable \"" << name << "\" ";)
312 else
313 {
314 colidx = colnames->num();
315 colnames->add(name);
316 colset.add(*emptycol);
317 }
318 }
319
320 MSG_DEBUG(std::cout << "DLPFRD03 LPFreadColName [" << name << "] = " << colidx << std::endl;)
321
322 if(LPFisSpace(*pos))
323 pos++;
324
325 return colidx;
326 }
327
328 static Rational LPFreadInfinity(char*& pos)
329 {
330 assert(LPFisInfinity(pos));
331
332 Rational sense = (*pos == '-') ? -1 : 1;
333
334 (void) LPFhasKeyword(++pos, "inf[inity]");
335
336 sense *= Rational(infinity);
337 return sense;
338 }
339
340 /// Read LP in "CPLEX LP File Format".
341 /** The specification is taken from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 527.
342 *
343 * This routine should read (most?) valid LP format files. What it will not do, is find all cases where a file is ill
344 * formed. If this happens it may complain and read nothing or read "something".
345 *
346 * Problem: A line ending in '+' or '-' followed by a line starting with a number, will be regarded as an error.
347 *
348 * The reader will accept the keyword INT[egers] as a synonym for GEN[erals] which is an undocumented feature in CPLEX.
349 *
350 * A difference to the CPLEX reader, is that no name for the objective row is required.
351 *
352 * The manual says the maximum allowed line length is 255 characters, but CPLEX does not complain if the lines are
353 * longer.
354 *
355 * @return true if the file was read correctly
356 */
357 template <> inline
358 bool SPxLPBase<Rational>::readLPF(
359 std::istream& p_input, ///< input stream.
360 NameSet* p_rnames, ///< row names.
361 NameSet* p_cnames, ///< column names.
362 DIdxSet* p_intvars) ///< integer variables.
363 {
364 enum
365 {
366 START, OBJECTIVE, CONSTRAINTS, BOUNDS, INTEGERS, BINARIES
367 } section = START;
368
369 NameSet* rnames; ///< row names.
370 NameSet* cnames; ///< column names.
371
372 LPColSetBase<Rational> cset; ///< the set of columns read.
373 LPRowSetBase<Rational> rset; ///< the set of rows read.
374 LPColBase<Rational> emptycol; ///< reusable empty column.
375 LPRowBase<Rational> row; ///< last assembled row.
376 DSVectorBase<Rational> vec; ///< last assembled vector (from row).
377
378 Rational val = 1;
379 int colidx;
380 int sense = 0;
381
382 char buf[LPF_MAX_LINE_LEN];
383 char tmp[LPF_MAX_LINE_LEN];
384 char line[LPF_MAX_LINE_LEN];
385 int lineno = 0;
386 bool unnamed = true;
387 bool finished = false;
388 bool other;
389 bool have_value = true;
390 int i;
391 int k;
392 char* s;
393 char* pos;
394 char* pos_old = 0;
395
396 if(p_cnames)
397 cnames = p_cnames;
398 else
399 {
400 cnames = 0;
401 spx_alloc(cnames);
402 cnames = new(cnames) NameSet();
403 }
404
405 cnames->clear();
406
407 if(p_rnames)
408 rnames = p_rnames;
409 else
410 {
411 try
412 {
413 rnames = 0;
414 spx_alloc(rnames);
415 rnames = new(rnames) NameSet();
416 }
417 catch(const SPxMemoryException& x)
418 {
419 if(!p_cnames)
420 {
421 cnames->~NameSet();
422 spx_free(cnames);
423 }
424
425 throw x;
426 }
427 }
428
429 rnames->clear();
430
431 SPxLPBase<Rational>::clear(); // clear the LP.
432
433 //--------------------------------------------------------------------------
434 //--- Main Loop
435 //--------------------------------------------------------------------------
436 for(;;)
437 {
438 // 0. Read a line from the file.
439 if(!p_input.getline(buf, sizeof(buf)))
440 {
441 if(strlen(buf) == LPF_MAX_LINE_LEN - 1)
442 {
443 MSG_ERROR(std::cerr << "ELPFRD06 Line exceeds " << LPF_MAX_LINE_LEN - 2
444 << " characters" << std::endl;)
445 }
446 else
447 {
448 MSG_ERROR(std::cerr << "ELPFRD07 No 'End' marker found" << std::endl;)
449 finished = true;
450 }
451
452 break;
453 }
454
455 lineno++;
456 i = 0;
457 pos = buf;
458
459 MSG_DEBUG(std::cout << "DLPFRD08 Reading line " << lineno
460 << " (pos=" << pos << ")" << std::endl;)
461
462 // 1. Remove comments.
463 if(0 != (s = strchr(buf, '\\')))
464 * s = '\0';
465
466 // 2. Look for keywords.
467 if(section == START)
468 {
469 if(LPFhasKeyword(pos, "max[imize]"))
470 {
471 changeSense(SPxLPBase<Rational>::MAXIMIZE);
472 section = OBJECTIVE;
473 }
474 else if(LPFhasKeyword(pos, "min[imize]"))
475 {
476 changeSense(SPxLPBase<Rational>::MINIMIZE);
477 section = OBJECTIVE;
478 }
479 }
480 else if(section == OBJECTIVE)
481 {
482 if(LPFhasKeyword(pos, "s[ubject][ ]t[o]")
483 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
484 || LPFhasKeyword(pos, "s[.][ ]t[.]")
485 || LPFhasKeyword(pos, "lazy con[straints]"))
486 {
487 // store objective vector
488 for(int j = vec.size() - 1; j >= 0; --j)
489 cset.maxObj_w(vec.index(j)) = vec.value(j);
490
491 // multiplication with -1 for minimization is done below
492 vec.clear();
493 have_value = true;
494 val = 1;
495 section = CONSTRAINTS;
496 }
497 }
498 else if(section == CONSTRAINTS &&
499 (LPFhasKeyword(pos, "s[ubject][ ]t[o]")
500 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
501 || LPFhasKeyword(pos, "s[.][ ]t[.]")))
502 {
503 have_value = true;
504 val = 1;
505 }
506 else
507 {
508 if(LPFhasKeyword(pos, "lazy con[straints]"))
509 ;
510 else if(LPFhasKeyword(pos, "bound[s]"))
511 section = BOUNDS;
512 else if(LPFhasKeyword(pos, "bin[ary]"))
513 section = BINARIES;
514 else if(LPFhasKeyword(pos, "bin[aries]"))
515 section = BINARIES;
516 else if(LPFhasKeyword(pos, "gen[erals]"))
517 section = INTEGERS;
518 else if(LPFhasKeyword(pos, "int[egers]")) // this is undocumented
519 section = INTEGERS;
520 else if(LPFhasKeyword(pos, "end"))
521 {
522 finished = true;
523 break;
524 }
525 else if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") // second time
526 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
527 || LPFhasKeyword(pos, "s[.][ ]t[.]")
528 || LPFhasKeyword(pos, "lazy con[straints]"))
529 {
530 // In principle this has to checked for all keywords above,
531 // otherwise we just ignore any half finished constraint
532 if(have_value)
533 goto syntax_error;
534
535 have_value = true;
536 val = 1;
537 }
538 }
539
540 // 3a. Look for row names in objective and drop it.
541 if(section == OBJECTIVE)
542 LPFhasRowName(pos, 0);
543
544 // 3b. Look for row name in constraint and store it.
545 if(section == CONSTRAINTS)
546 if(LPFhasRowName(pos, rnames))
547 unnamed = false;
548
549 // 4a. Remove initial spaces.
550 while(LPFisSpace(pos[i]))
551 i++;
552
553 // 4b. remove spaces if they do not appear before the name of a vaiable.
554 for(k = 0; pos[i] != '\0'; i++)
555 if(!LPFisSpace(pos[i]) || LPFisColName(&pos[i + 1]))
556 tmp[k++] = pos[i];
557
558 tmp[k] = '\0';
559
560 // 5. Is this an empty line ?
561 if(tmp[0] == '\0')
562 continue;
563
564 // 6. Collapse sequences of '+' and '-'. e.g ++---+ => -
565 for(i = 0, k = 0; tmp[i] != '\0'; i++)
566 {
567 while(((tmp[i] == '+') || (tmp[i] == '-')) && ((tmp[i + 1] == '+') || (tmp[i + 1] == '-')))
568 {
569 if(tmp[i++] == '-')
570 tmp[i] = (tmp[i] == '-') ? '+' : '-';
571 }
572
573 line[k++] = tmp[i];
574 }
575
576 line[k] = '\0';
577
578 //-----------------------------------------------------------------------
579 //--- Line processing loop
580 //-----------------------------------------------------------------------
581 pos = line;
582
583 MSG_DEBUG(std::cout << "DLPFRD09 pos=" << pos << std::endl;)
584
585 // 7. We have something left to process.
586 while((pos != 0) && (*pos != '\0'))
587 {
588 // remember our position, so we are sure we make progress.
589 pos_old = pos;
590
591 // now process the sections
592 switch(section)
593 {
594 case OBJECTIVE:
595 if(LPFisValue(pos))
596 {
597 Rational pre_sign = 1;
598
599 /* Already having here a value could only result from being the first number in a constraint, or a sign
600 * '+' or '-' as last token on the previous line.
601 */
602 if(have_value)
603 {
604 if(spxAbs(val) != 1)
605 goto syntax_error;
606
607 if(val == -1)
608 pre_sign = val;
609 }
610
611 have_value = true;
612 val = LPFreadValue(pos, spxout, lineno);
613 val *= pre_sign;
614 }
615
616 if(*pos == '\0')
617 continue;
618
619 if(!have_value || !LPFisColName(pos))
620 goto syntax_error;
621
622 have_value = false;
623 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout);
624 vec.add(colidx, val);
625 break;
626
627 case CONSTRAINTS:
628 if(LPFisValue(pos))
629 {
630 Rational pre_sign = 1;
631
632 /* Already having here a value could only result from being the first number in a constraint, or a sign
633 * '+' or '-' as last token on the previous line.
634 */
635 if(have_value)
636 {
637 if(spxAbs(val) != 1)
638 goto syntax_error;
639
640 if(val == -1)
641 pre_sign = val;
642 }
643
644 have_value = true;
645 val = LPFreadValue(pos, spxout, lineno);
646 val *= pre_sign;
647
648 if(sense != 0)
649 {
650 if(sense == '<')
651 {
652 row.setLhs(-infinity);
653 row.setRhs(val);
654 }
655 else if(sense == '>')
656 {
657 row.setLhs(val);
658 row.setRhs(infinity);
659 }
660 else
661 {
662 assert(sense == '=');
663
664 row.setLhs(val);
665 row.setRhs(val);
666 }
667
668 row.setRowVector(vec);
669 rset.add(row);
670 vec.clear();
671
672 if(!unnamed)
673 unnamed = true;
674 else
675 {
676 char name[16];
677 spxSnprintf(name, 16, "C%d", rset.num());
678 rnames->add(name);
679 }
680
681 have_value = true;
682 val = 1;
683 sense = 0;
684 pos = 0;
685 // next line
686 continue;
687 }
688 }
689
690 if(*pos == '\0')
691 continue;
692
693 if(have_value)
694 {
695 if(LPFisColName(pos))
696 {
697 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout);
698
699 if(val != 0)
700 {
701 // Do we have this index already in the row?
702 int n = vec.pos(colidx);
703
704 // if not, add it
705 if(n < 0)
706 vec.add(colidx, val);
707 // if yes, add them up and remove the element if it amounts to zero
708 else
709 {
710 assert(vec.index(n) == colidx);
711
712 val += vec.value(n);
713
714 if(val == 0)
715 vec.remove(n);
716 else
717 vec.value(n) = val;
718
719 assert(cnames->has(colidx));
720
721 MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD10 Duplicate index "
722 << (*cnames)[colidx]
723 << " in line " << lineno
724 << std::endl;)
725 }
726 }
727
728 have_value = false;
729 }
730 else
731 {
732 // We have a row like c1: <= 5 with no variables. We can not handle 10 <= 5; issue a syntax error.
733 if(val != 1)
734 goto syntax_error;
735
736 // If the next thing is not the sense we give up also.
737 if(!LPFisSense(pos))
738 goto syntax_error;
739
740 have_value = false;
741 }
742 }
743
744 assert(!have_value);
745
746 if(LPFisSense(pos))
747 sense = LPFreadSense(pos);
748
749 break;
750
751 case BOUNDS:
752 other = false;
753 sense = 0;
754
755 if(LPFisValue(pos))
756 {
757 val = LPFisInfinity(pos) ? LPFreadInfinity(pos) : LPFreadValue(pos, spxout, lineno);
758
759 if(!LPFisSense(pos))
760 goto syntax_error;
761
762 sense = LPFreadSense(pos);
763 other = true;
764 }
765
766 if(!LPFisColName(pos))
767 goto syntax_error;
768
769 if((colidx = LPFreadColName(pos, cnames, cset, 0, spxout)) < 0)
770 {
771 MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD11 in Bounds section line "
772 << lineno << " ignored" << std::endl;)
773 *pos = '\0';
774 continue;
775 }
776
777 if(sense)
778 {
779 if(sense == '<')
780 cset.lower_w(colidx) = val;
781 else if(sense == '>')
782 cset.upper_w(colidx) = val;
783 else
784 {
785 assert(sense == '=');
786 cset.lower_w(colidx) = val;
787 cset.upper_w(colidx) = val;
788 }
789 }
790
791 if(LPFisFree(pos))
792 {
793 cset.lower_w(colidx) = -infinity;
794 cset.upper_w(colidx) = infinity;
795 other = true;
796 pos += 4; // set position after the word "free"
797 }
798 else if(LPFisSense(pos))
799 {
800 sense = LPFreadSense(pos);
801 other = true;
802
803 if(!LPFisValue(pos))
804 goto syntax_error;
805
806 val = LPFisInfinity(pos) ? LPFreadInfinity(pos) : LPFreadValue(pos, spxout, lineno);
807
808 if(sense == '<')
809 cset.upper_w(colidx) = val;
810 else if(sense == '>')
811 cset.lower_w(colidx) = val;
812 else
813 {
814 assert(sense == '=');
815 cset.lower_w(colidx) = val;
816 cset.upper_w(colidx) = val;
817 }
818 }
819
820 /* Do we have only a single column name in the input line? We could ignore this savely, but it is probably
821 * a sign of some other error.
822 */
823 if(!other)
824 goto syntax_error;
825
826 break;
827
828 case BINARIES:
829 case INTEGERS:
830 if((colidx = LPFreadColName(pos, cnames, cset, 0, spxout)) < 0)
831 {
832 MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD12 in Binary/General section line " << lineno
833 << " ignored" << std::endl;)
834 }
835 else
836 {
837 if(section == BINARIES)
838 {
839 if(cset.lower(colidx) < 0)
840 {
841 cset.lower_w(colidx) = 0;
842 }
843
844 if(cset.upper(colidx) > 1)
845 {
846 cset.upper_w(colidx) = 1;
847 }
848 }
849
850 if(p_intvars != 0)
851 p_intvars->addIdx(colidx);
852 }
853
854 break;
855
856 case START:
857 MSG_ERROR(std::cerr << "ELPFRD13 This seems to be no LP format file" << std::endl;)
858 goto syntax_error;
859
860 default:
861 throw SPxInternalCodeException("XLPFRD01 This should never happen.");
862 }
863
864 if(pos == pos_old)
865 goto syntax_error;
866 }
867 }
868
869 assert(isConsistent());
870
871 addCols(cset);
872 assert(isConsistent());
873
874 addRows(rset);
875 assert(isConsistent());
876
877 syntax_error:
878
879 if(finished)
880 {
881 MSG_INFO2((*this->spxout), (*this->spxout) << "Finished reading " << lineno << " lines" <<
882 std::endl;)
883 }
884 else
885 MSG_ERROR(std::cerr << "ELPFRD15 Syntax error in line " << lineno << std::endl;)
886
887 if(p_cnames == 0)
888 spx_free(cnames);
889
890 if(p_rnames == 0)
891 spx_free(rnames);
892
893 return finished;
894 }
895
896 /// Process ROWS section.
897 static void MPSreadRows(MPSInput& mps, LPRowSetBase<Rational>& rset, NameSet& rnames,
898 SPxOut* spxout)
899 {
900 LPRowBase<Rational> row;
901
902 while(mps.readLine())
903 {
904 if(mps.field0() != 0)
905 {
906 MSG_INFO2((*spxout), (*spxout) << "IMPSRD02 Objective name : " << mps.objName() << std::endl;)
907
908 if(strcmp(mps.field0(), "COLUMNS"))
909 break;
910
911 mps.setSection(MPSInput::COLUMNS);
912
913 return;
914 }
915
916 if(*mps.field1() == 'N')
917 {
918 if(*mps.objName() == '\0')
919 mps.setObjName(mps.field2());
920 }
921 else
922 {
923 if(rnames.has(mps.field2()))
924 break;
925
926 rnames.add(mps.field2());
927
928 switch(*mps.field1())
929 {
930 case 'G':
931 row.setLhs(0);
932 row.setRhs(infinity);
933 break;
934
935 case 'E':
936 row.setLhs(0);
937 row.setRhs(0);
938 break;
939
940 case 'L':
941 row.setLhs(-infinity);
942 row.setRhs(0);
943 break;
944
945 default:
946 mps.syntaxError();
947 return;
948 }
949
950 rset.add(row);
951 }
952
953 assert((*mps.field1() == 'N') || (rnames.number(mps.field2()) == rset.num() - 1));
954 }
955
956 mps.syntaxError();
957 }
958
959
960
961 /// Process COLUMNS section.
962 static void MPSreadCols(MPSInput& mps, const LPRowSetBase<Rational>& rset, const NameSet& rnames,
963 LPColSetBase<Rational>& cset, NameSet& cnames, DIdxSet* intvars, SPxOut* spxout)
964 {
965 Rational val;
966 int idx;
967 char colname[MPSInput::MAX_LINE_LEN] = { '\0' };
968 LPColBase<Rational> col(rset.num());
969 DSVectorBase<Rational> vec;
970
971 col.setObj(0);
972 vec.clear();
973
974 while(mps.readLine())
975 {
976 if(mps.field0() != 0)
977 {
978 if(strcmp(mps.field0(), "RHS"))
979 break;
980
981 if(colname[0] != '\0')
982 {
983 col.setColVector(vec);
984 cset.add(col);
985 }
986
987 mps.setSection(MPSInput::RHS);
988
989 return;
990 }
991
992 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
993 break;
994
995 // new column?
996 if(strcmp(colname, mps.field1()))
997 {
998 // first column?
999 if(colname[0] != '\0')
1000 {
1001 col.setColVector(vec);
1002 cset.add(col);
1003 }
1004
1005 // save copy of string (make sure string ends with \0)
1006 spxSnprintf(colname, MPSInput::MAX_LINE_LEN - 1, "%s", mps.field1());
1007 colname[MPSInput::MAX_LINE_LEN - 1] = '\0';
1008
1009 int ncnames = cnames.size();
1010 cnames.add(colname);
1011
1012 // check whether the new name is unique wrt previous column names
1013 if(cnames.size() <= ncnames)
1014 {
1015 MSG_ERROR(std::cerr << "ERROR in COLUMNS: duplicate column name or not column-wise ordering" <<
1016 std::endl;)
1017 break;
1018 }
1019
1020 vec.clear();
1021 col.setObj(0);
1022 col.setLower(0);
1023 col.setUpper(infinity);
1024
1025 if(mps.isInteger())
1026 {
1027 assert(cnames.number(colname) == cset.num());
1028
1029 if(intvars != 0)
1030 intvars->addIdx(cnames.number(colname));
1031
1032 // for Integer variable the default bounds are 0/1
1033 col.setUpper(1);
1034 }
1035 }
1036
1037 try
1038 {
1039 val = ratFromString(mps.field3());
1040 }
1041 catch(const std::exception& e)
1042 {
1043 MSG_WARNING((*spxout), (*spxout) << "WMPSRD01 Warning: malformed rational value in MPS file\n");
1044 std::cerr << e.what() << '\n';
1045 }
1046
1047 if(!strcmp(mps.field2(), mps.objName()))
1048 col.setObj(val);
1049 else
1050 {
1051 if((idx = rnames.number(mps.field2())) < 0)
1052 mps.entryIgnored("Column", mps.field1(), "row", mps.field2());
1053 else if(val != 0)
1054 vec.add(idx, val);
1055 }
1056
1057 if(mps.field5() != 0)
1058 {
1059 assert(mps.field4() != 0);
1060
1061 try
1062 {
1063 val = ratFromString(mps.field5());
1064 }
1065 catch(const std::exception& e)
1066 {
1067 MSG_WARNING((*spxout), (*spxout) << "WMPSRD02 Warning: malformed rational value in MPS file\n");
1068 std::cerr << e.what() << '\n';
1069 }
1070
1071 if(!strcmp(mps.field4(), mps.objName()))
1072 col.setObj(val);
1073 else
1074 {
1075 if((idx = rnames.number(mps.field4())) < 0)
1076 mps.entryIgnored("Column", mps.field1(), "row", mps.field4());
1077 else if(val != 0)
1078 vec.add(idx, val);
1079 }
1080 }
1081 }
1082
1083 mps.syntaxError();
1084 }
1085
1086
1087
1088 /// Process RHS section.
1089 static void MPSreadRhs(MPSInput& mps, LPRowSetBase<Rational>& rset, const NameSet& rnames,
1090 SPxOut* spxout)
1091 {
1092 char rhsname[MPSInput::MAX_LINE_LEN] = { '\0' };
1093 char addname[MPSInput::MAX_LINE_LEN] = { '\0' };
1094 int idx;
1095 Rational val;
1096
1097 while(mps.readLine())
1098 {
1099 if(mps.field0() != 0)
1100 {
1101 MSG_INFO2((*spxout), (*spxout) << "IMPSRD03 RHS name : " << rhsname << std::endl;);
1102
1103 if(!strcmp(mps.field0(), "RANGES"))
1104 mps.setSection(MPSInput::RANGES);
1105 else if(!strcmp(mps.field0(), "BOUNDS"))
1106 mps.setSection(MPSInput::BOUNDS);
1107 else if(!strcmp(mps.field0(), "ENDATA"))
1108 mps.setSection(MPSInput::ENDATA);
1109 else
1110 break;
1111
1112 return;
1113 }
1114
1115 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0)))
1116 mps.insertName("_RHS_");
1117
1118 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1119 break;
1120
1121 if(*rhsname == '\0')
1122 spxSnprintf(rhsname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1123
1124 if(strcmp(rhsname, mps.field1()))
1125 {
1126 if(strcmp(addname, mps.field1()))
1127 {
1128 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN);
1129 spxSnprintf(addname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1130 MSG_INFO3((*spxout), (*spxout) << "IMPSRD07 RHS ignored : " << addname << std::endl);
1131 }
1132 }
1133 else
1134 {
1135 if((idx = rnames.number(mps.field2())) < 0)
1136 mps.entryIgnored("RHS", mps.field1(), "row", mps.field2());
1137 else
1138 {
1139 try
1140 {
1141 val = ratFromString(mps.field3());
1142 }
1143 catch(const std::exception& e)
1144 {
1145 MSG_WARNING((*spxout), (*spxout) << "WMPSRD03 Warning: malformed rational value in MPS file\n");
1146 std::cerr << e.what() << '\n';
1147 }
1148
1149 // LE or EQ
1150 if(double(rset.rhs(idx)) < double(infinity))
1151 rset.rhs_w(idx) = val;
1152
1153 // GE or EQ
1154 if(double(rset.lhs(idx)) > double(-infinity))
1155 rset.lhs_w(idx) = val;
1156 }
1157
1158 if(mps.field5() != 0)
1159 {
1160 if((idx = rnames.number(mps.field4())) < 0)
1161 mps.entryIgnored("RHS", mps.field1(), "row", mps.field4());
1162 else
1163 {
1164 try
1165 {
1166 val = ratFromString(mps.field5());
1167 }
1168 catch(const std::exception& e)
1169 {
1170 MSG_WARNING((*spxout), (*spxout) << "WMPSRD04 Warning: malformed rational value in MPS file\n");
1171 std::cerr << e.what() << '\n';
1172 }
1173
1174 // LE or EQ
1175 if(double(rset.rhs(idx)) < double(infinity))
1176 rset.rhs_w(idx) = val;
1177
1178 // GE or EQ
1179 if(double(rset.lhs(idx)) > double(-infinity))
1180 rset.lhs_w(idx) = val;
1181 }
1182 }
1183 }
1184 }
1185
1186 mps.syntaxError();
1187 }
1188
1189
1190
1191 /// Process RANGES section.
1192 static void MPSreadRanges(MPSInput& mps, LPRowSetBase<Rational>& rset, const NameSet& rnames,
1193 SPxOut* spxout)
1194 {
1195 char rngname[MPSInput::MAX_LINE_LEN] = { '\0' };
1196 int idx;
1197 Rational val;
1198
1199 while(mps.readLine())
1200 {
1201 if(mps.field0() != 0)
1202 {
1203 MSG_INFO2((*spxout), (*spxout) << "IMPSRD04 Range name : " << rngname << std::endl;);
1204
1205 if(!strcmp(mps.field0(), "BOUNDS"))
1206 mps.setSection(MPSInput::BOUNDS);
1207 else if(!strcmp(mps.field0(), "ENDATA"))
1208 mps.setSection(MPSInput::ENDATA);
1209 else
1210 break;
1211
1212 return;
1213 }
1214
1215 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0)))
1216 mps.insertName("_RNG_");
1217
1218 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1219 break;
1220
1221 if(*rngname == '\0')
1222 {
1223 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN);
1224 spxSnprintf(rngname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1225 }
1226
1227 /* The rules are:
1228 * Row Sign LHS RHS
1229 * ----------------------------------------
1230 * G +/- rhs rhs + |range|
1231 * L +/- rhs - |range| rhs
1232 * E + rhs rhs + range
1233 * E - rhs + range rhs
1234 * ----------------------------------------
1235 */
1236 if(!strcmp(rngname, mps.field1()))
1237 {
1238 if((idx = rnames.number(mps.field2())) < 0)
1239 mps.entryIgnored("Range", mps.field1(), "row", mps.field2());
1240 else
1241 {
1242 try
1243 {
1244 val = ratFromString(mps.field3());
1245 }
1246 catch(const std::exception& e)
1247 {
1248 MSG_WARNING((*spxout), (*spxout) << "WMPSRD05 Warning: malformed rational value in MPS file\n");
1249 std::cerr << e.what() << '\n';
1250 }
1251
1252 // EQ
1253 if((double(rset.lhs(idx)) > -double(infinity)) && (double(rset.rhs_w(idx)) < double(infinity)))
1254 {
1255 assert(rset.lhs(idx) == rset.rhs(idx));
1256
1257 if(double(val) >= 0)
1258 rset.rhs_w(idx) += val;
1259 else
1260 rset.lhs_w(idx) += val;
1261 }
1262 else
1263 {
1264 // GE
1265 if(double(rset.lhs(idx)) > -double(infinity))
1266 {
1267 rset.rhs_w(idx) = rset.lhs(idx);
1268 rset.rhs_w(idx) += spxAbs(val);
1269 }
1270 // LE
1271 else
1272 {
1273 rset.lhs_w(idx) = rset.rhs(idx);
1274 rset.lhs_w(idx) -= spxAbs(val);
1275 }
1276 }
1277 }
1278
1279 if(mps.field5() != 0)
1280 {
1281 if((idx = rnames.number(mps.field4())) < 0)
1282 mps.entryIgnored("Range", mps.field1(), "row", mps.field4());
1283 else
1284 {
1285 try
1286 {
1287 val = ratFromString(mps.field5());
1288 }
1289 catch(const std::exception& e)
1290 {
1291 MSG_WARNING((*spxout), (*spxout) << "WMPSRD06 Warning: malformed rational value in MPS file\n");
1292 std::cerr << e.what() << '\n';
1293 }
1294
1295 // EQ
1296 if((double(rset.lhs(idx)) > -double(infinity)) && (double(rset.rhs(idx)) < double(infinity)))
1297 {
1298 assert(rset.lhs(idx) == rset.rhs(idx));
1299
1300 if(double(val) >= 0)
1301 rset.rhs_w(idx) += val;
1302 else
1303 rset.lhs_w(idx) += val;
1304 }
1305 else
1306 {
1307 // GE
1308 if(double(rset.lhs(idx)) > -double(infinity))
1309 {
1310 rset.rhs_w(idx) = rset.lhs(idx);
1311 rset.rhs_w(idx) += spxAbs(val);
1312 }
1313 // LE
1314 else
1315 {
1316 rset.lhs_w(idx) = rset.rhs(idx);
1317 rset.lhs_w(idx) -= spxAbs(val);
1318 }
1319 }
1320 }
1321 }
1322 }
1323 }
1324
1325 mps.syntaxError();
1326 }
1327
1328
1329
1330 /// Process BOUNDS section.
1331 static void MPSreadBounds(MPSInput& mps, LPColSetBase<Rational>& cset, const NameSet& cnames,
1332 DIdxSet* intvars, SPxOut* spxout)
1333 {
1334 DIdxSet oldbinvars;
1335 char bndname[MPSInput::MAX_LINE_LEN] = { '\0' };
1336 int idx;
1337 Rational val;
1338
1339 while(mps.readLine())
1340 {
1341 if(mps.field0() != 0)
1342 {
1343 MSG_INFO2((*spxout), (*spxout) << "IMPSRD05 Bound name : " << bndname << std::endl;)
1344
1345 if(strcmp(mps.field0(), "ENDATA"))
1346 break;
1347
1348 mps.setSection(MPSInput::ENDATA);
1349
1350 return;
1351 }
1352
1353 // Is the value field used ?
1354 if((!strcmp(mps.field1(), "LO"))
1355 || (!strcmp(mps.field1(), "UP"))
1356 || (!strcmp(mps.field1(), "FX"))
1357 || (!strcmp(mps.field1(), "LI"))
1358 || (!strcmp(mps.field1(), "UI")))
1359 {
1360 if((mps.field3() != 0) && (mps.field4() == 0))
1361 mps.insertName("_BND_", true);
1362 }
1363 else
1364 {
1365 if((mps.field2() != 0) && (mps.field3() == 0))
1366 mps.insertName("_BND_", true);
1367 }
1368
1369 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1370 break;
1371
1372 if(*bndname == '\0')
1373 {
1374 assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN);
1375 spxSnprintf(bndname, MPSInput::MAX_LINE_LEN, "%s", mps.field2());
1376 }
1377
1378 // Only read the first Bound in section
1379 if(!strcmp(bndname, mps.field2()))
1380 {
1381 if((idx = cnames.number(mps.field3())) < 0)
1382 mps.entryIgnored("column", mps.field3(), "bound", bndname);
1383 else
1384 {
1385 if(mps.field4() == 0)
1386 val = 0;
1387 else if(!strcmp(mps.field4(), "-Inf") || !strcmp(mps.field4(), "-inf"))
1388 val = -infinity;
1389 else if(!strcmp(mps.field4(), "Inf") || !strcmp(mps.field4(), "inf")
1390 || !strcmp(mps.field4(), "+Inf") || !strcmp(mps.field4(), "+inf"))
1391 val = infinity;
1392 else
1393 try
1394 {
1395 val = ratFromString(mps.field4());
1396 }
1397 catch(const std::exception& e)
1398 {
1399 MSG_WARNING((*spxout), (*spxout) << "WMPSRD07 Warning: malformed rational value in MPS file\n");
1400 std::cerr << e.what() << '\n';
1401 }
1402
1403 // ILOG extension (Integer Bound)
1404 if(mps.field1()[1] == 'I')
1405 {
1406 if(intvars != 0)
1407 intvars->addIdx(idx);
1408
1409 // if the variable has appeared in the MARKER section of the COLUMNS section then its default bounds were
1410 // set to 0,1; the first time it is declared integer we need to change to default bounds 0,infinity
1411 if(oldbinvars.pos(idx) < 0)
1412 {
1413 cset.upper_w(idx) = infinity;
1414 oldbinvars.addIdx(idx);
1415 }
1416 }
1417
1418 switch(*mps.field1())
1419 {
1420 case 'L':
1421 cset.lower_w(idx) = val;
1422 break;
1423
1424 case 'U':
1425 cset.upper_w(idx) = val;
1426 break;
1427
1428 case 'F':
1429 if(mps.field1()[1] == 'X')
1430 {
1431 cset.lower_w(idx) = val;
1432 cset.upper_w(idx) = val;
1433 }
1434 else
1435 {
1436 cset.lower_w(idx) = -infinity;
1437 cset.upper_w(idx) = infinity;
1438 }
1439
1440 break;
1441
1442 case 'M':
1443 cset.lower_w(idx) = -infinity;
1444 break;
1445
1446 case 'P':
1447 cset.upper_w(idx) = infinity;
1448 break;
1449
1450 // Ilog extension (Binary)
1451 case 'B':
1452 cset.lower_w(idx) = 0;
1453 cset.upper_w(idx) = 1;
1454
1455 if(intvars != 0)
1456 intvars->addIdx(idx);
1457
1458 break;
1459
1460 default:
1461 mps.syntaxError();
1462 return;
1463 }
1464 }
1465 }
1466 }
1467
1468 mps.syntaxError();
1469 }
1470
1471 /// Read LP in MPS File Format.
1472 /**
1473 * The specification is taken from the IBM Optimization Library Guide and Reference, online available at
1474 * http://www.software.ibm.com/sos/features/libuser.htm and from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page
1475 * 531.
1476 *
1477 * This routine should read all valid MPS format files. What it will not do, is find all cases where a file is ill
1478 * formed. If this happens it may complain and read nothing or read "something".
1479 *
1480 * @return true if the file was read correctly.
1481 */
1482 #define INIT_COLS 1000 ///< initialy allocated columns.
1483 #define INIT_NZOS 5000 ///< initialy allocated non zeros.
1484 template <> inline
1485 bool SPxLPBase<Rational>::readMPS(
1486 std::istream& p_input, ///< input stream.
1487 NameSet* p_rnames, ///< row names.
1488 NameSet* p_cnames, ///< column names.
1489 DIdxSet* p_intvars) ///< integer variables.
1490 {
1491 LPRowSetBase<Rational>& rset = *this;
1492 LPColSetBase<Rational>& cset = *this;
1493 NameSet* rnames;
1494 NameSet* cnames;
1495
1496 if(p_cnames)
1497 cnames = p_cnames;
1498 else
1499 {
1500 cnames = 0;
1501 spx_alloc(cnames);
1502 cnames = new(cnames) NameSet();
1503 }
1504
1505 cnames->clear();
1506
1507 if(p_rnames)
1508 rnames = p_rnames;
1509 else
1510 {
1511 try
1512 {
1513 rnames = 0;
1514 spx_alloc(rnames);
1515 rnames = new(rnames) NameSet();
1516 }
1517 catch(const SPxMemoryException& x)
1518 {
1519 if(!p_cnames)
1520 {
1521 cnames->~NameSet();
1522 spx_free(cnames);
1523 }
1524
1525 throw x;
1526 }
1527 }
1528
1529 rnames->clear();
1530
1531 SPxLPBase<Rational>::clear(); // clear the LP.
1532
1533 cset.memRemax(INIT_NZOS);
1534 cset.reMax(INIT_COLS);
1535
1536 MPSInput mps(p_input);
1537
1538 MPSreadName(mps, spxout);
1539
1540 if(mps.section() == MPSInput::OBJSEN)
1541 MPSreadObjsen(mps);
1542
1543 if(mps.section() == MPSInput::OBJNAME)
1544 MPSreadObjname(mps);
1545
1546 if(mps.section() == MPSInput::ROWS)
1547 MPSreadRows(mps, rset, *rnames, spxout);
1548
1549 addedRows(rset.num());
1550
1551 if(mps.section() == MPSInput::COLUMNS)
1552 MPSreadCols(mps, rset, *rnames, cset, *cnames, p_intvars, spxout);
1553
1554 if(mps.section() == MPSInput::RHS)
1555 MPSreadRhs(mps, rset, *rnames, spxout);
1556
1557 if(mps.section() == MPSInput::RANGES)
1558 MPSreadRanges(mps, rset, *rnames, spxout);
1559
1560 if(mps.section() == MPSInput::BOUNDS)
1561 MPSreadBounds(mps, cset, *cnames, p_intvars, spxout);
1562
1563 if(mps.section() != MPSInput::ENDATA)
1564 mps.syntaxError();
1565
1566 if(mps.hasError())
1567 clear();
1568 else
1569 {
1570 changeSense(mps.objSense() == MPSInput::MINIMIZE ? SPxLPBase<Rational>::MINIMIZE :
1571 SPxLPBase<Rational>::MAXIMIZE);
1572
1573 MSG_INFO2((*spxout), (*spxout) << "IMPSRD06 Objective sense: " << ((mps.objSense() ==
1574 MPSInput::MINIMIZE) ? "Minimize\n" : "Maximize\n"));
1575
1576 added2Set(
1577 *(reinterpret_cast<SVSetBase<Rational>*>(static_cast<LPRowSetBase<Rational>*>(this))),
1578 *(reinterpret_cast<SVSetBase<Rational>*>(static_cast<LPColSetBase<Rational>*>(this))),
1579 cset.num());
1580 addedCols(cset.num());
1581
1582 assert(isConsistent());
1583 }
1584
1585 if(p_cnames == 0)
1586 {
1587 cnames->~NameSet();
1588 spx_free(cnames);
1589 }
1590
1591 if(p_rnames == 0)
1592 {
1593 rnames->~NameSet();
1594 spx_free(rnames);
1595 }
1596
1597 return !mps.hasError();
1598 }
1599
1600
1601
1602 // ---------------------------------------------------------------------------------------------------------------------
1603 // Specialization for writing LP format
1604 // ---------------------------------------------------------------------------------------------------------------------
1605
1606 // get the name of a row or construct one
1607 static const char* LPFgetRowName(
1608 const SPxLPBase<Rational>& p_lp,
1609 int p_idx,
1610 const NameSet* p_rnames,
1611 char* p_buf,
1612 int p_num_written_rows
1613 )
1614 {
1615 assert(p_buf != 0);
1616 assert(p_idx >= 0);
1617 assert(p_idx < p_lp.nRows());
1618
1619 if(p_rnames != 0)
1620 {
1621 DataKey key = p_lp.rId(p_idx);
1622
1623 if(p_rnames->has(key))
1624 return (*p_rnames)[key];
1625 }
1626
1627 spxSnprintf(p_buf, 16, "C%d", p_num_written_rows);
1628
1629 return p_buf;
1630 }
1631
1632
1633
1634 // get the name of a column or construct one
1635 static const char* getColName(
1636 const SPxLPBase<Rational>& p_lp,
1637 int p_idx,
1638 const NameSet* p_cnames,
1639 char* p_buf
1640 )
1641 {
1642 assert(p_buf != 0);
1643 assert(p_idx >= 0);
1644 assert(p_idx < p_lp.nCols());
1645
1646 if(p_cnames != 0)
1647 {
1648 DataKey key = p_lp.cId(p_idx);
1649
1650 if(p_cnames->has(key))
1651 return (*p_cnames)[key];
1652 }
1653
1654 spxSnprintf(p_buf, 16, "x%d", p_idx);
1655
1656 return p_buf;
1657 }
1658
1659
1660
1661 // write an SVector
1662 #define NUM_ENTRIES_PER_LINE 5
1663 static void LPFwriteSVector(
1664 const SPxLPBase<Rational>& p_lp, ///< the LP
1665 std::ostream& p_output, ///< output stream
1666 const NameSet* p_cnames, ///< column names
1667 const SVectorBase<Rational>& p_svec, ///< vector to write
1668 SPxOut* spxout ///< out stream
1669 )
1670 {
1671
1672 char name[16];
1673 int num_coeffs = 0;
1674 long long pos;
1675
1676 pos = p_output.tellp();
1677
1678 for(int j = 0; j < p_lp.nCols(); ++j)
1679 {
1680 const Rational coeff = p_svec[j];
1681
1682 if(coeff == 0)
1683 continue;
1684
1685 if(num_coeffs == 0)
1686 p_output << coeff << " " << getColName(p_lp, j, p_cnames, name);
1687 else
1688 {
1689 // insert a line break every NUM_ENTRIES_PER_LINE columns or whenever max line length is nearly exceeded
1690 if(num_coeffs == NUM_ENTRIES_PER_LINE ||
1691 (long long)(p_output.tellp()) - pos + (long long)(coeff.str().length() + 100) > MAX_LINE_WRITE_LEN)
1692 {
1693 num_coeffs = 0;
1694 p_output << "\n\t";
1695
1696 if((long long)(p_output.tellp()) - pos > MAX_LINE_WRITE_LEN)
1697 {
1698 MSG_WARNING((*spxout), (*spxout) <<
1699 "XLPSWR01 Warning: MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n");
1700 }
1701
1702 pos = p_output.tellp();
1703 }
1704
1705 if(coeff < 0)
1706 p_output << " - " << -coeff;
1707 else
1708 p_output << " + " << coeff;
1709
1710 p_output << " " << getColName(p_lp, j, p_cnames, name);
1711 }
1712
1713 ++num_coeffs;
1714 }
1715 }
1716
1717
1718
1719 // write the objective
1720 static void LPFwriteObjective(
1721 const SPxLPBase<Rational>& p_lp, ///< the LP
1722 std::ostream& p_output, ///< output stream
1723 const NameSet* p_cnames, ///< column names
1724 SPxOut* spxout ///< out stream
1725 )
1726 {
1727
1728 const int sense = p_lp.spxSense();
1729
1730 p_output << ((sense == SPxLPBase<Rational>::MINIMIZE) ? "Minimize\n" : "Maximize\n");
1731 p_output << " obj: ";
1732
1733 const VectorBase<Rational>& obj = p_lp.maxObj();
1734 DSVectorBase<Rational> svec(obj.dim());
1735 svec.operator = (obj);
1736 svec *= Rational(sense);
1737 LPFwriteSVector(p_lp, p_output, p_cnames, svec, spxout);
1738 p_output << "\n";
1739 }
1740
1741
1742
1743 // write non-ranged rows
1744 static void LPFwriteRow(
1745 const SPxLPBase<Rational>& p_lp, ///< the LP
1746 std::ostream& p_output, ///< output stream
1747 const NameSet* p_cnames, ///< column names
1748 const SVectorBase<Rational>& p_svec, ///< vector of the row
1749 const Rational& p_lhs, ///< lhs of the row
1750 const Rational& p_rhs, ///< rhs of the row
1751 SPxOut* spxout ///< out stream
1752 )
1753 {
1754
1755 long long pos;
1756 pos = p_output.tellp();
1757
1758 LPFwriteSVector(p_lp, p_output, p_cnames, p_svec, spxout);
1759
1760 long long sidelen;
1761 sidelen = (p_lhs == p_rhs
1762 || double(p_lhs) <= double(-infinity)) ? (long long)p_rhs.str().length()
1763 : (long long)p_lhs.str().length();
1764
1765 // insert a line break if max line length is in danger of being exceeded
1766 if((long long)(p_output.tellp()) - pos + sidelen + (long long)100 > MAX_LINE_WRITE_LEN)
1767 {
1768 p_output << "\n\t";
1769
1770 if((long long)(p_output.tellp()) - pos > MAX_LINE_WRITE_LEN)
1771 {
1772 MSG_WARNING((*spxout), (*spxout) <<
1773 "XLPSWR02 Warning: MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n");
1774 }
1775
1776 pos = p_output.tellp();
1777 }
1778
1779 // write bound value
1780 if(p_lhs == p_rhs)
1781 p_output << " = " << p_rhs;
1782 else if(double(p_lhs) <= double(-infinity))
1783 p_output << " <= " << p_rhs;
1784 else
1785 {
1786 assert(double(p_rhs) >= double(infinity));
1787 p_output << " >= " << p_lhs;
1788 }
1789
1790 p_output << "\n";
1791
1792 if((long long)(p_output.tellp()) - pos > MAX_LINE_WRITE_LEN)
1793 {
1794 MSG_WARNING((*spxout), (*spxout) <<
1795 "XLPSWR03 Warning: MAX_LINE_WRITE_LEN possibly exceeded when writing LP file\n");
1796 }
1797 }
1798
1799
1800
1801 // write all rows
1802 static void LPFwriteRows(
1803 const SPxLPBase<Rational>& p_lp, ///< the LP
1804 std::ostream& p_output, ///< output stream
1805 const NameSet* p_rnames, ///< row names
1806 const NameSet* p_cnames, ///< column names
1807 SPxOut* spxout ///< out stream
1808 )
1809 {
1810
1811 char name[16];
1812
1813 p_output << "Subject To\n";
1814
1815 for(int i = 0; i < p_lp.nRows(); ++i)
1816 {
1817 const Rational lhs = p_lp.lhs(i);
1818 const Rational rhs = p_lp.rhs(i);
1819
1820 if(double(lhs) > -double(infinity) && double(rhs) < double(infinity) && lhs != rhs)
1821 {
1822 // ranged row -> write two non-ranged rows
1823 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_1 : ";
1824 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, infinity, spxout);
1825
1826 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_2 : ";
1827 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), -infinity, rhs, spxout);
1828 }
1829 else
1830 {
1831 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << " : ";
1832 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, rhs, spxout);
1833 }
1834 }
1835 }
1836
1837
1838
1839 // write the variable bounds
1840 // (the default bounds 0 <= x <= infinity are not written)
1841 static void LPFwriteBounds(
1842 const SPxLPBase<Rational>& p_lp, ///< the LP to write
1843 std::ostream& p_output, ///< output stream
1844 const NameSet* p_cnames, ///< column names
1845 SPxOut* spxout ///< out stream
1846 )
1847 {
1848
1849 char name[16];
1850 long long pos;
1851
1852 pos = p_output.tellp();
1853
1854 p_output << "Bounds\n";
1855
1856 for(int j = 0; j < p_lp.nCols(); ++j)
1857 {
1858 const Rational lower = p_lp.lower(j);
1859 const Rational upper = p_lp.upper(j);
1860
1861 if(lower == upper)
1862 {
1863 p_output << " " << getColName(p_lp, j, p_cnames, name) << " = " << upper << '\n';
1864 }
1865 else if(double(lower) > -double(infinity))
1866 {
1867 if(double(upper) < double(infinity))
1868 {
1869 // range bound
1870 if(lower != 0)
1871 p_output << " " << lower << " <= "
1872 << getColName(p_lp, j, p_cnames, name)
1873 << " <= " << upper << '\n';
1874 else
1875 p_output << " " << getColName(p_lp, j, p_cnames, name)
1876 << " <= " << upper << '\n';
1877 }
1878 else if(lower != 0)
1879 p_output << " " << lower << " <= "
1880 << getColName(p_lp, j, p_cnames, name)
1881 << '\n';
1882 }
1883 else if(double(upper) < double(infinity))
1884 p_output << " -Inf <= "
1885 << getColName(p_lp, j, p_cnames, name)
1886 << " <= " << upper << '\n';
1887 else
1888 p_output << " " << getColName(p_lp, j, p_cnames, name)
1889 << " free\n";
1890
1891 // check if max line length exceeded
1892 if((long long)(p_output.tellp()) - pos > MAX_LINE_WRITE_LEN)
1893 {
1894 MSG_WARNING((*spxout), (*spxout) <<
1895 "XLPSWR04 Warning: MAX_LINE_WRITE_LEN exceeded when writing LP file\n");
1896 }
1897
1898 pos = p_output.tellp();
1899 }
1900 }
1901
1902
1903
1904 // write the generals section
1905 static void LPFwriteGenerals(
1906 const SPxLPBase<Rational>& p_lp, ///< the LP to write
1907 std::ostream& p_output, ///< output stream
1908 const NameSet* p_cnames, ///< column names
1909 const DIdxSet* p_intvars ///< integer variables
1910 )
1911 {
1912
1913 char name[16];
1914
1915 if(p_intvars == NULL || p_intvars->size() <= 0)
1916 return; // no integer variables
1917
1918 p_output << "Generals\n";
1919
1920 for(int j = 0; j < p_lp.nCols(); ++j)
1921 if(p_intvars->pos(j) >= 0)
1922 p_output << " " << getColName(p_lp, j, p_cnames, name) << "\n";
1923 }
1924
1925
1926 /// Write LP in LP Format.
1927 template <> inline
1928 void SPxLPBase<Rational>::writeLPF(
1929 std::ostream& p_output, ///< output stream
1930 const NameSet* p_rnames, ///< row names
1931 const NameSet* p_cnames, ///< column names
1932 const DIdxSet* p_intvars ///< integer variables
1933 ) const
1934 {
1935 LPFwriteObjective(*this, p_output, p_cnames, spxout);
1936 LPFwriteRows(*this, p_output, p_rnames, p_cnames, spxout);
1937 LPFwriteBounds(*this, p_output, p_cnames, spxout);
1938 LPFwriteGenerals(*this, p_output, p_cnames, p_intvars);
1939
1940 p_output << "End" << std::endl;
1941 }
1942
1943
1944
1945 // ---------------------------------------------------------------------------------------------------------------------
1946 // Specialization for writing MPS format
1947 // ---------------------------------------------------------------------------------------------------------------------
1948
1949 // A problem here.
1950 static void MPSwriteRecord(
1951 std::ostream& os,
1952 const char* indicator,
1953 const char* name,
1954 SPxOut* spxout,
1955 const char* name1 = nullptr,
1956 const Rational value1 = 0,
1957 const char* name2 = nullptr,
1958 const Rational value2 = 0
1959 )
1960 {
1961 char buf[81];
1962 long long pos;
1963 pos = os.tellp();
1964
1965 spxSnprintf(buf, sizeof(buf), " %-2.2s %-8.8s", (indicator == 0) ? "" : indicator,
1966 (name == 0) ? "" : name);
1967 os << buf;
1968
1969 if(name1 != nullptr)
1970 {
1971 spxSnprintf(buf, sizeof(buf), " %-8.8s ", name1);
1972 os << buf << value1;
1973
1974 if(name2 != 0)
1975 {
1976 spxSnprintf(buf, sizeof(buf), " %-8.8s ", name2);
1977 os << buf << value2;
1978 }
1979 }
1980
1981 os << std::endl;
1982
1983 // Warning if line is too long
1984 if((long long)(os.tellp()) - pos > MAX_LINE_WRITE_LEN)
1985 {
1986 MSG_WARNING((*spxout), (*spxout) <<
1987 "XMPSWR04 Warning: MAX_LINE_WRITE_LEN exceeded when writing MPS file\n");
1988 }
1989 }
1990
1991
1992
1993 static Rational MPSgetRHS(Rational left, Rational right)
1994 {
1995 Rational rhsval;
1996
1997 if(double(left) > -double(infinity)) /// This includes ranges
1998 rhsval = left;
1999 else if(double(right) < double(infinity))
2000 rhsval = right;
2001 else
2002 throw SPxInternalCodeException("XMPSWR01 This should never happen.");
2003
2004 return rhsval;
2005 }
2006
2007
2008
2009 static const char* MPSgetRowName(
2010 const SPxLPBase<Rational>& lp,
2011 int idx,
2012 const NameSet* rnames,
2013 char* buf
2014 )
2015 {
2016 assert(buf != 0);
2017 assert(idx >= 0);
2018 assert(idx < lp.nRows());
2019
2020 if(rnames != 0)
2021 {
2022 DataKey key = lp.rId(idx);
2023
2024 if(rnames->has(key))
2025 return (*rnames)[key];
2026 }
2027
2028 spxSnprintf(buf, 16, "C%d", idx);
2029
2030 return buf;
2031 }
2032
2033
2034
2035 /// Write LP in MPS format.
2036 /** @note There will always be a BOUNDS section, even if there are no bounds.
2037 */
2038 template <> inline
2039 void SPxLPBase<Rational>::writeMPS(
2040 std::ostream& p_output, ///< output stream.
2041 const NameSet* p_rnames, ///< row names.
2042 const NameSet* p_cnames, ///< column names.
2043 const DIdxSet* p_intvars ///< integer variables.
2044 ) const
2045 {
2046
2047 const char* indicator;
2048 char name [16];
2049 char name1[16];
2050 char name2[16];
2051 bool has_ranges = false;
2052 int i;
2053 int k;
2054
2055 // --- NAME Section ---
2056 p_output << "NAME MPSDATA" << std::endl;
2057
2058 // --- ROWS Section ---
2059 p_output << "ROWS" << std::endl;
2060
2061 for(i = 0; i < nRows(); i++)
2062 {
2063 if(lhs(i) == rhs(i))
2064 indicator = "E";
2065 else if((double(lhs(i)) > -double(infinity)) && (double(rhs(i)) < double(infinity)))
2066 {
2067 indicator = "E";
2068 has_ranges = true;
2069 }
2070 else if(double(lhs(i)) > -double(infinity))
2071 indicator = "G";
2072 else if(double(rhs(i)) < double(infinity))
2073 indicator = "L";
2074 else
2075 throw SPxInternalCodeException("XMPSWR02 This should never happen.");
2076
2077 MPSwriteRecord(p_output, indicator, MPSgetRowName(*this, i, p_rnames, name), spxout);
2078 }
2079
2080 MPSwriteRecord(p_output, "N", "MINIMIZE", spxout);
2081
2082 // --- COLUMNS Section ---
2083 p_output << "COLUMNS" << std::endl;
2084
2085 bool has_intvars = (p_intvars != 0) && (p_intvars->size() > 0);
2086
2087 for(int j = 0; j < (has_intvars ? 2 : 1); j++)
2088 {
2089 bool is_intrun = has_intvars && (j == 1);
2090
2091 if(is_intrun)
2092 p_output << " MARK0001 'MARKER' 'INTORG'" << std::endl;
2093
2094 for(i = 0; i < nCols(); i++)
2095 {
2096 bool is_intvar = has_intvars && (p_intvars->pos(i) >= 0);
2097
2098 if((is_intrun && !is_intvar) || (!is_intrun && is_intvar))
2099 continue;
2100
2101 const SVectorBase<Rational>& col = colVector(i);
2102 int colsize2 = (col.size() / 2) * 2;
2103
2104 assert(colsize2 % 2 == 0);
2105
2106 for(k = 0; k < colsize2; k += 2)
2107 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout,
2108 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k),
2109 MPSgetRowName(*this, col.index(k + 1), p_rnames, name2), col.value(k + 1));
2110
2111 if(colsize2 != col.size())
2112 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout,
2113 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k));
2114
2115 if(maxObj(i) != 0)
2116 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), spxout, "MINIMIZE", -maxObj(i));
2117 }
2118
2119 if(is_intrun)
2120 p_output << " MARK0001 'MARKER' 'INTEND'" << std::endl;
2121 }
2122
2123 // --- RHS Section ---
2124 p_output << "RHS" << std::endl;
2125
2126 i = 0;
2127
2128 while(i < nRows())
2129 {
2130 Rational rhsval1 = 0;
2131 Rational rhsval2 = 0;
2132
2133 for(; i < nRows(); i++)
2134 if((rhsval1 = MPSgetRHS(lhs(i), rhs(i))) != 0)
2135 break;
2136
2137 if(i < nRows())
2138 {
2139 for(k = i + 1; k < nRows(); k++)
2140 {
2141 if((rhsval2 = MPSgetRHS(lhs(k), rhs(k))) != 0)
2142 break;
2143 }
2144
2145 if(k < nRows())
2146 {
2147 MPSwriteRecord(p_output, 0, "RHS", spxout, MPSgetRowName(*this, i, p_rnames, name1), rhsval1,
2148 MPSgetRowName(*this, k, p_rnames, name2), rhsval2);
2149 }
2150 else
2151 MPSwriteRecord(p_output, 0, "RHS", spxout, MPSgetRowName(*this, i, p_rnames, name1), rhsval1);
2152
2153 i = k + 1;
2154 }
2155 }
2156
2157 // --- RANGES Section ---
2158 if(has_ranges)
2159 {
2160 p_output << "RANGES" << std::endl;
2161
2162 for(i = 0; i < nRows(); i++)
2163 {
2164 if((double(lhs(i)) > -double(infinity)) && (double(rhs(i)) < double(infinity)))
2165 {
2166 Rational range = rhs(i);
2167 range -= lhs(i);
2168 MPSwriteRecord(p_output, "", "RANGE", spxout, MPSgetRowName(*this, i, p_rnames, name1), range);
2169 }
2170 }
2171 }
2172
2173 // --- BOUNDS Section ---
2174 p_output << "BOUNDS" << std::endl;
2175
2176 for(i = 0; i < nCols(); i++)
2177 {
2178 // skip variables that do not appear in the objective function or any constraint
2179 const SVectorBase<Rational>& col = colVector(i);
2180
2181 if(col.size() == 0 && maxObj(i) == 0)
2182 continue;
2183
2184 if(lower(i) == upper(i))
2185 {
2186 MPSwriteRecord(p_output, "FX", "BOUND", spxout, getColName(*this, i, p_cnames, name1), lower(i));
2187 continue;
2188 }
2189
2190 if((double(lower(i)) <= double(-infinity)) && (double(upper(i)) >= double(infinity)))
2191 {
2192 MPSwriteRecord(p_output, "FR", "BOUND", spxout, getColName(*this, i, p_cnames, name1));
2193 continue;
2194 }
2195
2196 if(lower(i) != 0)
2197 {
2198 if(double(lower(i)) > -double(infinity))
2199 MPSwriteRecord(p_output, "LO", "BOUND", spxout, getColName(*this, i, p_cnames, name1), lower(i));
2200 else
2201 MPSwriteRecord(p_output, "MI", "BOUND", spxout, getColName(*this, i, p_cnames, name1));
2202 }
2203
2204 if(has_intvars && (p_intvars->pos(i) >= 0))
2205 {
2206 // Integer variables have default upper bound 1, but we should write
2207 // it nevertheless since CPLEX seems to assume infinity otherwise.
2208 MPSwriteRecord(p_output, "UP", "BOUND", spxout, getColName(*this, i, p_cnames, name1), upper(i));
2209 }
2210 else
2211 {
2212 // Continous variables have default upper bound infinity
2213 if(double(upper(i)) < double(infinity))
2214 MPSwriteRecord(p_output, "UP", "BOUND", spxout, getColName(*this, i, p_cnames, name1), upper(i));
2215 }
2216 }
2217
2218 // --- ENDATA Section ---
2219 p_output << "ENDATA" << std::endl;
2220
2221 // Output warning when writing a maximisation problem
2222 if(spxSense() == SPxLPBase<Rational>::MAXIMIZE)
2223 {
2224 MSG_WARNING((*spxout), (*spxout) <<
2225 "XMPSWR03 Warning: objective function inverted when writing maximization problem in MPS file format\n");
2226 }
2227 }
2228
2229
2230
2231 /// Building the dual problem from a given LP
2232 /// @note primalRows must be as large as the number of unranged primal rows + 2 * the number of ranged primal rows.
2233 /// dualCols must have the identical size to the primal rows.
2234 template <> inline
2235 void SPxLPBase<Rational>::buildDualProblem(SPxLPBase<Rational>& dualLP, SPxRowId primalRowIds[],
2236 SPxColId primalColIds[],
2237 SPxRowId dualRowIds[], SPxColId dualColIds[], int* nprimalrows, int* nprimalcols, int* ndualrows,
2238 int* ndualcols)
2239 {
2240 assert(false);
2241 MSG_ERROR(std::cerr << "Method buildDualProblem() not implemented for Rational\n");
2242 }
2243
2244
2245 // ---------------------------------------------------------------------------------------------------------------------
2246 // Explicit instantiation
2247 // ---------------------------------------------------------------------------------------------------------------------
2248 template class SPxLPBase < Rational >;
2249 } // namespace soplex
2250