1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25 /**@file spxlpbase_real.hpp
26 * @brief Saving LPs with R values in a form suitable for SoPlex.
27 */
28
29 #include <assert.h>
30 #include <stdio.h>
31 #include <ctype.h>
32 #include <iostream>
33
34 #include "soplex/spxdefines.h"
35 #include "soplex/spxout.h"
36 #include "soplex/mpsinput.h"
37 #include "soplex/exceptions.h"
38 #include "soplex/spxscaler.h"
39
40 namespace soplex
41 {
42 /// Is \p c a \c space, \c tab, \c nl or \c cr ?
43 static inline bool LPFisSpace(int c)
44 {
45 return (c == ' ') || (c == '\t') || (c == '\n') || (c == '\r');
46 }
47
48 /// Is there a number at the beginning of \p s ?
49 static inline bool LPFisValue(const char* s)
50 {
51 return ((*s >= '0') && (*s <= '9')) || (*s == '+') || (*s == '-') || (*s == '.');
52 }
53
54
55 /// Is there a comparison operator at the beginning of \p s ?
56 static inline bool LPFisSense(const char* s)
57 {
58 return (*s == '<') || (*s == '>') || (*s == '=');
59 }
60
61 template <class R>
62 void SPxLPBase<R>::unscaleLP()
63 {
64 SPX_MSG_INFO3((*this->spxout), (*this->spxout) << "remove persistent scaling of LP" << std::endl;)
65
66 if(lp_scaler)
67 {
68 lp_scaler->unscale(*this);
69 }
70 else
71 {
72 SPX_MSG_INFO3((*this->spxout), (*this->spxout) << "no LP scaler available" << std::endl;)
73 }
74 }
75
76 template <class R> inline
77 void SPxLPBase<R>::computePrimalActivity(const VectorBase<R>& primal, VectorBase<R>& activity,
78 const bool unscaled) const
79 {
80 if(primal.dim() != nCols())
81 throw SPxInternalCodeException("XSPXLP01 Primal vector for computing row activity has wrong dimension");
82
83 if(activity.dim() != nRows())
84 throw SPxInternalCodeException("XSPXLP03 Activity vector computing row activity has wrong dimension");
85
86 int c;
87
88 for(c = 0; c < nCols() && primal[c] == 0; c++)
89 ;
90
91 if(c >= nCols())
92 {
93 activity.clear();
94 return;
95 }
96
97 DSVectorBase<R> tmp(nRows());
98
99 if(unscaled && _isScaled)
100 {
101 lp_scaler->getColUnscaled(*this, c, tmp);
102 activity = tmp;
103 }
104 else
105 activity = colVector(c);
106
107 activity *= primal[c];
108 c++;
109
110 for(; c < nCols(); c++)
111 {
112 if(primal[c] != 0)
113 {
114 if(unscaled && _isScaled)
115 {
116 lp_scaler->getColUnscaled(*this, c, tmp);
117 activity.multAdd(primal[c], tmp);
118 }
119 else
120 activity.multAdd(primal[c], colVector(c));
121 }
122 }
123 }
124
125 template <class R> inline
126 void SPxLPBase<R>::computeDualActivity(const VectorBase<R>& dual, VectorBase<R>& activity,
127 const bool unscaled) const
128 {
129 if(dual.dim() != nRows())
130 throw SPxInternalCodeException("XSPXLP02 Dual vector for computing dual activity has wrong dimension");
131
132 if(activity.dim() != nCols())
133 throw SPxInternalCodeException("XSPXLP04 Activity vector computing dual activity has wrong dimension");
134
135 int r;
136
137 for(r = 0; r < nRows() && dual[r] == 0; r++)
138 ;
139
140 if(r >= nRows())
141 {
142 activity.clear();
143 return;
144 }
145
146 DSVectorBase<R> tmp(nCols());
147
148 if(unscaled && _isScaled)
149 {
150 lp_scaler->getRowUnscaled(*this, r, tmp);
151 activity = tmp;
152 }
153 else
154 activity = rowVector(r);
155
156 activity *= dual[r];
157 r++;
158
159 for(; r < nRows(); r++)
160 {
161 if(dual[r] != 0)
162 {
163 if(unscaled && _isScaled)
164 {
165 lp_scaler->getRowUnscaled(*this, r, tmp);
166 activity.multAdd(dual[r], tmp);
167 }
168 else
169 activity.multAdd(dual[r], rowVector(r));
170 }
171 }
172 }
173
174 template <class R> inline
175 R SPxLPBase<R>::maxAbsNzo(bool unscaled) const
176 {
177 R maxi = 0.0;
178
179 if(unscaled && _isScaled)
180 {
181 assert(lp_scaler != nullptr);
182
183 for(int i = 0; i < nCols(); ++i)
184 {
185 R m = lp_scaler->getColMaxAbsUnscaled(*this, i);
186
187 if(m > maxi)
188 maxi = m;
189 }
190 }
191 else
192 {
193 for(int i = 0; i < nCols(); ++i)
194 {
195 R m = colVector(i).maxAbs();
196
197 if(m > maxi)
198 maxi = m;
199 }
200 }
201
202 assert(maxi >= 0.0);
203
204 return maxi;
205 }
206
207 template <class R> inline
208 R SPxLPBase<R>::minAbsNzo(bool unscaled) const
209 {
210 R mini = R(infinity);
211
212 if(unscaled && _isScaled)
213 {
214 assert(lp_scaler != nullptr);
215
216 for(int i = 0; i < nCols(); ++i)
217 {
218 R m = lp_scaler->getColMinAbsUnscaled(*this, i);
219
220 if(m < mini)
221 mini = m;
222 }
223 }
224 else
225 {
226 for(int i = 0; i < nCols(); ++i)
227 {
228 R m = colVector(i).minAbs();
229
230 if(m < mini)
231 mini = m;
232 }
233 }
234
235 assert(mini >= 0.0);
236
237 return mini;
238 }
239
240 /// Gets unscaled objective vector.
241 template <class R>
242 void SPxLPBase<R>::getObjUnscaled(VectorBase<R>& pobj) const
243 {
244 if(_isScaled)
245 {
246 assert(lp_scaler);
247 lp_scaler->getMaxObjUnscaled(*this, pobj);
248 }
249 else
250 {
251 pobj = LPColSetBase<R>::maxObj();
252 }
253
254 if(spxSense() == MINIMIZE)
255 pobj *= -1.0;
256 }
257
258 /// Gets unscaled row vector of row \p i.
259 template <class R>
260 void SPxLPBase<R>::getRowVectorUnscaled(int i, DSVectorBase<R>& vec) const
261 {
262 assert(i >= 0 && i < nRows());
263
264 if(_isScaled)
265 lp_scaler->getRowUnscaled(*this, i, vec);
266 else
267 vec = DSVectorBase<R>(LPRowSetBase<R>::rowVector(i));
268 }
269
270 /// Gets unscaled right hand side vector.
271 template <class R>
272 void SPxLPBase<R>::getRhsUnscaled(VectorBase<R>& vec) const
273 {
274 if(_isScaled)
275 lp_scaler->getRhsUnscaled(*this, vec);
276 else
277 vec = LPRowSetBase<R>::rhs();
278 }
279
280 /// Returns unscaled right hand side of row number \p i.
281 template <class R>
282 R SPxLPBase<R>::rhsUnscaled(int i) const
283 {
284 assert(i >= 0 && i < nRows());
285
286 if(_isScaled)
287 return lp_scaler->rhsUnscaled(*this, i);
288 else
289 return LPRowSetBase<R>::rhs(i);
290 }
291
292 /// Returns unscaled right hand side of row with identifier \p id.
293 template <class R>
294 R SPxLPBase<R>::rhsUnscaled(const SPxRowId& id) const
295 {
296 assert(id.isValid());
297 return rhsUnscaled(number(id));
298 }
299
300 /// Returns unscaled left hand side vector.
301 template <class R>
302 void SPxLPBase<R>::getLhsUnscaled(VectorBase<R>& vec) const
303 {
304 if(_isScaled)
305 lp_scaler->getLhsUnscaled(*this, vec);
306 else
307 vec = LPRowSetBase<R>::lhs();
308 }
309
310 /// Returns unscaled left hand side of row number \p i.
311 template <class R>
312 R SPxLPBase<R>::lhsUnscaled(int i) const
313 {
314 assert(i >= 0 && i < nRows());
315
316 if(_isScaled)
317 return lp_scaler->lhsUnscaled(*this, i);
318 else
319 return LPRowSetBase<R>::lhs(i);
320 }
321
322 /// Returns left hand side of row with identifier \p id.
323 template <class R>
324 R SPxLPBase<R>::lhsUnscaled(const SPxRowId& id) const
325 {
326 assert(id.isValid());
327 return lhsUnscaled(number(id));
328 }
329
330 /// Gets column vector of column \p i.
331 template <class R>
332 void SPxLPBase<R>::getColVectorUnscaled(int i, DSVectorBase<R>& vec) const
333 {
334 assert(i >= 0 && i < nCols());
335
336 if(_isScaled)
337 lp_scaler->getColUnscaled(*this, i, vec);
338 else
339 vec = LPColSetBase<R>::colVector(i);
340 }
341
342 /// Gets column vector of column with identifier \p id.
343 template <class R>
344 void SPxLPBase<R>::getColVectorUnscaled(const SPxColId& id, DSVectorBase<R>& vec) const
345 {
346 assert(id.isValid());
347 getColVectorUnscaled(number(id), vec);
348 }
349
350 /// Returns unscaled objective value of column \p i.
351 template <class R>
352 R SPxLPBase<R>::objUnscaled(int i) const
353 {
354 assert(i >= 0 && i < nCols());
355 R res;
356
357 if(_isScaled)
358 {
359 res = lp_scaler->maxObjUnscaled(*this, i);
360 }
361 else
362 {
363 res = maxObj(i);
364 }
365
366 if(spxSense() == MINIMIZE)
367 res *= -1;
368
369 return res;
370 }
371
372 /// Returns unscaled objective value of column with identifier \p id.
373 template <class R>
374 R SPxLPBase<R>::objUnscaled(const SPxColId& id) const
375 {
376 assert(id.isValid());
377 return objUnscaled(number(id));
378 }
379
380 /// Returns unscaled objective vector for maximization problem.
381 template <class R>
382 void SPxLPBase<R>::maxObjUnscaled(VectorBase<R>& vec) const
383 {
384 if(_isScaled)
385 lp_scaler->getMaxObjUnscaled(*this, vec);
386 else
387 vec = LPColSetBase<R>::maxObj();
388 }
389
390 /// Returns unscaled objective value of column \p i for maximization problem.
391 template <class R>
392 R SPxLPBase<R>::maxObjUnscaled(int i) const
393 {
394 assert(i >= 0 && i < nCols());
395
396 if(_isScaled)
397 return lp_scaler->maxObjUnscaled(*this, i);
398 else
399 return LPColSetBase<R>::maxObj(i);
400 }
401
402 /// Returns unscaled objective value of column with identifier \p id for maximization problem.
403 template <class R>
404 R SPxLPBase<R>::maxObjUnscaled(const SPxColId& id) const
405 {
406 assert(id.isValid());
407 return maxObjUnscaled(number(id));
408 }
409
410 /// Returns unscaled upper bound vector
411 template <class R>
412 void SPxLPBase<R>::getUpperUnscaled(VectorBase<R>& vec) const
413 {
414 if(_isScaled)
415 lp_scaler->getUpperUnscaled(*this, vec);
416 else
417 vec = VectorBase<R>(LPColSetBase<R>::upper());
418 }
419
420 /// Returns unscaled upper bound of column \p i.
421 template <class R>
422 R SPxLPBase<R>::upperUnscaled(int i) const
423 {
424 assert(i >= 0 && i < nCols());
425
426 if(_isScaled)
427 return lp_scaler->upperUnscaled(*this, i);
428 else
429 return LPColSetBase<R>::upper(i);
430 }
431
432 /// Returns unscaled upper bound of column with identifier \p id.
433 template <class R>
434 R SPxLPBase<R>::upperUnscaled(const SPxColId& id) const
435 {
436 assert(id.isValid());
437 return upperUnscaled(number(id));
438 }
439
440 /// Returns unscaled lower bound vector.
441 template <class R>
442 void SPxLPBase<R>::getLowerUnscaled(VectorBase<R>& vec) const
443 {
444 if(_isScaled)
445 lp_scaler->getLowerUnscaled(*this, vec);
446 else
447 vec = VectorBase<R>(LPColSetBase<R>::lower());
448 }
449
450 /// Returns unscaled lower bound of column \p i.
451 template<class R>
452 R SPxLPBase<R>::lowerUnscaled(int i) const
453 {
454 assert(i >= 0 && i < nCols());
455
456 if(_isScaled)
457 return lp_scaler->lowerUnscaled(*this, i);
458 else
459 return LPColSetBase<R>::lower(i);
460 }
461
462 /// Returns unscaled lower bound of column with identifier \p id.
463 template <class R>
464 R SPxLPBase<R>::lowerUnscaled(const SPxColId& id) const
465 {
466 assert(id.isValid());
467 return lowerUnscaled(number(id));
468 }
469
470
471
472
473 // ---------------------------------------------------------------------------------------------------------------------
474 // Specialization for reading LP format
475 // ---------------------------------------------------------------------------------------------------------------------
476
477 #define SOPLEX_LPF_MAX_LINE_LEN 8192 ///< maximum length of a line (8190 + \\n + \\0)
478
479
480 /// Is there a possible column name at the beginning of \p s ?
481 static inline bool LPFisColName(const char* s)
482 {
483 // strchr() gives a true for the null char.
484 if(*s == '\0')
485 return false;
486
487 return ((*s >= 'A') && (*s <= 'Z'))
488 || ((*s >= 'a') && (*s <= 'z'))
489 || (strchr("!\"#$%&()/,;?@_'`{}|~", *s) != 0);
490 }
491
492
493 static inline bool LPFisInfinity(const char* s)
494 {
495 return ((s[0] == '-') || (s[0] == '+'))
496 && (tolower(s[1]) == 'i')
497 && (tolower(s[2]) == 'n')
498 && (tolower(s[3]) == 'f');
499 }
500
501
502
503 static inline bool LPFisFree(const char* s)
504 {
505 return (tolower(s[0]) == 'f')
506 && (tolower(s[1]) == 'r')
507 && (tolower(s[2]) == 'e')
508 && (tolower(s[3]) == 'e');
509 }
510
511
512
513 /// Read the next number and advance \p pos.
514 /** If only a sign is encountered, the number is assumed to be \c sign * 1.0. This routine will not catch malformatted
515 * numbers like .e10 !
516 */
517 template <class R>
518 static R LPFreadValue(char*& pos, SPxOut* spxout)
519 {
520 assert(LPFisValue(pos));
521
522 char tmp[SOPLEX_LPF_MAX_LINE_LEN];
523 const char* s = pos;
524 char* t;
525 R value = 1.0;
526 bool has_digits = false;
527 bool has_emptyexponent = false;
528
529 // 1. sign
530 if((*s == '+') || (*s == '-'))
531 s++;
532
533 // 2. Digits before the decimal dot
534 while((*s >= '0') && (*s <= '9'))
535 {
536 has_digits = true;
537 s++;
538 }
539
540 // 3. Decimal dot
541 if(*s == '.')
542 {
543 s++;
544
545 // 4. If there was a dot, possible digit behind it
546 while((*s >= '0') && (*s <= '9'))
547 {
548 has_digits = true;
549 s++;
550 }
551 }
552
553 // 5. Exponent
554 if(tolower(*s) == 'e')
555 {
556 has_emptyexponent = true;
557 s++;
558
559 // 6. Exponent sign
560 if((*s == '+') || (*s == '-'))
561 s++;
562
563 // 7. Exponent digits
564 while((*s >= '0') && (*s <= '9'))
565 {
566 has_emptyexponent = false;
567 s++;
568 }
569 }
570
571 assert(s != pos);
572
573 if(has_emptyexponent)
574 {
575 SPX_MSG_WARNING((*spxout), (*spxout) <<
576 "WLPFRD01 Warning: found empty exponent in LP file - check for forbidden variable names with initial 'e' or 'E'\n";
577 )
578 }
579
580 if(!has_digits)
581 value = (*pos == '-') ? -1.0 : 1.0;
582 else
583 {
584 for(t = tmp; pos != s; pos++)
585 *t++ = *pos;
586
587 *t = '\0';
588 value = atof(tmp);
589 }
590
591 pos += s - pos;
592
593 assert(pos == s);
594
595 SPxOut::debug(spxout, "DLPFRD01 LPFreadValue = {}\n", value);
596
597 if(LPFisSpace(*pos))
598 pos++;
599
600 return value;
601 }
602
603
604
605 /// Read the next column name from the input.
606 /** The name read is looked up and if not found \p emptycol
607 * is added to \p colset. \p pos is advanced behind the name.
608 * @return The Index of the named column.
609 */
610 template <class R>
611 static int LPFreadColName(char*& pos, NameSet* colnames, LPColSetBase<R>& colset,
612 const LPColBase<R>* emptycol, SPxOut* spxout)
613 {
614 assert(LPFisColName(pos));
615 assert(colnames != 0);
616
617 char name[SOPLEX_LPF_MAX_LINE_LEN];
618 const char* s = pos;
619 int i;
620 int colidx;
621
622 // These are the characters that are not allowed in a column name.
623 while((strchr("+-.<>= ", *s) == 0) && (*s != '\0'))
624 s++;
625
626 for(i = 0; pos != s; i++, pos++)
627 name[i] = *pos;
628
629 name[i] = '\0';
630
631 if((colidx = colnames->number(name)) < 0)
632 {
633 // We only add the name if we got an empty column.
634 if(emptycol == nullptr)
635 {
636 SPX_MSG_WARNING((*spxout), (*spxout) << "WLPFRD02 Unknown variable \"" << name << "\" ";)
637 }
638 else
639 {
640 colidx = colnames->num();
641 colnames->add(name);
642 colset.add(*emptycol);
643 }
644 }
645
646 SPxOut::debug(spxout, "DLPFRD03 LPFreadColName [{}] = {}\n", name, colidx);
647
648 if(LPFisSpace(*pos))
649 pos++;
650
651 return colidx;
652 }
653
654
655
656 /// Read the next <,>,=,==,<=,=<,>=,=> and advance \p pos.
657 static inline int LPFreadSense(char*& pos)
658 {
659 assert(LPFisSense(pos));
660
661 int sense = *pos++;
662
663 if((*pos == '<') || (*pos == '>'))
664 sense = *pos++;
665 else if(*pos == '=')
666 pos++;
667
668 if(LPFisSpace(*pos))
669 pos++;
670
671 return sense;
672 }
673
674
675
676 /// Is the \p keyword present in \p buf ? If yes, advance \p pos.
677 /** \p keyword should be lower case. It can contain optional sections which are enclosed in '[' ']' like "min[imize]".
678 */
679 static inline bool LPFhasKeyword(char*& pos, const char* keyword)
680 {
681 int i;
682 int k;
683
684 assert(keyword != 0);
685
686 for(i = 0, k = 0; keyword[i] != '\0'; i++, k++)
687 {
688 if(keyword[i] == '[')
689 {
690 i++;
691
692 // Here we assumed that we have a ']' for the '['.
693 while((tolower(pos[k]) == keyword[i]) && (pos[k] != '\0'))
694 {
695 k++;
696 i++;
697 }
698
699 while(keyword[i] != ']')
700 i++;
701
702 --k;
703 }
704 else
705 {
706 if(keyword[i] != tolower(pos[k]))
707 break;
708 }
709 }
710
711 // we have to be at the end of the keyword and the word found on the line also has to end here. Attention: The
712 // LPFisSense is a kludge to allow LPFhasKeyword also to process Inf[inity] keywords in the bounds section.
713 if(keyword[i] == '\0' && (pos[k] == '\0' || LPFisSpace(pos[k]) || LPFisSense(&pos[k])))
714 {
715 pos += k;
716
717 return true;
718 }
719
720 return false;
721 }
722
723
724
725 /// If \p buf start with "name:" store the name in \p rownames and advance \p pos.
726 static inline bool LPFhasRowName(char*& pos, NameSet* rownames)
727 {
728 const char* s = strchr(pos, ':');
729
730 if(s == 0)
731 return false;
732
733 int dcolpos = int(s - pos);
734
735 int end;
736 int srt;
737
738 // skip spaces between name and ":"
739 for(end = dcolpos - 1; end >= 0; end--)
740 if(pos[end] != ' ')
741 break;
742
743 // are there only spaces in front of the ":" ?
744 if(end < 0)
745 {
746 pos = &(pos[dcolpos + 1]);
747 return false;
748 }
749
750 // skip spaces in front of name
751 for(srt = end - 1; srt >= 0; srt--)
752 if(pos[srt] == ' ')
753 break;
754
755 // go back to the non-space character
756 srt++;
757
758 assert(srt <= end && pos[srt] != ' ');
759
760 char name[SOPLEX_LPF_MAX_LINE_LEN];
761 int i;
762 int k = 0;
763
764 for(i = srt; i <= end; i++)
765 name[k++] = pos[i];
766
767 name[k] = '\0';
768
769 if(rownames != 0)
770 rownames->add(name);
771
772 pos = &(pos[dcolpos + 1]);
773
774 return true;
775 }
776
777
778 template <class R>
779 static R LPFreadInfinity(char*& pos)
780 {
781 assert(LPFisInfinity(pos));
782
783 R sense = (*pos == '-') ? -1.0 : 1.0;
784
785 (void) LPFhasKeyword(++pos, "inf[inity]");
786
787 return sense * R(infinity);
788 }
789
790
791 /// Read LP in "CPLEX LP File Format".
792 /** The specification is taken from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 527.
793 *
794 * This routine should read (most?) valid LP format files. What it will not do, is find all cases where a file is ill
795 * formed. If this happens it may complain and read nothing or read "something".
796 *
797 * Problem: A line ending in '+' or '-' followed by a line starting with a number, will be regarded as an error.
798 *
799 * The reader will accept the keyword INT[egers] as a synonym for GEN[erals] which is an undocumented feature in CPLEX.
800 *
801 * A difference to the CPLEX reader, is that no name for the objective row is required.
802 *
803 * The manual says the maximum allowed line length is 255 characters, but CPLEX does not complain if the lines are
804 * longer.
805 *
806 * @return true if the file was read correctly
807 */
808 template <class R> inline
809 bool SPxLPBase<R>::readLPF(
810 std::istream& p_input, ///< input stream.
811 NameSet* p_rnames, ///< row names.
812 NameSet* p_cnames, ///< column names.
813 DIdxSet* p_intvars) ///< integer variables.
814 {
815 enum
816 {
817 START, OBJECTIVE, CONSTRAINTS, BOUNDS, INTEGERS, BINARIES
818 } section = START;
819
820 NameSet* rnames; ///< row names.
821 NameSet* cnames; ///< column names.
822
823 LPColSetBase<R> cset; ///< the set of columns read.
824 LPRowSetBase<R> rset; ///< the set of rows read.
825 LPColBase<R> emptycol; ///< reusable empty column.
826 LPRowBase<R> row; ///< last assembled row.
(1) Event start: |
Starting defect path here. |
827 DSVectorBase<R> vec; ///< last assembled vector (from row).
828
829 R val = 1.0;
830 int colidx;
831 int sense = 0;
832
833 int lineno = 0;
834 bool unnamed = true;
835 bool finished = false;
836 bool other;
837 bool have_value = true;
838 int i;
839 int k;
840 int buf_size;
841 int buf_pos;
842 char* buf = NULL;
843 char* tmp = NULL;
844 char* line = NULL;
845 char* s;
846 char* pos;
847 char* pos_old = 0;
848
(2) Event cond_true: |
Condition "p_cnames", taking true branch. |
849 if(p_cnames)
(3) Event if_fallthrough: |
Falling through to end of if statement. |
850 cnames = p_cnames;
851 else
852 {
853 cnames = 0;
854 spx_alloc(cnames);
855 cnames = new(cnames) NameSet();
(4) Event if_end: |
End of if statement. |
856 }
857
858 cnames->clear();
859
(5) Event cond_true: |
Condition "p_rnames", taking true branch. |
860 if(p_rnames)
(6) Event if_fallthrough: |
Falling through to end of if statement. |
861 rnames = p_rnames;
862 else
863 {
864 try
865 {
866 rnames = 0;
867 spx_alloc(rnames);
868 rnames = new(rnames) NameSet();
869 }
870 catch(const SPxMemoryException& x)
871 {
872 if(!p_cnames)
873 {
874 cnames->~NameSet();
875 spx_free(cnames);
876 }
877
878 throw x;
879 }
(7) Event if_end: |
End of if statement. |
880 }
881
882 rnames->clear();
883
884 SPxLPBase<R>::clear(); // clear the LP.
885
886 //--------------------------------------------------------------------------
887 //--- Main Loop
888 //--------------------------------------------------------------------------
889 buf_size = SOPLEX_LPF_MAX_LINE_LEN;
890 spx_alloc(buf, buf_size);
891 spx_alloc(tmp, buf_size);
892 spx_alloc(line, buf_size);
893 buf[0] = '\0';
894
895 for(;;)
896 {
897 // 0. Read a line from the file.
898 buf_pos = 0;
899
(9) Event noescape: |
Resource "buf + buf_pos" is not freed or pointed-to in "getline". [Note: The source code implementation of the function has been overridden by a builtin model.] |
(10) Event cond_true: |
Condition "!p_input->getline(buf + buf_pos, buf_size - buf_pos)", taking true branch. |
(41) Event noescape: |
Resource "buf + buf_pos" is not freed or pointed-to in "getline". [Note: The source code implementation of the function has been overridden by a builtin model.] |
(42) Event cond_false: |
Condition "!p_input->getline(buf + buf_pos, buf_size - buf_pos)", taking false branch. |
Also see events: |
[alloc_arg][noescape][var_assign][noescape][var_assign][identity_transfer][noescape][var_assign][leaked_storage][leaked_storage] |
900 while(!p_input.getline(buf + buf_pos, buf_size - buf_pos))
901 {
902 p_input.clear();
903
904 if(strlen(buf) == (size_t) buf_size - 1)
905 {
906 buf_pos = buf_size - 1;
907 buf_size = buf_size + SOPLEX_LPF_MAX_LINE_LEN;
908
909 if(buf_size >= INT_MAX)
910 {
911 SPX_MSG_ERROR(std::cerr << "ELPFRD16 Line longer than INT_MAX" << std::endl;)
912 finished = true;
913 break;
914 }
915
916 spx_realloc(buf, buf_size);
917 }
918 else
(13) Event else_branch: |
Reached else branch. |
919 {
920 SPX_MSG_ERROR(std::cerr << "ELPFRD07 No 'End' marker found" << std::endl;)
921 finished = true;
(14) Event break: |
Breaking from loop. |
922 break;
923 }
(15) Event loop_end: |
Reached end of loop. |
(43) Event loop_end: |
Reached end of loop. |
924 }
925
(16) Event cond_true: |
Condition "(size_t)buf_size > 8UL /* sizeof (tmp) */", taking true branch. |
(44) Event cond_true: |
Condition "(size_t)buf_size > 8UL /* sizeof (tmp) */", taking true branch. |
926 if((size_t) buf_size > sizeof(tmp))
927 {
928 spx_realloc(tmp, buf_size);
929 spx_realloc(line, buf_size);
930 }
931
932 lineno++;
933 i = 0;
934 pos = buf;
935
936 SPxOut::debug(spxout, "DLPFRD08 Reading line {} (pos={})\n", lineno, pos);
937
938 // 1. Remove comments.
(18) Event noescape: |
Resource "buf" is not freed or pointed-to in "strchr". [Note: The source code implementation of the function has been overridden by a builtin model.] |
(19) Event cond_false: |
Condition "NULL != (s = strchr(buf, '\\'))", taking false branch. |
(46) Event identity_transfer: |
Passing "buf" as argument 1 to function "strchr", which returns an offset off that argument. [Note: The source code implementation of the function has been overridden by a builtin model.] |
(47) Event noescape: |
Resource "buf" is not freed or pointed-to in "strchr". [Note: The source code implementation of the function has been overridden by a builtin model.] |
(48) Event var_assign: |
Assigning: "s" = storage returned from "strchr(buf, 92)". |
(49) Event cond_true: |
Condition "NULL != (s = strchr(buf, '\\'))", taking true branch. |
Also see events: |
[alloc_arg][noescape][noescape][var_assign][noescape][var_assign][leaked_storage][leaked_storage] |
939 if(0 != (s = strchr(buf, '\\')))
(20) Event if_end: |
End of if statement. |
940 * s = '\0';
941
942 // 2. Look for keywords.
(21) Event cond_true: |
Condition "section == START", taking true branch. |
(50) Event cond_false: |
Condition "section == START", taking false branch. |
943 if(section == START)
944 {
(22) Event cond_true: |
Condition "soplex::LPFhasKeyword(pos, "max[imize]")", taking true branch. |
945 if(LPFhasKeyword(pos, "max[imize]"))
946 {
947 changeSense(SPxLPBase<R>::MAXIMIZE);
948 section = OBJECTIVE;
(23) Event if_fallthrough: |
Falling through to end of if statement. |
949 }
950 else if(LPFhasKeyword(pos, "min[imize]"))
951 {
952 changeSense(SPxLPBase<R>::MINIMIZE);
953 section = OBJECTIVE;
(24) Event if_end: |
End of if statement. |
954 }
(25) Event if_fallthrough: |
Falling through to end of if statement. |
955 }
(51) Event else_branch: |
Reached else branch. |
(52) Event cond_true: |
Condition "section == OBJECTIVE", taking true branch. |
956 else if(section == OBJECTIVE)
957 {
(53) Event cond_true: |
Condition "soplex::LPFhasKeyword(pos, "s[ubject][ ]t[o]")", taking true branch. |
958 if(LPFhasKeyword(pos, "s[ubject][ ]t[o]")
959 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
960 || LPFhasKeyword(pos, "s[.][ ]t[.]")
961 || LPFhasKeyword(pos, "lazy con[straints]"))
962 {
963 // store objective vector
(54) Event cond_true: |
Condition "j >= 0", taking true branch. |
(56) Event loop_begin: |
Jumped back to beginning of loop. |
(57) Event cond_false: |
Condition "j >= 0", taking false branch. |
964 for(int j = vec.size() - 1; j >= 0; --j)
(55) Event loop: |
Jumping back to the beginning of the loop. |
(58) Event loop_end: |
Reached end of loop. |
965 cset.maxObj_w(vec.index(j)) = vec.value(j);
966
967 // multiplication with -1 for minimization is done below
968 vec.clear();
969 have_value = true;
970 val = 1.0;
971 section = CONSTRAINTS;
972 }
(59) Event if_fallthrough: |
Falling through to end of if statement. |
973 }
974 else if(section == CONSTRAINTS &&
975 (LPFhasKeyword(pos, "s[ubject][ ]t[o]")
976 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
977 || LPFhasKeyword(pos, "s[.][ ]t[.]")))
978 {
979 have_value = true;
980 val = 1.0;
981 }
982 else
983 {
984 if(LPFhasKeyword(pos, "lazy con[straints]"))
985 ;
986 else if(LPFhasKeyword(pos, "bound[s]"))
987 section = BOUNDS;
988 else if(LPFhasKeyword(pos, "bin[ary]"))
989 section = BINARIES;
990 else if(LPFhasKeyword(pos, "bin[aries]"))
991 section = BINARIES;
992 else if(LPFhasKeyword(pos, "gen[erals]"))
993 section = INTEGERS;
994 else if(LPFhasKeyword(pos, "int[egers]")) // this is undocumented
995 section = INTEGERS;
996 else if(LPFhasKeyword(pos, "end"))
997 {
998 finished = true;
999 break;
1000 }
1001 else if(LPFhasKeyword(pos, "s[ubject][ ]t[o]") // second time
1002 || LPFhasKeyword(pos, "s[uch][ ]t[hat]")
1003 || LPFhasKeyword(pos, "s[.][ ]t[.]")
1004 || LPFhasKeyword(pos, "lazy con[straints]"))
1005 {
1006 // In principle this has to checked for all keywords above,
1007 // otherwise we just ignore any half finished constraint
1008 if(have_value)
1009 goto syntax_error;
1010
1011 have_value = true;
1012 val = 1.0;
1013 }
(26) Event if_end: |
End of if statement. |
(60) Event if_end: |
End of if statement. |
1014 }
1015
1016 // 3a. Look for row names in objective and drop it.
(27) Event cond_true: |
Condition "section == OBJECTIVE", taking true branch. |
(61) Event cond_false: |
Condition "section == OBJECTIVE", taking false branch. |
1017 if(section == OBJECTIVE)
(62) Event if_end: |
End of if statement. |
1018 LPFhasRowName(pos, 0);
1019
1020 // 3b. Look for row name in constraint and store it.
(28) Event cond_false: |
Condition "section == CONSTRAINTS", taking false branch. |
(63) Event cond_true: |
Condition "section == CONSTRAINTS", taking true branch. |
1021 if(section == CONSTRAINTS)
(64) Event cond_true: |
Condition "soplex::LPFhasRowName(pos, rnames)", taking true branch. |
1022 if(LPFhasRowName(pos, rnames))
(29) Event if_end: |
End of if statement. |
1023 unnamed = false;
1024
1025 // 4a. Remove initial spaces.
(30) Event cond_false: |
Condition "soplex::LPFisSpace(pos[i])", taking false branch. |
(65) Event cond_false: |
Condition "soplex::LPFisSpace(pos[i])", taking false branch. |
1026 while(LPFisSpace(pos[i]))
(31) Event loop_end: |
Reached end of loop. |
(66) Event loop_end: |
Reached end of loop. |
1027 i++;
1028
1029 // 4b. remove spaces if they do not appear before the name of a vaiable.
(32) Event cond_true: |
Condition "pos[i] != '\0'", taking true branch. |
(35) Event loop_begin: |
Jumped back to beginning of loop. |
(36) Event cond_false: |
Condition "pos[i] != '\0'", taking false branch. |
(67) Event cond_true: |
Condition "pos[i] != '\0'", taking true branch. |
(70) Event loop_begin: |
Jumped back to beginning of loop. |
(71) Event cond_false: |
Condition "pos[i] != '\0'", taking false branch. |
1030 for(k = 0; pos[i] != '\0'; i++)
(33) Event cond_true: |
Condition "!soplex::LPFisSpace(pos[i])", taking true branch. |
(68) Event cond_true: |
Condition "!soplex::LPFisSpace(pos[i])", taking true branch. |
1031 if(!LPFisSpace(pos[i]) || LPFisColName(&pos[i + 1]))
(34) Event loop: |
Jumping back to the beginning of the loop. |
(37) Event loop_end: |
Reached end of loop. |
(69) Event loop: |
Jumping back to the beginning of the loop. |
(72) Event loop_end: |
Reached end of loop. |
1032 tmp[k++] = pos[i];
1033
1034 tmp[k] = '\0';
1035
1036 // 5. Is this an empty line ?
(38) Event cond_true: |
Condition "tmp[0] == '\0'", taking true branch. |
(73) Event cond_false: |
Condition "tmp[0] == '\0'", taking false branch. |
1037 if(tmp[0] == '\0')
(39) Event continue: |
Continuing loop. |
(74) Event if_end: |
End of if statement. |
1038 continue;
1039
1040 // 6. Collapse sequences of '+' and '-'. e.g ++---+ => -
(75) Event cond_true: |
Condition "tmp[i] != '\0'", taking true branch. |
(81) Event loop_begin: |
Jumped back to beginning of loop. |
(82) Event cond_false: |
Condition "tmp[i] != '\0'", taking false branch. |
1041 for(i = 0, k = 0; tmp[i] != '\0'; i++)
1042 {
(76) Event cond_true: |
Condition "tmp[i] == '+'", taking true branch. |
(77) Event cond_false: |
Condition "tmp[i + 1] == '+'", taking false branch. |
(78) Event cond_false: |
Condition "tmp[i + 1] == '-'", taking false branch. |
1043 while(((tmp[i] == '+') || (tmp[i] == '-')) && ((tmp[i + 1] == '+') || (tmp[i + 1] == '-')))
1044 {
1045 if(tmp[i++] == '-')
1046 tmp[i] = (tmp[i] == '-') ? '+' : '-';
(79) Event loop_end: |
Reached end of loop. |
1047 }
1048
1049 line[k++] = tmp[i];
(80) Event loop: |
Jumping back to the beginning of the loop. |
(83) Event loop_end: |
Reached end of loop. |
1050 }
1051
1052 line[k] = '\0';
1053
1054 //-----------------------------------------------------------------------
1055 //--- Line processing loop
1056 //-----------------------------------------------------------------------
1057 pos = line;
1058
1059 SPxOut::debug(spxout, "DLPFRD09 pos={}\n", pos);
1060
1061 // 7. We have something left to process.
(84) Event cond_true: |
Condition "pos != NULL", taking true branch. |
(85) Event cond_true: |
Condition "*pos != '\0'", taking true branch. |
1062 while((pos != 0) && (*pos != '\0'))
1063 {
1064 // remember our position, so we are sure we make progress.
1065 pos_old = pos;
1066
1067 // now process the sections
(86) Event switch: |
Switch case value "CONSTRAINTS". |
1068 switch(section)
1069 {
1070 case OBJECTIVE:
1071 if(LPFisValue(pos))
1072 {
1073 R pre_sign = 1.0;
1074
1075 /* Already having here a value could only result from being the first number in a constraint, or a sign
1076 * '+' or '-' as last token on the previous line.
1077 */
1078 if(have_value)
1079 {
1080 if(NE(spxAbs(val), R(1.0), this->tolerances()->epsilon()))
1081 goto syntax_error;
1082
1083 if(EQ(val, R(-1.0), this->tolerances()->epsilon()))
1084 pre_sign = val;
1085 }
1086
1087 /* non-finite coefficients are not allowed in the objective */
1088 if(LPFisInfinity(pos))
1089 goto syntax_error;
1090
1091 have_value = true;
1092 val = LPFreadValue<R>(pos, spxout) * pre_sign;
1093 }
1094
1095 if(*pos == '\0')
1096 continue;
1097
1098 if(!have_value || !LPFisColName(pos))
1099 goto syntax_error;
1100
1101 have_value = false;
1102 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout);
1103 vec.add(colidx, val);
1104 break;
1105
(87) Event switch_case: |
Reached case "CONSTRAINTS". |
1106 case CONSTRAINTS:
(88) Event cond_false: |
Condition "soplex::LPFisValue(pos)", taking false branch. |
1107 if(LPFisValue(pos))
1108 {
1109 R pre_sign = 1.0;
1110
1111 /* Already having here a value could only result from being the first number in a constraint, or a sign
1112 * '+' or '-' as last token on the previous line.
1113 */
1114 if(have_value)
1115 {
1116 if(NE(spxAbs(val), R(1.0), this->tolerances()->epsilon()))
1117 goto syntax_error;
1118
1119 if(EQ(val, R(-1.0), this->tolerances()->epsilon()))
1120 pre_sign = val;
1121 }
1122
1123 if(LPFisInfinity(pos))
1124 {
1125 /* non-finite coefficients are not allowed */
1126 if(sense == 0)
1127 goto syntax_error;
1128
1129 val = LPFreadInfinity<R>(pos) * pre_sign;
1130 }
1131 else
1132 val = LPFreadValue<R>(pos, spxout) * pre_sign;
1133
1134 have_value = true;
1135
1136 if(sense != 0)
1137 {
1138 if(sense == '<')
1139 {
1140 row.setLhs(R(-infinity));
1141 row.setRhs(val);
1142 }
1143 else if(sense == '>')
1144 {
1145 row.setLhs(val);
1146 row.setRhs(R(infinity));
1147 }
1148 else
1149 {
1150 assert(sense == '=');
1151
1152 row.setLhs(val);
1153 row.setRhs(val);
1154 }
1155
1156 row.setRowVector(vec);
1157 rset.add(row);
1158 vec.clear();
1159
1160 if(!unnamed)
1161 unnamed = true;
1162 else
1163 {
1164 char name[16];
1165 spxSnprintf(name, 16, "C%d", rset.num());
1166 rnames->add(name);
1167 }
1168
1169 have_value = true;
1170 val = 1.0;
1171 sense = 0;
1172 pos = 0;
1173 // next line
1174 continue;
1175 }
(89) Event if_end: |
End of if statement. |
1176 }
1177
(90) Event cond_false: |
Condition "*pos == '\0'", taking false branch. |
1178 if(*pos == '\0')
(91) Event if_end: |
End of if statement. |
1179 continue;
1180
(92) Event cond_true: |
Condition "have_value", taking true branch. |
1181 if(have_value)
1182 {
(93) Event cond_false: |
Condition "soplex::LPFisColName(pos)", taking false branch. |
1183 if(LPFisColName(pos))
1184 {
1185 colidx = LPFreadColName(pos, cnames, cset, &emptycol, spxout);
1186
1187 if(val != 0.0)
1188 {
1189 // Do we have this index already in the row?
1190 int n = vec.pos(colidx);
1191
1192 // if not, add it
1193 if(n < 0)
1194 vec.add(colidx, val);
1195 // if yes, add them up and remove the element if it amounts to zero
1196 else
1197 {
1198 assert(vec.index(n) == colidx);
1199
1200 val += vec.value(n);
1201
1202 if(val == 0.0)
1203 vec.remove(n);
1204 else
1205 vec.value(n) = val;
1206
1207 assert(cnames->has(colidx));
1208
1209 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD10 Duplicate index "
1210 << (*cnames)[colidx]
1211 << " in line " << lineno
1212 << std::endl;)
1213 }
1214 }
1215
1216 have_value = false;
1217 }
1218 else
(94) Event else_branch: |
Reached else branch. |
1219 {
1220 // We have a row like c1: <= 5 with no variables. We can not handle 10 <= 5; issue a syntax error.
(95) Event cond_false: |
Condition "val != 1.", taking false branch. |
1221 if(val != 1.0)
(96) Event if_end: |
End of if statement. |
1222 goto syntax_error;
1223
1224 // If the next thing is not the sense we give up also.
(97) Event cond_true: |
Condition "!soplex::LPFisSense(pos)", taking true branch. |
1225 if(!LPFisSense(pos))
(98) Event goto: |
Jumping to label "syntax_error". |
1226 goto syntax_error;
1227
1228 have_value = false;
1229 }
1230 }
1231
1232 assert(!have_value);
1233
1234 if(LPFisSense(pos))
1235 sense = LPFreadSense(pos);
1236
1237 break;
1238
1239 case BOUNDS:
1240 other = false;
1241 sense = 0;
1242
1243 if(LPFisValue(pos))
1244 {
1245 val = LPFisInfinity(pos) ? LPFreadInfinity<R>(pos) : LPFreadValue<R>(pos, spxout);
1246
1247 if(!LPFisSense(pos))
1248 goto syntax_error;
1249
1250 sense = LPFreadSense(pos);
1251 other = true;
1252 }
1253
1254 if(!LPFisColName(pos))
1255 goto syntax_error;
1256
1257 if((colidx = LPFreadColName<R>(pos, cnames, cset, nullptr, spxout)) < 0)
1258 {
1259 SPX_MSG_WARNING((*this->spxout), (*this->spxout) << "WLPFRD11 in Bounds section line "
1260 << lineno << " ignored" << std::endl;)
1261 *pos = '\0';
1262 continue;
1263 }
1264
1265 if(sense)
1266 {
1267 if(sense == '<')
1268 cset.lower_w(colidx) = val;
1269 else if(sense == '>')
1270 cset.upper_w(colidx) = val;
1271 else
1272 {
1273 assert(sense == '=');
1274 cset.lower_w(colidx) = val;
1275 cset.upper_w(colidx) = val;
1276 }
1277 }
1278
1279 if(LPFisFree(pos))
1280 {
1281 cset.lower_w(colidx) = R(-infinity);
1282 cset.upper_w(colidx) = R(infinity);
1283 other = true;
1284 pos += 4; // set position after the word "free"
1285 }
1286 else if(LPFisSense(pos))
1287 {
1288 sense = LPFreadSense(pos);
1289 other = true;
1290
1291 if(!LPFisValue(pos))
1292 goto syntax_error;
1293
1294 val = LPFisInfinity(pos) ? LPFreadInfinity<R>(pos) : LPFreadValue<R>(pos, spxout);
1295
1296 if(sense == '<')
1297 cset.upper_w(colidx) = val;
1298 else if(sense == '>')
1299 cset.lower_w(colidx) = val;
1300 else
1301 {
1302 assert(sense == '=');
1303 cset.lower_w(colidx) = val;
1304 cset.upper_w(colidx) = val;
1305 }
1306 }
1307
1308 /* Do we have only a single column name in the input line? We could ignore this savely, but it is probably
1309 * a sign of some other error.
1310 */
1311 if(!other)
1312 goto syntax_error;
1313
1314 break;
1315
1316 case BINARIES:
1317 case INTEGERS:
1318 if((colidx = LPFreadColName<R>(pos, cnames, cset, 0, spxout)) < 0)
1319 {
1320 SPX_MSG_WARNING((*this->spxout),
1321 (*this->spxout) << "WLPFRD12 in Binary/General section line " << lineno
1322 << " ignored" << std::endl;)
1323 }
1324 else
1325 {
1326 if(section == BINARIES)
1327 {
1328 if(cset.lower(colidx) < 0.0)
1329 {
1330 cset.lower_w(colidx) = 0.0;
1331 }
1332
1333 if(cset.upper(colidx) > 1.0)
1334 {
1335 cset.upper_w(colidx) = 1.0;
1336 }
1337 }
1338
1339 if(p_intvars != 0)
1340 p_intvars->addIdx(colidx);
1341 }
1342
1343 break;
1344
1345 case START:
1346 SPX_MSG_ERROR(std::cerr << "ELPFRD13 This seems to be no LP format file" << std::endl;)
1347 goto syntax_error;
1348
1349 default:
1350 throw SPxInternalCodeException("XLPFRD01 This should never happen.");
1351 }
1352
1353 if(pos == pos_old)
1354 goto syntax_error;
1355 }
(40) Event loop: |
Looping back. |
1356 }
1357
1358 assert(isConsistent());
1359
1360 addCols(cset);
1361 assert(isConsistent());
1362
1363 addRows(rset);
1364 assert(isConsistent());
1365
(99) Event label: |
Reached label "syntax_error". |
1366 syntax_error:
1367
(100) Event cond_true: |
Condition "finished", taking true branch. |
1368 if(finished)
1369 {
(101) Event cond_true: |
Condition "this->spxout != NULL", taking true branch. |
(102) Event cond_true: |
Condition "soplex::SPxOut::INFO2 <= this->spxout->getVerbosity()", taking true branch. |
1370 SPX_MSG_INFO2((*this->spxout), (*this->spxout) << "Finished reading " << lineno << " lines" <<
1371 std::endl;)
(103) Event if_fallthrough: |
Falling through to end of if statement. |
1372 }
1373 else
(104) Event if_end: |
End of if statement. |
1374 SPX_MSG_ERROR(std::cerr << "ELPFRD15 Syntax error in line " << lineno << std::endl;)
1375
(105) Event cond_false: |
Condition "p_cnames == NULL", taking false branch. |
1376 if(p_cnames == 0)
(106) Event if_end: |
End of if statement. |
1377 spx_free(cnames);
1378
(107) Event cond_false: |
Condition "p_rnames == NULL", taking false branch. |
1379 if(p_rnames == 0)
(108) Event if_end: |
End of if statement. |
1380 spx_free(rnames);
1381
1382 return finished;
1383 }
1384
1385
1386
1387 // ---------------------------------------------------------------------------------------------------------------------
1388 // Specialization for reading MPS format
1389 // ---------------------------------------------------------------------------------------------------------------------
1390
1391 /// Process NAME section.
1392 static inline void MPSreadName(MPSInput& mps, SPxOut* spxout)
1393 {
1394 do
1395 {
1396 // This has to be the Line with the NAME section.
1397 if(!mps.readLine() || (mps.field0() == 0) || strcmp(mps.field0(), "NAME"))
1398 break;
1399
1400 // Sometimes the name is omitted.
1401 mps.setProbName((mps.field1() == 0) ? "_MPS_" : mps.field1());
1402
1403 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD01 Problem name : " << mps.probName() << std::endl;)
1404
1405 // This has to be a new section
1406 if(!mps.readLine() || (mps.field0() == 0))
1407 break;
1408
1409 if(!strcmp(mps.field0(), "ROWS"))
1410 mps.setSection(MPSInput::ROWS);
1411 else if(!strncmp(mps.field0(), "OBJSEN", 6))
1412 mps.setSection(MPSInput::OBJSEN);
1413 else if(!strcmp(mps.field0(), "OBJNAME"))
1414 mps.setSection(MPSInput::OBJNAME);
1415 else
1416 break;
1417
1418 return;
1419 }
1420 while(false);
1421
1422 mps.syntaxError();
1423 }
1424
1425
1426
1427 /// Process OBJSEN section. This Section is an ILOG extension.
1428 static inline void MPSreadObjsen(MPSInput& mps)
1429 {
1430 do
1431 {
1432 // This has to be the Line with MIN or MAX.
1433 if(!mps.readLine() || (mps.field1() == 0))
1434 break;
1435
1436 if(!strcmp(mps.field1(), "MIN"))
1437 mps.setObjSense(MPSInput::MINIMIZE);
1438 else if(!strcmp(mps.field1(), "MAX"))
1439 mps.setObjSense(MPSInput::MAXIMIZE);
1440 else
1441 break;
1442
1443 // Look for ROWS or OBJNAME Section
1444 if(!mps.readLine() || (mps.field0() == 0))
1445 break;
1446
1447 if(!strcmp(mps.field0(), "ROWS"))
1448 mps.setSection(MPSInput::ROWS);
1449 else if(!strcmp(mps.field0(), "OBJNAME"))
1450 mps.setSection(MPSInput::OBJNAME);
1451 else
1452 break;
1453
1454 return;
1455 }
1456 while(false);
1457
1458 mps.syntaxError();
1459 }
1460
1461
1462
1463 /// Process OBJNAME section. This Section is an ILOG extension.
1464 static inline void MPSreadObjname(MPSInput& mps)
1465 {
1466 do
1467 {
1468 // This has to be the Line with the name.
1469 if(!mps.readLine() || (mps.field1() == 0))
1470 break;
1471
1472 mps.setObjName(mps.field1());
1473
1474 // Look for ROWS Section
1475 if(!mps.readLine() || (mps.field0() == 0))
1476 break;
1477
1478 if(strcmp(mps.field0(), "ROWS"))
1479 break;
1480
1481 mps.setSection(MPSInput::ROWS);
1482
1483 return;
1484 }
1485 while(false);
1486
1487 mps.syntaxError();
1488 }
1489
1490
1491
1492 /// Process ROWS section.
1493 template <class R>
1494 static void MPSreadRows(MPSInput& mps, LPRowSetBase<R>& rset, NameSet& rnames, SPxOut* spxout)
1495 {
1496 LPRowBase<R> row;
1497
1498 while(mps.readLine())
1499 {
1500 if(mps.field0() != 0)
1501 {
1502 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD02 Objective name : " << mps.objName() << std::endl;)
1503
1504 if(strcmp(mps.field0(), "COLUMNS"))
1505 break;
1506
1507 mps.setSection(MPSInput::COLUMNS);
1508
1509 return;
1510 }
1511
1512 if((mps.field1() == 0) || (mps.field2() == 0))
1513 break;
1514
1515 if(*mps.field1() == 'N')
1516 {
1517 if(*mps.objName() == '\0')
1518 mps.setObjName(mps.field2());
1519 }
1520 else
1521 {
1522 if(rnames.has(mps.field2()))
1523 break;
1524
1525 rnames.add(mps.field2());
1526
1527 switch(*mps.field1())
1528 {
1529 case 'G':
1530 row.setLhs(0.0);
1531 row.setRhs(R(infinity));
1532 break;
1533
1534 case 'E':
1535 row.setLhs(0.0);
1536 row.setRhs(0.0);
1537 break;
1538
1539 case 'L':
1540 row.setLhs(R(-infinity));
1541 row.setRhs(0.0);
1542 break;
1543
1544 default:
1545 mps.syntaxError();
1546 return;
1547 }
1548
1549 rset.add(row);
1550 }
1551
1552 assert((*mps.field1() == 'N') || (rnames.number(mps.field2()) == rset.num() - 1));
1553 }
1554
1555 mps.syntaxError();
1556 }
1557
1558
1559
1560 /// Process COLUMNS section.
1561 template <class R>
1562 static void MPSreadCols(MPSInput& mps, const LPRowSetBase<R>& rset, const NameSet& rnames,
1563 LPColSetBase<R>& cset, NameSet& cnames, DIdxSet* intvars)
1564 {
1565 R val;
1566 int idx;
1567 char colname[MPSInput::MAX_LINE_LEN] = { '\0' };
1568 LPColBase<R> col(rset.num());
1569 DSVectorBase<R> vec;
1570
1571 col.setObj(0.0);
1572 vec.clear();
1573
1574 while(mps.readLine())
1575 {
1576 if(mps.field0() != 0)
1577 {
1578 if(strcmp(mps.field0(), "RHS"))
1579 break;
1580
1581 if(colname[0] != '\0')
1582 {
1583 col.setColVector(vec);
1584 cset.add(col);
1585 }
1586
1587 mps.setSection(MPSInput::RHS);
1588
1589 return;
1590 }
1591
1592 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1593 break;
1594
1595 // new column?
1596 if(strcmp(colname, mps.field1()))
1597 {
1598 // first column?
1599 if(colname[0] != '\0')
1600 {
1601 col.setColVector(vec);
1602 cset.add(col);
1603 }
1604
1605 // save copy of string (make sure string ends with \0)
1606 spxSnprintf(colname, MPSInput::MAX_LINE_LEN - 1, "%s", mps.field1());
1607 colname[MPSInput::MAX_LINE_LEN - 1] = '\0';
1608
1609 int ncnames = cnames.size();
1610 cnames.add(colname);
1611
1612 // check whether the new name is unique wrt previous column names
1613 if(cnames.size() <= ncnames)
1614 {
1615 SPX_MSG_ERROR(std::cerr << "ERROR in COLUMNS: duplicate column name or not column-wise ordering" <<
1616 std::endl;)
1617 break;
1618 }
1619
1620 vec.clear();
1621 col.setObj(0.0);
1622 col.setLower(0.0);
1623 col.setUpper(R(infinity));
1624
1625 if(mps.isInteger())
1626 {
1627 assert(cnames.number(colname) == cset.num());
1628
1629 if(intvars != 0)
1630 intvars->addIdx(cnames.number(colname));
1631
1632 // for Integer variable the default bounds are 0/1
1633 col.setUpper(1.0);
1634 }
1635 }
1636
1637 val = atof(mps.field3());
1638
1639 if(!strcmp(mps.field2(), mps.objName()))
1640 col.setObj(val);
1641 else
1642 {
1643 if((idx = rnames.number(mps.field2())) < 0)
1644 mps.entryIgnored("Column", mps.field1(), "row", mps.field2());
1645 else if(val != 0.0)
1646 vec.add(idx, val);
1647 }
1648
1649 if(mps.field5() != 0)
1650 {
1651 assert(mps.field4() != 0);
1652
1653 val = atof(mps.field5());
1654
1655 if(!strcmp(mps.field4(), mps.objName()))
1656 col.setObj(val);
1657 else
1658 {
1659 if((idx = rnames.number(mps.field4())) < 0)
1660 mps.entryIgnored("Column", mps.field1(), "row", mps.field4());
1661 else if(val != 0.0)
1662 vec.add(idx, val);
1663 }
1664 }
1665 }
1666
1667 mps.syntaxError();
1668 }
1669
1670
1671
1672 /// Process RHS section.
1673 template <class R>
1674 static void MPSreadRhs(MPSInput& mps, LPRowSetBase<R>& rset, const NameSet& rnames, SPxOut* spxout)
1675 {
1676 char rhsname[MPSInput::MAX_LINE_LEN] = { '\0' };
1677 char addname[MPSInput::MAX_LINE_LEN] = { '\0' };
1678 int idx;
1679 R val;
1680
1681 while(mps.readLine())
1682 {
1683 if(mps.field0() != 0)
1684 {
1685 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD03 RHS name : " << rhsname << std::endl;);
1686
1687 if(!strcmp(mps.field0(), "RANGES"))
1688 mps.setSection(MPSInput::RANGES);
1689 else if(!strcmp(mps.field0(), "BOUNDS"))
1690 mps.setSection(MPSInput::BOUNDS);
1691 else if(!strcmp(mps.field0(), "ENDATA"))
1692 mps.setSection(MPSInput::ENDATA);
1693 else
1694 break;
1695
1696 return;
1697 }
1698
1699 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0)))
1700 mps.insertName("_RHS_");
1701
1702 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1703 break;
1704
1705 if(*rhsname == '\0')
1706 spxSnprintf(rhsname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1707
1708 if(strcmp(rhsname, mps.field1()))
1709 {
1710 if(strcmp(addname, mps.field1()))
1711 {
1712 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN);
1713 spxSnprintf(addname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1714 SPX_MSG_INFO3((*spxout), (*spxout) << "IMPSRD07 RHS ignored : " << addname << std::endl);
1715 }
1716 }
1717 else
1718 {
1719 if((idx = rnames.number(mps.field2())) < 0)
1720 mps.entryIgnored("RHS", mps.field1(), "row", mps.field2());
1721 else
1722 {
1723 val = atof(mps.field3());
1724
1725 // LE or EQ
1726 if(rset.rhs(idx) < R(infinity))
1727 rset.rhs_w(idx) = val;
1728
1729 // GE or EQ
1730 if(rset.lhs(idx) > R(-infinity))
1731 rset.lhs_w(idx) = val;
1732 }
1733
1734 if(mps.field5() != 0)
1735 {
1736 if((idx = rnames.number(mps.field4())) < 0)
1737 mps.entryIgnored("RHS", mps.field1(), "row", mps.field4());
1738 else
1739 {
1740 val = atof(mps.field5());
1741
1742 // LE or EQ
1743 if(rset.rhs(idx) < R(infinity))
1744 rset.rhs_w(idx) = val;
1745
1746 // GE or EQ
1747 if(rset.lhs(idx) > R(-infinity))
1748 rset.lhs_w(idx) = val;
1749 }
1750 }
1751 }
1752 }
1753
1754 mps.syntaxError();
1755 }
1756
1757
1758
1759 /// Process RANGES section.
1760 template <class R>
1761 static void MPSreadRanges(MPSInput& mps, LPRowSetBase<R>& rset, const NameSet& rnames,
1762 SPxOut* spxout)
1763 {
1764 char rngname[MPSInput::MAX_LINE_LEN] = { '\0' };
1765 int idx;
1766 R val;
1767
1768 while(mps.readLine())
1769 {
1770 if(mps.field0() != 0)
1771 {
1772 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD04 Range name : " << rngname << std::endl;);
1773
1774 if(!strcmp(mps.field0(), "BOUNDS"))
1775 mps.setSection(MPSInput::BOUNDS);
1776 else if(!strcmp(mps.field0(), "ENDATA"))
1777 mps.setSection(MPSInput::ENDATA);
1778 else
1779 break;
1780
1781 return;
1782 }
1783
1784 if(((mps.field2() != 0) && (mps.field3() == 0)) || ((mps.field4() != 0) && (mps.field5() == 0)))
1785 mps.insertName("_RNG_");
1786
1787 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1788 break;
1789
1790 if(*rngname == '\0')
1791 {
1792 assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN);
1793 spxSnprintf(rngname, MPSInput::MAX_LINE_LEN, "%s", mps.field1());
1794 }
1795
1796 /* The rules are:
1797 * Row Sign LHS RHS
1798 * ----------------------------------------
1799 * G +/- rhs rhs + |range|
1800 * L +/- rhs - |range| rhs
1801 * E + rhs rhs + range
1802 * E - rhs + range rhs
1803 * ----------------------------------------
1804 */
1805 if(!strcmp(rngname, mps.field1()))
1806 {
1807 if((idx = rnames.number(mps.field2())) < 0)
1808 mps.entryIgnored("Range", mps.field1(), "row", mps.field2());
1809 else
1810 {
1811 val = atof(mps.field3());
1812
1813 // EQ
1814 if((rset.lhs(idx) > R(-infinity)) && (rset.rhs_w(idx) < R(infinity)))
1815 {
1816 assert(rset.lhs(idx) == rset.rhs(idx));
1817
1818 if(val >= 0)
1819 rset.rhs_w(idx) += val;
1820 else
1821 rset.lhs_w(idx) += val;
1822 }
1823 else
1824 {
1825 // GE
1826 if(rset.lhs(idx) > R(-infinity))
1827 rset.rhs_w(idx) = rset.lhs(idx) + spxAbs(val);
1828 // LE
1829 else
1830 rset.lhs_w(idx) = rset.rhs(idx) - spxAbs(val);
1831 }
1832 }
1833
1834 if(mps.field5() != 0)
1835 {
1836 if((idx = rnames.number(mps.field4())) < 0)
1837 mps.entryIgnored("Range", mps.field1(), "row", mps.field4());
1838 else
1839 {
1840 val = atof(mps.field5());
1841
1842 // EQ
1843 if((rset.lhs(idx) > R(-infinity)) && (rset.rhs(idx) < R(infinity)))
1844 {
1845 assert(rset.lhs(idx) == rset.rhs(idx));
1846
1847 if(val >= 0)
1848 rset.rhs_w(idx) += val;
1849 else
1850 rset.lhs_w(idx) += val;
1851 }
1852 else
1853 {
1854 // GE
1855 if(rset.lhs(idx) > R(-infinity))
1856 rset.rhs_w(idx) = rset.lhs(idx) + spxAbs(val);
1857 // LE
1858 else
1859 rset.lhs_w(idx) = rset.rhs(idx) - spxAbs(val);
1860 }
1861 }
1862 }
1863 }
1864 }
1865
1866 mps.syntaxError();
1867 }
1868
1869
1870
1871 /// Process BOUNDS section.
1872 template <class R>
1873 static void MPSreadBounds(MPSInput& mps, LPColSetBase<R>& cset, const NameSet& cnames,
1874 DIdxSet* intvars, SPxOut* spxout)
1875 {
1876 DIdxSet oldbinvars;
1877 char bndname[MPSInput::MAX_LINE_LEN] = { '\0' };
1878 int idx;
1879 R val;
1880
1881 while(mps.readLine())
1882 {
1883 if(mps.field0() != 0)
1884 {
1885 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD05 Bound name : " << bndname << std::endl;)
1886
1887 if(strcmp(mps.field0(), "ENDATA"))
1888 break;
1889
1890 mps.setSection(MPSInput::ENDATA);
1891
1892 return;
1893 }
1894
1895 // Is the value field used ?
1896 if((!strcmp(mps.field1(), "LO"))
1897 || (!strcmp(mps.field1(), "UP"))
1898 || (!strcmp(mps.field1(), "FX"))
1899 || (!strcmp(mps.field1(), "LI"))
1900 || (!strcmp(mps.field1(), "UI")))
1901 {
1902 if((mps.field3() != 0) && (mps.field4() == 0))
1903 mps.insertName("_BND_", true);
1904 }
1905 else
1906 {
1907 if((mps.field2() != 0) && (mps.field3() == 0))
1908 mps.insertName("_BND_", true);
1909 }
1910
1911 if((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
1912 break;
1913
1914 if(*bndname == '\0')
1915 {
1916 assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN);
1917 spxSnprintf(bndname, MPSInput::MAX_LINE_LEN, "%s", mps.field2());
1918 }
1919
1920 // Only read the first Bound in section
1921 if(!strcmp(bndname, mps.field2()))
1922 {
1923 if((idx = cnames.number(mps.field3())) < 0)
1924 mps.entryIgnored("column", mps.field3(), "bound", bndname);
1925 else
1926 {
1927 if(mps.field4() == 0)
1928 val = 0.0;
1929 else if(!strcmp(mps.field4(), "-Inf") || !strcmp(mps.field4(), "-inf"))
1930 val = R(-infinity);
1931 else if(!strcmp(mps.field4(), "Inf") || !strcmp(mps.field4(), "inf")
1932 || !strcmp(mps.field4(), "+Inf") || !strcmp(mps.field4(), "+inf"))
1933 val = R(infinity);
1934 else
1935 val = atof(mps.field4());
1936
1937 // ILOG extension (Integer Bound)
1938 if(mps.field1()[1] == 'I')
1939 {
1940 if(intvars != 0)
1941 intvars->addIdx(idx);
1942
1943 // if the variable has appeared in the MARKER section of the COLUMNS section then its default bounds were
1944 // set to 0,1; the first time it is declared integer we need to change to default bounds 0,R(infinity)
1945 if(oldbinvars.pos(idx) < 0)
1946 {
1947 cset.upper_w(idx) = R(infinity);
1948 oldbinvars.addIdx(idx);
1949 }
1950 }
1951
1952 switch(*mps.field1())
1953 {
1954 case 'L':
1955 cset.lower_w(idx) = val;
1956 break;
1957
1958 case 'U':
1959 cset.upper_w(idx) = val;
1960 break;
1961
1962 case 'F':
1963 if(mps.field1()[1] == 'X')
1964 {
1965 cset.lower_w(idx) = val;
1966 cset.upper_w(idx) = val;
1967 }
1968 else
1969 {
1970 cset.lower_w(idx) = R(-infinity);
1971 cset.upper_w(idx) = R(infinity);
1972 }
1973
1974 break;
1975
1976 case 'M':
1977 cset.lower_w(idx) = R(-infinity);
1978 break;
1979
1980 case 'P':
1981 cset.upper_w(idx) = R(infinity);
1982 break;
1983
1984 // Ilog extension (Binary)
1985 case 'B':
1986 cset.lower_w(idx) = 0.0;
1987 cset.upper_w(idx) = 1.0;
1988
1989 if(intvars != 0)
1990 intvars->addIdx(idx);
1991
1992 break;
1993
1994 default:
1995 mps.syntaxError();
1996 return;
1997 }
1998 }
1999 }
2000 }
2001
2002 mps.syntaxError();
2003 }
2004
2005
2006
2007 /// Read LP in MPS File Format.
2008 /**
2009 * The specification is taken from the IBM Optimization Library Guide and Reference, online available at
2010 * http://www.software.ibm.com/sos/features/libuser.htm and from the ILOG CPLEX 7.0 Reference Manual, Appendix E, Page
2011 * 531.
2012 *
2013 * This routine should read all valid MPS format files. What it will not do, is find all cases where a file is ill
2014 * formed. If this happens it may complain and read nothing or read "something".
2015 *
2016 * @return true if the file was read correctly.
2017 */
2018 const int Init_Cols = 10000; ///< initialy allocated columns.
2019 const int Init_NZos = 100000; ///< initialy allocated non zeros.
2020 template <class R> inline
2021 bool SPxLPBase<R>::readMPS(
2022 std::istream& p_input, ///< input stream.
2023 NameSet* p_rnames, ///< row names.
2024 NameSet* p_cnames, ///< column names.
2025 DIdxSet* p_intvars) ///< integer variables.
2026 {
2027 LPRowSetBase<R>& rset = *this;
2028 LPColSetBase<R>& cset = *this;
2029 NameSet* rnames;
2030 NameSet* cnames;
2031
2032 if(p_cnames)
2033 cnames = p_cnames;
2034 else
2035 {
2036 cnames = 0;
2037 spx_alloc(cnames);
2038 cnames = new(cnames) NameSet();
2039 }
2040
2041 cnames->clear();
2042
2043 if(p_rnames)
2044 rnames = p_rnames;
2045 else
2046 {
2047 try
2048 {
2049 rnames = 0;
2050 spx_alloc(rnames);
2051 rnames = new(rnames) NameSet();
2052 }
2053 catch(const SPxMemoryException& x)
2054 {
2055 if(!p_cnames)
2056 {
2057 cnames->~NameSet();
2058 spx_free(cnames);
2059 }
2060
2061 throw x;
2062 }
2063 }
2064
2065 rnames->clear();
2066
2067 SPxLPBase<R>::clear(); // clear the LP.
2068
2069 cset.memRemax(Init_NZos);
2070 cset.reMax(Init_Cols);
2071
2072 MPSInput mps(p_input);
2073
2074 MPSreadName(mps, spxout);
2075
2076 if(mps.section() == MPSInput::OBJSEN)
2077 MPSreadObjsen(mps);
2078
2079 if(mps.section() == MPSInput::OBJNAME)
2080 MPSreadObjname(mps);
2081
2082 if(mps.section() == MPSInput::ROWS)
2083 MPSreadRows(mps, rset, *rnames, spxout);
2084
2085 addedRows(rset.num());
2086
2087 if(mps.section() == MPSInput::COLUMNS)
2088 MPSreadCols(mps, rset, *rnames, cset, *cnames, p_intvars);
2089
2090 if(mps.section() == MPSInput::RHS)
2091 MPSreadRhs(mps, rset, *rnames, spxout);
2092
2093 if(mps.section() == MPSInput::RANGES)
2094 MPSreadRanges(mps, rset, *rnames, spxout);
2095
2096 if(mps.section() == MPSInput::BOUNDS)
2097 MPSreadBounds(mps, cset, *cnames, p_intvars, spxout);
2098
2099 if(mps.section() != MPSInput::ENDATA)
2100 mps.syntaxError();
2101
2102 if(mps.hasError())
2103 clear();
2104 else
2105 {
2106 changeSense(mps.objSense() == MPSInput::MINIMIZE ? SPxLPBase<R>::MINIMIZE : SPxLPBase<R>::MAXIMIZE);
2107
2108 SPX_MSG_INFO2((*spxout), (*spxout) << "IMPSRD06 Objective sense: " << ((mps.objSense() ==
2109 MPSInput::MINIMIZE) ? "Minimize\n" : "Maximize\n"));
2110
2111 added2Set(
2112 *(reinterpret_cast<SVSetBase<R>*>(static_cast<LPRowSetBase<R>*>(this))),
2113 *(reinterpret_cast<SVSetBase<R>*>(static_cast<LPColSetBase<R>*>(this))),
2114 cset.num());
2115 addedCols(cset.num());
2116
2117 assert(isConsistent());
2118 }
2119
2120 if(p_cnames == 0)
2121 {
2122 cnames->~NameSet();
2123 spx_free(cnames);
2124 }
2125
2126 if(p_rnames == 0)
2127 {
2128 rnames->~NameSet();
2129 spx_free(rnames);
2130 }
2131
2132 return !mps.hasError();
2133 }
2134
2135
2136
2137 // ---------------------------------------------------------------------------------------------------------------------
2138 // Specialization for writing LP format
2139 // ---------------------------------------------------------------------------------------------------------------------
2140
2141 // get the name of a row or construct one
2142 template <class R>
2143 static const char* LPFgetRowName(
2144 const SPxLPBase<R>& p_lp,
2145 int p_idx,
2146 const NameSet* p_rnames,
2147 char* p_buf,
2148 int p_num_written_rows
2149 )
2150 {
2151 assert(p_buf != 0);
2152 assert(p_idx >= 0);
2153 assert(p_idx < p_lp.nRows());
2154
2155 if(p_rnames != 0)
2156 {
2157 DataKey key = p_lp.rId(p_idx);
2158
2159 if(p_rnames->has(key))
2160 return (*p_rnames)[key];
2161 }
2162
2163 spxSnprintf(p_buf, 16, "C%d", p_num_written_rows);
2164
2165 return p_buf;
2166 }
2167
2168
2169
2170 // get the name of a column or construct one
2171 template <class R>
2172 static const char* getColName(
2173 const SPxLPBase<R>& p_lp,
2174 int p_idx,
2175 const NameSet* p_cnames,
2176 char* p_buf
2177 )
2178 {
2179 assert(p_buf != 0);
2180 assert(p_idx >= 0);
2181 assert(p_idx < p_lp.nCols());
2182
2183 if(p_cnames != 0)
2184 {
2185 DataKey key = p_lp.cId(p_idx);
2186
2187 if(p_cnames->has(key))
2188 return (*p_cnames)[key];
2189 }
2190
2191 spxSnprintf(p_buf, 16, "x%d", p_idx);
2192
2193 return p_buf;
2194 }
2195
2196
2197
2198 // write an SVectorBase<R>
2199 #define SOPLEX_NUM_ENTRIES_PER_LINE 5
2200 template <class R>
2201 static void LPFwriteSVector(
2202 const SPxLPBase<R>& p_lp, ///< the LP
2203 std::ostream& p_output, ///< output stream
2204 const NameSet* p_cnames, ///< column names
2205 const SVectorBase<R>& p_svec) ///< vector to write
2206 {
2207
2208 char name[16];
2209 int num_coeffs = 0;
2210
2211 for(int j = 0; j < p_lp.nCols(); ++j)
2212 {
2213 const R coeff = p_svec[j];
2214
2215 if(coeff == 0)
2216 continue;
2217
2218 if(num_coeffs == 0)
2219 p_output << coeff << " " << getColName(p_lp, j, p_cnames, name);
2220 else
2221 {
2222 // insert a line break every SOPLEX_NUM_ENTRIES_PER_LINE columns
2223 if(num_coeffs % SOPLEX_NUM_ENTRIES_PER_LINE == 0)
2224 p_output << "\n\t";
2225
2226 if(coeff < 0)
2227 p_output << " - " << -coeff;
2228 else
2229 p_output << " + " << coeff;
2230
2231 p_output << " " << getColName(p_lp, j, p_cnames, name);
2232 }
2233
2234 ++num_coeffs;
2235 }
2236 }
2237
2238
2239
2240 // write the objective
2241 template <class R>
2242 static void LPFwriteObjective(
2243 const SPxLPBase<R>& p_lp, ///< the LP
2244 std::ostream& p_output, ///< output stream
2245 const NameSet* p_cnames ///< column names
2246 )
2247 {
2248
2249 const int sense = p_lp.spxSense();
2250
2251 p_output << ((sense == SPxLPBase<R>::MINIMIZE) ? "Minimize\n" : "Maximize\n");
2252 p_output << " obj: ";
2253
2254 const VectorBase<R>& obj = p_lp.maxObj();
2255 DSVectorBase<R> svec(obj.dim());
2256 svec.operator = (obj);
2257 svec *= R(sense);
2258 LPFwriteSVector(p_lp, p_output, p_cnames, svec);
2259 p_output << "\n";
2260 }
2261
2262
2263
2264 // write non-ranged rows
2265 template <class R>
2266 static void LPFwriteRow(
2267 const SPxLPBase<R>& p_lp, ///< the LP
2268 std::ostream& p_output, ///< output stream
2269 const NameSet* p_cnames, ///< column names
2270 const SVectorBase<R>& p_svec, ///< vector of the row
2271 const R& p_lhs, ///< lhs of the row
2272 const R& p_rhs ///< rhs of the row
2273 )
2274 {
2275
2276 LPFwriteSVector(p_lp, p_output, p_cnames, p_svec);
2277
2278 if(p_lhs == p_rhs)
2279 p_output << " = " << p_rhs;
2280 else if(p_lhs <= R(-infinity))
2281 p_output << " <= " << p_rhs;
2282 else
2283 {
2284 assert(p_rhs >= R(infinity));
2285 p_output << " >= " << p_lhs;
2286 }
2287
2288 p_output << "\n";
2289 }
2290
2291
2292
2293 // write all rows
2294 template <class R>
2295 static void LPFwriteRows(
2296 const SPxLPBase<R>& p_lp, ///< the LP
2297 std::ostream& p_output, ///< output stream
2298 const NameSet* p_rnames, ///< row names
2299 const NameSet* p_cnames ///< column names
2300 )
2301 {
2302
2303 char name[16];
2304
2305 p_output << "Subject To\n";
2306
2307 for(int i = 0; i < p_lp.nRows(); ++i)
2308 {
2309 const R lhs = p_lp.lhs(i);
2310 const R rhs = p_lp.rhs(i);
2311
2312 if(lhs > R(-infinity) && rhs < R(infinity) && lhs != rhs)
2313 {
2314 // ranged row -> write two non-ranged rows
2315 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_1 : ";
2316 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, R(infinity));
2317
2318 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << "_2 : ";
2319 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), R(-infinity), rhs);
2320 }
2321 else
2322 {
2323 p_output << " " << LPFgetRowName(p_lp, i, p_rnames, name, i) << " : ";
2324 LPFwriteRow(p_lp, p_output, p_cnames, p_lp.rowVector(i), lhs, rhs);
2325 }
2326 }
2327 }
2328
2329
2330
2331 // write the variable bounds
2332 // (the default bounds 0 <= x <= R(infinity) are not written)
2333 template <class R>
2334 static void LPFwriteBounds(
2335 const SPxLPBase<R>& p_lp, ///< the LP to write
2336 std::ostream& p_output, ///< output stream
2337 const NameSet* p_cnames ///< column names
2338 )
2339 {
2340
2341 char name[16];
2342
2343 p_output << "Bounds\n";
2344
2345 for(int j = 0; j < p_lp.nCols(); ++j)
2346 {
2347 const R lower = p_lp.lower(j);
2348 const R upper = p_lp.upper(j);
2349
2350 if(lower == upper)
2351 {
2352 p_output << " " << getColName(p_lp, j, p_cnames, name) << " = " << upper << '\n';
2353 }
2354 else if(lower > R(-infinity))
2355 {
2356 if(upper < R(infinity))
2357 {
2358 // range bound
2359 if(lower != 0)
2360 p_output << " " << lower << " <= "
2361 << getColName(p_lp, j, p_cnames, name)
2362 << " <= " << upper << '\n';
2363 else
2364 p_output << " " << getColName(p_lp, j, p_cnames, name)
2365 << " <= " << upper << '\n';
2366 }
2367 else if(lower != 0)
2368 p_output << " " << lower << " <= "
2369 << getColName(p_lp, j, p_cnames, name)
2370 << '\n';
2371 }
2372 else if(upper < R(infinity))
2373 p_output << " -Inf <= "
2374 << getColName(p_lp, j, p_cnames, name)
2375 << " <= " << upper << '\n';
2376 else
2377 p_output << " " << getColName(p_lp, j, p_cnames, name)
2378 << " free\n";
2379 }
2380 }
2381
2382
2383
2384 // write the generals section
2385 template <class R>
2386 static void LPFwriteGenerals(
2387 const SPxLPBase<R>& p_lp, ///< the LP to write
2388 std::ostream& p_output, ///< output stream
2389 const NameSet* p_cnames, ///< column names
2390 const DIdxSet* p_intvars ///< integer variables
2391 )
2392 {
2393
2394 char name[16];
2395
2396 if(p_intvars == NULL || p_intvars->size() <= 0)
2397 return; // no integer variables
2398
2399 p_output << "Generals\n";
2400
2401 for(int j = 0; j < p_lp.nCols(); ++j)
2402 if(p_intvars->pos(j) >= 0)
2403 p_output << " " << getColName(p_lp, j, p_cnames, name) << "\n";
2404 }
2405
2406
2407
2408 /// Write LP in LP Format.
2409 template <class R> inline
2410 void SPxLPBase<R>::writeLPF(
2411 std::ostream& p_output, ///< output stream
2412 const NameSet* p_rnames, ///< row names
2413 const NameSet* p_cnames, ///< column names
2414 const DIdxSet* p_intvars ///< integer variables
2415 ) const
2416 {
2417 SPxOut::setScientific(p_output, 16);
2418
2419 LPFwriteObjective(*this, p_output, p_cnames);
2420 LPFwriteRows(*this, p_output, p_rnames, p_cnames);
2421 LPFwriteBounds(*this, p_output, p_cnames);
2422 LPFwriteGenerals(*this, p_output, p_cnames, p_intvars);
2423
2424 p_output << "End" << std::endl;
2425 }
2426
2427
2428
2429 // ---------------------------------------------------------------------------------------------------------------------
2430 // Specialization for writing MPS format
2431 // ---------------------------------------------------------------------------------------------------------------------
2432
2433 template <class R>
2434 static void MPSwriteRecord(
2435 std::ostream& os,
2436 const char* indicator,
2437 const char* name,
2438 const char* name1 = nullptr,
2439 const R value1 = 0.0,
2440 const char* name2 = nullptr,
2441 const R value2 = 0.0
2442 )
2443 {
2444 char buf[81];
2445
2446 spxSnprintf(buf, sizeof(buf), " %-2.2s %-8.8s", (indicator == 0) ? "" : indicator,
2447 (name == 0) ? "" : name);
2448 os << buf;
2449
2450 if(name1 != nullptr)
2451 {
2452 spxSnprintf(buf, sizeof(buf), "%-8.8s %.15" SOPLEX_REAL_FORMAT, name1, (Real) value1);
2453 os << buf;
2454
2455 if(name2 != 0)
2456 {
2457 spxSnprintf(buf, sizeof(buf), " %-8.8s %.15" SOPLEX_REAL_FORMAT, name2, (Real) value2);
2458 os << buf;
2459 }
2460 }
2461
2462 os << std::endl;
2463 }
2464
2465
2466
2467 template <class R>
2468 static R MPSgetRHS(R left, R right)
2469 {
2470 R rhsval;
2471
2472 if(left > R(-infinity)) /// This includes ranges
2473 rhsval = left;
2474 else if(right < R(infinity))
2475 rhsval = right;
2476 else
2477 throw SPxInternalCodeException("XMPSWR01 This should never happen.");
2478
2479 return rhsval;
2480 }
2481
2482
2483 template <class R>
2484 static const char* MPSgetRowName(
2485 const SPxLPBase<R>& lp,
2486 int idx,
2487 const NameSet* rnames,
2488 char* buf
2489 )
2490 {
2491 assert(buf != 0);
2492 assert(idx >= 0);
2493 assert(idx < lp.nRows());
2494
2495 if(rnames != 0)
2496 {
2497 DataKey key = lp.rId(idx);
2498
2499 if(rnames->has(key))
2500 return (*rnames)[key];
2501 }
2502
2503 spxSnprintf(buf, 16, "C%d", idx);
2504
2505 return buf;
2506 }
2507
2508
2509
2510 /// Write LP in MPS format.
2511 /** @note There will always be a BOUNDS section, even if there are no bounds.
2512 */
2513 template <class R> inline
2514 void SPxLPBase<R>::writeMPS(
2515 std::ostream& p_output, ///< output stream.
2516 const NameSet* p_rnames, ///< row names.
2517 const NameSet* p_cnames, ///< column names.
2518 const DIdxSet* p_intvars ///< integer variables.
2519 ) const
2520 {
2521
2522 const char* indicator;
2523 char name [16];
2524 char name1[16];
2525 char name2[16];
2526 bool has_ranges = false;
2527 int i;
2528 int k;
2529
2530 SPxOut::setScientific(p_output, 16);
2531 // --- NAME Section ---
2532 p_output << "NAME MPSDATA" << std::endl;
2533
2534 // --- ROWS Section ---
2535 p_output << "ROWS" << std::endl;
2536
2537 for(i = 0; i < nRows(); i++)
2538 {
2539 if(lhs(i) == rhs(i))
2540 indicator = "E";
2541 else if((lhs(i) > R(-infinity)) && (rhs(i) < R(infinity)))
2542 {
2543 indicator = "E";
2544 has_ranges = true;
2545 }
2546 else if(lhs(i) > R(-infinity))
2547 indicator = "G";
2548 else if(rhs(i) < R(infinity))
2549 indicator = "L";
2550 else
2551 throw SPxInternalCodeException("XMPSWR02 This should never happen.");
2552
2553 MPSwriteRecord<R>(p_output, indicator, MPSgetRowName(*this, i, p_rnames, name));
2554 }
2555
2556 MPSwriteRecord<R>(p_output, "N", "MINIMIZE");
2557
2558 // --- COLUMNS Section ---
2559 p_output << "COLUMNS" << std::endl;
2560
2561 bool has_intvars = (p_intvars != 0) && (p_intvars->size() > 0);
2562
2563 for(int j = 0; j < (has_intvars ? 2 : 1); j++)
2564 {
2565 bool is_intrun = has_intvars && (j == 1);
2566
2567 if(is_intrun)
2568 p_output << " MARK0001 'MARKER' 'INTORG'" << std::endl;
2569
2570 for(i = 0; i < nCols(); i++)
2571 {
2572 bool is_intvar = has_intvars && (p_intvars->pos(i) >= 0);
2573
2574 if((is_intrun && !is_intvar) || (!is_intrun && is_intvar))
2575 continue;
2576
2577 const SVectorBase<R>& col = colVector(i);
2578 int colsize2 = (col.size() / 2) * 2;
2579
2580 assert(colsize2 % 2 == 0);
2581
2582 for(k = 0; k < colsize2; k += 2)
2583 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name),
2584 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k),
2585 MPSgetRowName(*this, col.index(k + 1), p_rnames, name2), col.value(k + 1));
2586
2587 if(colsize2 != col.size())
2588 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name),
2589 MPSgetRowName(*this, col.index(k), p_rnames, name1), col.value(k));
2590
2591 if(isNotZero(maxObj(i), this->tolerances()->epsilon()))
2592 MPSwriteRecord(p_output, 0, getColName(*this, i, p_cnames, name), "MINIMIZE", -maxObj(i));
2593 }
2594
2595 if(is_intrun)
2596 p_output << " MARK0001 'MARKER' 'INTEND'" << std::endl;
2597 }
2598
2599 // --- RHS Section ---
2600 p_output << "RHS" << std::endl;
2601
2602 i = 0;
2603
2604 while(i < nRows())
2605 {
2606 R rhsval1 = 0.0;
2607 R rhsval2 = 0.0;
2608
2609 for(; i < nRows(); i++)
2610 if((rhsval1 = MPSgetRHS(lhs(i), rhs(i))) != 0.0)
2611 break;
2612
2613 if(i < nRows())
2614 {
2615 for(k = i + 1; k < nRows(); k++)
2616 {
2617 if((rhsval2 = MPSgetRHS(lhs(k), rhs(k))) != 0.0)
2618 break;
2619 }
2620
2621 if(k < nRows())
2622 {
2623 MPSwriteRecord(p_output, 0, "RHS", MPSgetRowName(*this, i, p_rnames, name1), rhsval1,
2624 MPSgetRowName(*this, k, p_rnames, name2), rhsval2);
2625 }
2626 else
2627 MPSwriteRecord(p_output, 0, "RHS", MPSgetRowName(*this, i, p_rnames, name1), rhsval1);
2628
2629 i = k + 1;
2630 }
2631 }
2632
2633 // --- RANGES Section ---
2634 if(has_ranges)
2635 {
2636 p_output << "RANGES" << std::endl;
2637
2638 for(i = 0; i < nRows(); i++)
2639 {
2640 if((lhs(i) > R(-infinity)) && (rhs(i) < R(infinity)))
2641 MPSwriteRecord(p_output, "", "RANGE", MPSgetRowName(*this, i, p_rnames, name1), rhs(i) - lhs(i));
2642 }
2643 }
2644
2645 // --- BOUNDS Section ---
2646 p_output << "BOUNDS" << std::endl;
2647
2648 for(i = 0; i < nCols(); i++)
2649 {
2650 // skip variables that do not appear in the objective function or any constraint
2651 const SVectorBase<R>& col = colVector(i);
2652
2653 if(col.size() == 0 && isZero(maxObj(i), this->tolerances()->epsilon()))
2654 continue;
2655
2656 if(lower(i) == upper(i))
2657 {
2658 MPSwriteRecord(p_output, "FX", "BOUND", getColName(*this, i, p_cnames, name1), lower(i));
2659 continue;
2660 }
2661
2662 if((lower(i) <= R(-infinity)) && (upper(i) >= R(infinity)))
2663 {
2664 MPSwriteRecord<R>(p_output, "FR", "BOUND", getColName(*this, i, p_cnames, name1));
2665 continue;
2666 }
2667
2668 if(lower(i) != 0.0)
2669 {
2670 if(lower(i) > R(-infinity))
2671 MPSwriteRecord(p_output, "LO", "BOUND", getColName(*this, i, p_cnames, name1), lower(i));
2672 else
2673 MPSwriteRecord<R>(p_output, "MI", "BOUND", getColName(*this, i, p_cnames, name1));
2674 }
2675
2676 if(has_intvars && (p_intvars->pos(i) >= 0))
2677 {
2678 // Integer variables have default upper bound 1.0, but we should write
2679 // it nevertheless since CPLEX seems to assume R(infinity) otherwise.
2680 MPSwriteRecord(p_output, "UP", "BOUND", getColName(*this, i, p_cnames, name1), upper(i));
2681 }
2682 else
2683 {
2684 // Continous variables have default upper bound R(infinity)
2685 if(upper(i) < R(infinity))
2686 MPSwriteRecord(p_output, "UP", "BOUND", getColName(*this, i, p_cnames, name1), upper(i));
2687 }
2688 }
2689
2690 // --- ENDATA Section ---
2691 p_output << "ENDATA" << std::endl;
2692
2693 // Output warning when writing a maximisation problem
2694 if(spxSense() == SPxLPBase<R>::MAXIMIZE)
2695 {
2696 SPX_MSG_WARNING((*spxout), (*spxout) <<
2697 "XMPSWR03 Warning: objective function inverted when writing maximization problem in MPS file format\n");
2698 }
2699 }
2700
2701
2702
2703 /// Building the dual problem from a given LP
2704 /// @note primalRows must be as large as the number of unranged primal rows + 2 * the number of ranged primal rows.
2705 /// dualCols must have the identical size to the primal rows.
2706 template <class R> inline
2707 void SPxLPBase<R>::buildDualProblem(SPxLPBase<R>& dualLP, SPxRowId primalRowIds[],
2708 SPxColId primalColIds[],
2709 SPxRowId dualRowIds[], SPxColId dualColIds[], int* nprimalrows, int* nprimalcols, int* ndualrows,
2710 int* ndualcols)
2711 {
2712 // Setting up the primalrowids and dualcolids arrays if not given as parameters
2713 if(primalRowIds == 0 || primalColIds == 0 || dualRowIds == 0 || dualColIds == 0)
2714 {
2715 DataArray < SPxRowId > primalrowids(2 * nRows());
2716 DataArray < SPxColId > primalcolids(2 * nCols());
2717 DataArray < SPxRowId > dualrowids(2 * nCols());
2718 DataArray < SPxColId > dualcolids(2 * nRows());
2719 int numprimalrows = 0;
2720 int numprimalcols = 0;
2721 int numdualrows = 0;
2722 int numdualcols = 0;
2723
2724 buildDualProblem(dualLP, primalrowids.get_ptr(), primalcolids.get_ptr(), dualrowids.get_ptr(),
2725 dualcolids.get_ptr(), &numprimalrows, &numprimalcols, &numdualrows, &numdualcols);
2726
2727 if(primalRowIds != 0)
2728 {
2729 primalRowIds = primalrowids.get_ptr();
2730 (*nprimalrows) = numprimalrows;
2731 }
2732
2733 if(primalColIds != 0)
2734 {
2735 primalColIds = primalcolids.get_ptr();
2736 (*nprimalcols) = numprimalcols;
2737 }
2738
2739 if(dualRowIds != 0)
2740 {
2741 dualRowIds = dualrowids.get_ptr();
2742 (*ndualrows) = numdualrows;
2743 }
2744
2745 if(dualColIds != 0)
2746 {
2747 dualColIds = dualcolids.get_ptr();
2748 (*ndualcols) = numdualcols;
2749 }
2750
2751 return;
2752 }
2753
2754 // setting the sense of the dual LP
2755 if(spxSense() == MINIMIZE)
2756 dualLP.changeSense(MAXIMIZE);
2757 else
2758 dualLP.changeSense(MINIMIZE);
2759
2760 LPRowSetBase<R> dualrows(nCols());
2761 LPColSetBase<R> dualcols(nRows());
2762 DSVectorBase<R> col(1);
2763
2764 int numAddedRows = 0;
2765 int numVarBoundCols = 0;
2766 int primalrowsidx = 0;
2767 int primalcolsidx = 0;
2768
2769 for(int i = 0; i < nCols(); ++i)
2770 {
2771 primalColIds[primalcolsidx] = cId(i);
2772 primalcolsidx++;
2773
2774 if(lower(i) <= R(-infinity) && upper(i) >= R(infinity)) // unrestricted variables
2775 {
2776 dualrows.create(0, obj(i), obj(i));
2777 numAddedRows++;
2778 }
2779 else if(lower(i) <= R(-infinity)) // no lower bound is set, indicating a <= 0 variable
2780 {
2781 if(isZero(upper(i), this->tolerances()->epsilon())) // standard bound variable
2782 {
2783 if(spxSense() == MINIMIZE)
2784 dualrows.create(0, obj(i), R(infinity));
2785 else
2786 dualrows.create(0, R(-infinity), obj(i));
2787 }
2788 else // additional upper bound on the variable
2789 {
2790 col.add(numAddedRows, 1.0);
2791
2792 if(spxSense() == MINIMIZE)
2793 {
2794 dualrows.create(0, obj(i), obj(i));
2795 dualcols.add(upper(i), R(-infinity), col, 0.0);
2796 }
2797 else
2798 {
2799 dualrows.create(0, obj(i), obj(i));
2800 dualcols.add(upper(i), 0.0, col, R(infinity));
2801 }
2802
2803 col.clear();
2804
2805 numVarBoundCols++;
2806 }
2807
2808 numAddedRows++;
2809 }
2810 else if(upper(i) >= R(infinity)) // no upper bound set, indicating a >= 0 variable
2811 {
2812 if(isZero(lower(i), this->tolerances()->epsilon())) // standard bound variable
2813 {
2814 if(spxSense() == MINIMIZE)
2815 dualrows.create(0, R(-infinity), obj(i));
2816 else
2817 dualrows.create(0, obj(i), R(infinity));
2818 }
2819 else // additional lower bound on the variable
2820 {
2821 col.add(numAddedRows, 1.0);
2822
2823 if(spxSense() == MINIMIZE)
2824 {
2825 dualrows.create(0, obj(i), obj(i));
2826 dualcols.add(lower(i), 0.0, col, R(infinity));
2827 }
2828 else
2829 {
2830 dualrows.create(0, obj(i), obj(i));
2831 dualcols.add(lower(i), R(-infinity), col, 0.0);
2832 }
2833
2834 col.clear();
2835
2836 numVarBoundCols++;
2837 }
2838
2839 numAddedRows++;
2840 }
2841 else if(NE(lower(i), upper(i), this->tolerances()->epsilon())) // a boxed variable
2842 {
2843 if(isZero(lower(i), this->tolerances()->epsilon())) // variable bounded between 0 and upper(i)
2844 {
2845 col.add(numAddedRows, 1.0);
2846
2847 if(spxSense() == MINIMIZE)
2848 {
2849 dualrows.create(0, R(-infinity), obj(i));
2850 dualcols.add(upper(i), R(-infinity), col, 0.0);
2851 }
2852 else
2853 {
2854 dualrows.create(0, obj(i), R(infinity));
2855 dualcols.add(upper(i), 0.0, col, R(infinity));
2856 }
2857
2858 col.clear();
2859
2860 numVarBoundCols++;
2861 }
2862 else if(isZero(upper(i),
2863 this->tolerances()->epsilon())) // variable bounded between lower(i) and 0
2864 {
2865 col.add(numAddedRows, 1.0);
2866
2867 if(spxSense() == MINIMIZE)
2868 {
2869 dualrows.create(0, obj(i), R(infinity));
2870 dualcols.add(lower(i), 0.0, col, R(infinity));
2871 }
2872 else
2873 {
2874 dualrows.create(0, R(-infinity), obj(i));
2875 dualcols.add(lower(i), R(-infinity), col, 0.0);
2876 }
2877
2878 col.clear();
2879
2880 numVarBoundCols++;
2881 }
2882 else // variable bounded between lower(i) and upper(i)
2883 {
2884 dualrows.create(0, obj(i), obj(i));
2885
2886 col.add(numAddedRows, 1.0);
2887
2888 if(spxSense() == MINIMIZE)
2889 {
2890 dualcols.add(lower(i), 0.0, col, R(infinity));
2891 dualcols.add(upper(i), R(-infinity), col, 0.0);
2892 }
2893 else
2894 {
2895 dualcols.add(lower(i), R(-infinity), col, 0.0);
2896 dualcols.add(upper(i), 0.0, col, R(infinity));
2897 }
2898
2899 col.clear();
2900
2901 numVarBoundCols += 2;
2902 }
2903
2904 numAddedRows++;
2905 }
2906 else
2907 {
2908 assert(lower(i) == upper(i));
2909
2910 dualrows.create(0, obj(i), obj(i));
2911
2912 col.add(numAddedRows, 1.0);
2913 dualcols.add(lower(i), 0, col, R(infinity));
2914 dualcols.add(lower(i), R(-infinity), col, 0);
2915 col.clear();
2916
2917 numVarBoundCols += 2;
2918 numAddedRows++;
2919 }
2920 }
2921
2922 // adding the empty rows to the dual LP
2923 dualLP.addRows(dualrows);
2924
2925 // setting the dual row ids for the related primal cols.
2926 // this assumes that the rows are added in sequential order.
2927 for(int i = 0; i < primalcolsidx; i++)
2928 dualRowIds[i] = dualLP.rId(i);
2929
2930 (*nprimalcols) = primalcolsidx;
2931 (*ndualrows) = primalcolsidx;
2932
2933 // iterating over each of the rows to create dual columns
2934 for(int i = 0; i < nRows(); ++i)
2935 {
2936 // checking the type of the row
2937 switch(rowType(i))
2938 {
2939 case LPRowBase<R>::RANGE: // range constraint, requires the addition of two dual variables
2940 assert(lhs(i) > R(-infinity));
2941 assert(rhs(i) < R(infinity));
2942
2943 if(spxSense() == MINIMIZE)
2944 {
2945 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2946 primalrowsidx++;
2947 dualcols.add(lhs(i), 0.0, rowVector(i), R(infinity));
2948
2949 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2950 primalrowsidx++;
2951 dualcols.add(rhs(i), R(-infinity), rowVector(i), 0.0);
2952 }
2953 else
2954 {
2955 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2956 primalrowsidx++;
2957 dualcols.add(lhs(i), R(-infinity), rowVector(i), 0.0);
2958
2959 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2960 primalrowsidx++;
2961 dualcols.add(rhs(i), 0.0, rowVector(i), R(infinity));
2962 }
2963
2964 break;
2965
2966 case LPRowBase<R>::GREATER_EQUAL: // >= constraint
2967 assert(lhs(i) > R(-infinity));
2968 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2969 primalrowsidx++;
2970
2971 if(spxSense() == MINIMIZE)
2972 dualcols.add(lhs(i), 0.0, rowVector(i), R(infinity));
2973 else
2974 dualcols.add(lhs(i), R(-infinity), rowVector(i), 0.0);
2975
2976 break;
2977
2978 case LPRowBase<R>::LESS_EQUAL: // <= constriant
2979 assert(rhs(i) < R(infinity));
2980 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2981 primalrowsidx++;
2982
2983 if(spxSense() == MINIMIZE)
2984 dualcols.add(rhs(i), R(-infinity), rowVector(i), 0.0);
2985 else
2986 dualcols.add(rhs(i), 0.0, rowVector(i), R(infinity));
2987
2988 break;
2989
2990 case LPRowBase<R>::EQUAL: // Equality constraint
2991 assert(EQ(lhs(i), rhs(i), this->tolerances()->epsilon()));
2992 primalRowIds[primalrowsidx] = rId(i); // setting the rowid for the primal row
2993 primalrowsidx++;
2994 dualcols.add(rhs(i), R(-infinity), rowVector(i), R(infinity));
2995 break;
2996
2997 default:
2998 throw SPxInternalCodeException("XLPFRD01 This should never happen.");
2999 }
3000 }
3001
3002 // adding the filled columns to the dual LP
3003 dualLP.addCols(dualcols);
3004
3005 // setting the dual column ids for the related primal rows.
3006 // this assumes that the columns are added in sequential order.
3007 for(int i = 0; i < primalrowsidx; i++)
3008 dualColIds[i] = dualLP.cId(i + numVarBoundCols);
3009
3010 (*nprimalrows) = primalrowsidx;
3011 (*ndualcols) = primalrowsidx;
3012 }
3013
3014 } // namespace soplex
3015