SoPlex Doxygen Documentation
spxmpsread.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2012 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 spxmpsread.cpp
17  * @brief Read LP from MPS format file.
18  */
19 //#define DEBUGGING 1
20 
21 #include <assert.h>
22 #include <string.h>
23 #include <iostream>
24 
25 #include "spxdefines.h"
26 #include "spxlp.h"
27 #include "mpsinput.h"
28 #include "spxout.h"
29 
30 #define INIT_COLS 10000 ///< initialy allocated columns.
31 #define INIT_NZOS 100000 ///< initialy allocated non zeros.
32 
33 namespace soplex
34 {
35 
36 /// Process NAME section.
37 static void readName(MPSInput& mps)
38 {
39  do
40  {
41  // This has to be the Line with the NAME section.
42  if (!mps.readLine()
43  || (mps.field0() == 0) || strcmp(mps.field0(), "NAME"))
44  break;
45 
46  // Sometimes the name is omitted.
47  mps.setProbName((mps.field1() == 0) ? "_MPS_" : mps.field1());
48 
49  MSG_INFO2( spxout << "IMPSRD01 Problem name : " << mps.probName()
50  << std::endl; )
51 
52  // This hat to be a new section
53  if (!mps.readLine() || (mps.field0() == 0))
54  break;
55 
56  if (!strcmp(mps.field0(), "ROWS"))
57  mps.setSection(MPSInput::ROWS);
58  else if (!strncmp(mps.field0(), "OBJSEN", 6))
59  mps.setSection(MPSInput::OBJSEN);
60  else if (!strcmp(mps.field0(), "OBJNAME"))
61  mps.setSection(MPSInput::OBJNAME);
62  else
63  break;
64 
65  return;
66  }
67  while(false);
68 
69  mps.syntaxError();
70 }
71 
72 /// Process OBJSEN section. This Section is an ILOG extension.
73 static void readObjsen(MPSInput& mps)
74 {
75  do
76  {
77  // This has to be the Line with MIN or MAX.
78  if (!mps.readLine() || (mps.field1() == 0))
79  break;
80 
81  if (!strcmp(mps.field1(), "MIN"))
82  mps.setObjSense(SPxLP::MINIMIZE);
83  else if (!strcmp(mps.field1(), "MAX"))
84  mps.setObjSense(SPxLP::MAXIMIZE);
85  else
86  break;
87 
88  // Look for ROWS or OBJNAME Section
89  if (!mps.readLine() || (mps.field0() == 0))
90  break;
91 
92  if (!strcmp(mps.field0(), "ROWS"))
93  mps.setSection(MPSInput::ROWS);
94  else if (!strcmp(mps.field0(), "OBJNAME"))
95  mps.setSection(MPSInput::OBJNAME);
96  else
97  break;
98 
99  return;
100  }
101  while(false);
102 
103  mps.syntaxError();
104 }
105 
106 /// Process OBJNAME section. This Section is an ILOG extension.
107 static void readObjname(MPSInput& mps)
108 {
109  do
110  {
111  // This has to be the Line with the name.
112  if (!mps.readLine() || (mps.field1() == 0))
113  break;
114 
115  mps.setObjName(mps.field1());
116 
117  // Look for ROWS Section
118  if (!mps.readLine() || (mps.field0() == 0))
119  break;
120 
121  if (strcmp(mps.field0(), "ROWS"))
122  break;
123 
124  mps.setSection(MPSInput::ROWS);
125  return;
126  }
127  while(false);
128 
129  mps.syntaxError();
130 }
131 
132 /// Process ROWS section.
133 static void readRows(
134  MPSInput& mps,
135  LPRowSet& rset,
136  NameSet& rnames)
137 {
138  LPRow row;
139 
140  while(mps.readLine())
141  {
142  if (mps.field0() != 0)
143  {
144  MSG_INFO2( spxout << "IMPSRD02 Objective name : " << mps.objName()
145  << std::endl; )
146 
147  if (strcmp(mps.field0(), "COLUMNS"))
148  break;
149 
150  mps.setSection(MPSInput::COLUMNS);
151  return;
152  }
153  if (*mps.field1() == 'N')
154  {
155  if (*mps.objName() == '\0')
156  mps.setObjName(mps.field2());
157  }
158  else
159  {
160  if (rnames.has(mps.field2()))
161  break;
162 
163  rnames.add(mps.field2());
164 
165  switch(*mps.field1())
166  {
167  case 'G' :
168  row.setLhs(0.0);
169  row.setRhs(infinity);
170  break;
171  case 'E' :
172  row.setLhs(0.0);
173  row.setRhs(0.0);
174  break;
175  case 'L' :
176  row.setLhs(-infinity);
177  row.setRhs(0.0);
178  break;
179  default :
180  mps.syntaxError();
181  return;
182  }
183  rset.add(row);
184  }
185  assert((*mps.field1() == 'N')
186  || (rnames.number(mps.field2()) == rset.num() - 1));
187  }
188  mps.syntaxError();
189 }
190 
191 /// Process COLUMNS section.
192 static void readCols(
193  MPSInput& mps,
194  const LPRowSet& rset,
195  const NameSet& rnames,
196  LPColSet& cset,
197  NameSet& cnames,
198  DIdxSet* intvars)
199 {
200  Real val;
201  int idx;
202  char colname[MPSInput::MAX_LINE_LEN] = { '\0' };
203  LPCol col(rset.num());
204  DSVector vec;
205 
206  col.setObj(0.0);
207  vec.clear();
208 
209  while(mps.readLine())
210  {
211  if (mps.field0() != 0)
212  {
213  if (strcmp(mps.field0(), "RHS"))
214  break;
215 
216  if (colname[0] != '\0')
217  {
218  col.setColVector(vec);
219  cset.add(col);
220  }
221  mps.setSection(MPSInput::RHS);
222  return;
223  }
224  if ((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
225  break;
226 
227  // new column?
228  if (strcmp(colname, mps.field1()))
229  {
230  // first column?
231  if (colname[0] != '\0')
232  {
233  col.setColVector(vec);
234  cset.add(col);
235  }
236  // save copy of string (make sure string ends with \0)
237  strncpy(colname, mps.field1(), MPSInput::MAX_LINE_LEN-1);
238  colname[MPSInput::MAX_LINE_LEN-1] = '\0';
239  cnames.add(colname);
240  vec.clear();
241  col.setObj(0.0);
242  col.setLower(0.0);
243  col.setUpper(infinity);
244 
245  if (mps.isInteger())
246  {
247  assert(cnames.number(colname) == cset.num());
248 
249  if (intvars != 0)
250  intvars->addIdx(cnames.number(colname));
251 
252  // For Integer variable the default bounds are 0/1
253  col.setUpper(1.0);
254  }
255  }
256  val = atof(mps.field3());
257 
258  if (!strcmp(mps.field2(), mps.objName()))
259  col.setObj(val);
260  else
261  {
262  if ((idx = rnames.number(mps.field2())) < 0)
263  mps.entryIgnored("Column", mps.field1(), "row", mps.field2());
264  else
265  if (val != 0.0)
266  vec.add(idx, val);
267  }
268  if (mps.field5() != 0)
269  {
270  assert(mps.field4() != 0);
271 
272  val = atof(mps.field5());
273 
274  if (!strcmp(mps.field4(), mps.objName()))
275  col.setObj(val);
276  else
277  {
278  if ((idx = rnames.number(mps.field4())) < 0)
279  mps.entryIgnored("Column", mps.field1(), "row", mps.field4());
280  else
281  if (val != 0.0)
282  vec.add(idx, val);
283  }
284  }
285  }
286  mps.syntaxError();
287 }
288 
289 /// Process RHS section.
290 static void readRhs(
291  MPSInput& mps,
292  LPRowSet& rset,
293  const NameSet& rnames)
294 {
295  char rhsname[MPSInput::MAX_LINE_LEN] = { '\0' };
296  char addname[MPSInput::MAX_LINE_LEN] = { '\0' };
297  int idx;
298  Real val;
299 
300  while(mps.readLine())
301  {
302  if (mps.field0() != 0)
303  {
304  MSG_INFO2( spxout << "IMPSRD03 RHS name : " << rhsname
305  << std::endl; );
306 
307  if (!strcmp(mps.field0(), "RANGES"))
308  mps.setSection(MPSInput::RANGES);
309  else if (!strcmp(mps.field0(), "BOUNDS"))
310  mps.setSection(MPSInput::BOUNDS);
311  else if (!strcmp(mps.field0(), "ENDATA"))
312  mps.setSection(MPSInput::ENDATA);
313  else
314  break;
315 
316  return;
317  }
318  if (((mps.field2() != 0) && (mps.field3() == 0))
319  || ((mps.field4() != 0) && (mps.field5() == 0)))
320  mps.insertName("_RHS_");
321 
322  if ((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
323  break;
324 
325  if (*rhsname == '\0')
326  strcpy(rhsname, mps.field1());
327 
328  if (strcmp(rhsname, mps.field1()))
329  {
330  if (strcmp(addname, mps.field1()))
331  {
332  assert(strlen(mps.field1()) < MPSInput::MAX_LINE_LEN);
333  strcpy(addname, mps.field1());
334  MSG_INFO3( spxout << "IMPSRD07 RHS ignored : " << addname
335  << std::endl; );
336  }
337  }
338  else
339  {
340  if ((idx = rnames.number(mps.field2())) < 0)
341  mps.entryIgnored("RHS", mps.field1(), "row", mps.field2());
342  else
343  {
344  val = atof(mps.field3());
345 
346  // LE or EQ
347  if (rset.rhs(idx) < infinity)
348  rset.rhs_w(idx) = val;
349  // GE or EQ
350  if (rset.lhs(idx) > -infinity)
351  rset.lhs_w(idx) = val;
352  }
353  if (mps.field5() != 0)
354  {
355  if ((idx = rnames.number(mps.field4())) < 0)
356  mps.entryIgnored("RHS", mps.field1(), "row", mps.field4());
357  else
358  {
359  val = atof(mps.field5());
360 
361  // LE or EQ
362  if (rset.rhs(idx) < infinity)
363  rset.rhs_w(idx) = val;
364  // GE or EQ
365  if (rset.lhs(idx) > -infinity)
366  rset.lhs_w(idx) = val;
367  }
368  }
369  }
370  }
371  mps.syntaxError();
372 }
373 
374 /// Process RANGES section.
375 static void readRanges(
376  MPSInput& mps,
377  LPRowSet& rset,
378  const NameSet& rnames)
379 {
380  char rngname[MPSInput::MAX_LINE_LEN] = { '\0' };
381  int idx;
382  Real val;
383 
384  while(mps.readLine())
385  {
386  if (mps.field0() != 0)
387  {
388  MSG_INFO2( spxout << "IMPSRD04 Range name : " << rngname
389  << std::endl; );
390 
391  if (!strcmp(mps.field0(), "BOUNDS"))
392  mps.setSection(MPSInput::BOUNDS);
393  else if (!strcmp(mps.field0(), "ENDATA"))
394  mps.setSection(MPSInput::ENDATA);
395  else
396  break;
397 
398  return;
399  }
400  if (((mps.field2() != 0) && (mps.field3() == 0))
401  || ((mps.field4() != 0) && (mps.field5() == 0)))
402  mps.insertName("_RNG_");
403 
404  if ((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
405  break;
406 
407  if (*rngname == '\0')
408  {
409  assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN);
410  strcpy(rngname, mps.field1());
411  }
412 
413  /* The rules are:
414  * Row Sign LHS RHS
415  * ----------------------------------------
416  * G +/- rhs rhs + |range|
417  * L +/- rhs - |range| rhs
418  * E + rhs rhs + range
419  * E - rhs + range rhs
420  * ----------------------------------------
421  */
422  if (!strcmp(rngname, mps.field1()))
423  {
424  if ((idx = rnames.number(mps.field2())) < 0)
425  mps.entryIgnored("Range", mps.field1(), "row", mps.field2());
426  else
427  {
428  val = atof(mps.field3());
429 
430  // EQ
431  if ( (rset.lhs(idx) > -infinity)
432  && (rset.rhs_w(idx) < infinity))
433  {
434  assert(rset.lhs(idx) == rset.rhs(idx));
435 
436  if (val >= 0)
437  rset.rhs_w(idx) += val;
438  else
439  rset.lhs_w(idx) += val;
440  }
441  else
442  {
443  // GE
444  if (rset.lhs(idx) > -infinity)
445  rset.rhs_w(idx) = rset.lhs(idx) + fabs(val);
446  else // LE
447  rset.lhs_w(idx) = rset.rhs(idx) - fabs(val);
448  }
449  }
450  if (mps.field5() != 0)
451  {
452  if ((idx = rnames.number(mps.field4())) < 0)
453  mps.entryIgnored("Range", mps.field1(), "row", mps.field4());
454  else
455  {
456  val = atof(mps.field5());
457 
458  // EQ
459  if ( (rset.lhs(idx) > -infinity)
460  && (rset.rhs(idx) < infinity))
461  {
462  assert(rset.lhs(idx) == rset.rhs(idx));
463 
464  if (val >= 0)
465  rset.rhs_w(idx) += val;
466  else
467  rset.lhs_w(idx) += val;
468  }
469  else
470  {
471  // GE
472  if (rset.lhs(idx) > -infinity)
473  rset.rhs_w(idx) = rset.lhs(idx) + fabs(val);
474  else // LE
475  rset.lhs_w(idx) = rset.rhs(idx) - fabs(val);
476  }
477  }
478  }
479  }
480  }
481  mps.syntaxError();
482 }
483 
484 /// Process BOUNDS section.
485 static void readBounds(
486  MPSInput& mps,
487  LPColSet& cset,
488  const NameSet& cnames,
489  DIdxSet* intvars)
490 {
491  char bndname[MPSInput::MAX_LINE_LEN] = { '\0' };
492  int idx;
493  Real val;
494 
495  while(mps.readLine())
496  {
497  if (mps.field0() != 0)
498  {
499  MSG_INFO2( spxout << "IMPSRD05 Bound name : " << bndname
500  << std::endl; )
501 
502  if (strcmp(mps.field0(), "ENDATA"))
503  break;
504 
505  mps.setSection(MPSInput::ENDATA);
506  return;
507  }
508  // Is the value field used ?
509  if ( (!strcmp(mps.field1(), "LO"))
510  || (!strcmp(mps.field1(), "UP"))
511  || (!strcmp(mps.field1(), "FX"))
512  || (!strcmp(mps.field1(), "LI"))
513  || (!strcmp(mps.field1(), "UI")))
514  {
515  if ((mps.field3() != 0) && (mps.field4() == 0))
516  mps.insertName("_BND_", true);
517  }
518  else
519  {
520  if ((mps.field2() != 0) && (mps.field3() == 0))
521  mps.insertName("_BND_", true);
522  }
523 
524  if ((mps.field1() == 0) || (mps.field2() == 0) || (mps.field3() == 0))
525  break;
526 
527  if (*bndname == '\0')
528  {
529  assert(strlen(mps.field2()) < MPSInput::MAX_LINE_LEN);
530  strcpy(bndname, mps.field2());
531  }
532 
533  // Only read the first Bound in section
534  if (!strcmp(bndname, mps.field2()))
535  {
536  if ((idx = cnames.number(mps.field3())) < 0)
537  mps.entryIgnored("column", mps.field3(), "bound", bndname);
538  else
539  {
540  val = (mps.field4() == 0) ? 0.0 : atof(mps.field4());
541 
542  switch(*mps.field1())
543  {
544  case 'L':
545  cset.lower_w(idx) = val;
546 
547  // ILOG extension (Integer Lower Bound)
548  if ((intvars != 0) && (mps.field1()[1] == 'I'))
549  intvars->addIdx(idx);
550  break;
551  case 'U':
552  cset.upper_w(idx) = val;
553 
554  // ILOG extension (Integer Upper Bound)
555  if ((intvars != 0) && (mps.field1()[1] == 'I'))
556  intvars->addIdx(idx);
557  break;
558  case 'F':
559  if (mps.field1()[1] == 'X')
560  {
561  cset.lower_w(idx) = val;
562  cset.upper_w(idx) = val;
563  }
564  else
565  {
566  cset.lower_w(idx) = -infinity;
567  cset.upper_w(idx) = infinity;
568  }
569  break;
570  case 'M':
571  cset.lower_w(idx) = -infinity;
572  break;
573  case 'P':
574  cset.upper_w(idx) = infinity;
575  break;
576  case 'B' : // Ilog extension (Binary)
577  cset.lower_w(idx) = 0.0;
578  cset.upper_w(idx) = 1.0;
579 
580  if (intvars != 0)
581  intvars->addIdx(idx);
582  break;
583  default:
584  mps.syntaxError();
585  return;
586  }
587  }
588  }
589  }
590  mps.syntaxError();
591 }
592 
593 /// Read LP in "MPS File Format".
594 /**
595  * The specification is taken from the
596  *
597  * IBM Optimization Library Guide and Reference
598  *
599  * Online available at http://www.software.ibm.com/sos/features/libuser.htm
600  *
601  * and from the
602  *
603  * ILOG CPLEX 7.0 Reference Manual, Appendix E, Page 531.
604  *
605  * This routine should read all valid MPS format files.
606  * What it will not do, is find all cases where a file is ill formed.
607  * If this happens it may complain and read nothing or read "something".
608  *
609  * @return true if the file was read correctly.
610  */
611 bool SPxLP::readMPS(
612  std::istream& p_input, ///< input stream.
613  NameSet* p_rnames, ///< row names.
614  NameSet* p_cnames, ///< column names.
615  DIdxSet* p_intvars) ///< integer variables.
616 {
617  LPRowSet& rset = *this;
618  LPColSet& cset = *this;
619  NameSet* rnames; ///< row names.
620  NameSet* cnames; ///< column names.
621 
622  cnames = (p_cnames != 0)
623  ? p_cnames : new NameSet();
624 
625  cnames->clear();
626 
627  try
628  {
629  rnames = (p_rnames != 0)
630  ? p_rnames : new NameSet();
631  }catch(std::bad_alloc& x)
632  {
633  if(p_cnames == 0)
634  delete cnames;
635  throw x;
636  }
637 
638  rnames->clear();
639 
640  SPxLP::clear(); // clear the LP.
641 
642  cset.memRemax(INIT_NZOS);
643  cset.reMax(INIT_COLS);
644 
645  MPSInput mps(p_input);
646 
647  readName(mps);
648 
649  if (mps.section() == MPSInput::OBJSEN)
650  readObjsen(mps);
651 
652  if (mps.section() == MPSInput::OBJNAME)
653  readObjname(mps);
654 
655  if (mps.section() == MPSInput::ROWS)
656  readRows(mps, rset, *rnames);
657 
658  addedRows(rset.num());
659 
660  if (mps.section() == MPSInput::COLUMNS)
661  readCols(mps, rset, *rnames, cset, *cnames, p_intvars);
662 
663  if (mps.section() == MPSInput::RHS)
664  readRhs(mps, rset, *rnames);
665 
666  if (mps.section() == MPSInput::RANGES)
667  readRanges(mps, rset, *rnames);
668 
669  if (mps.section() == MPSInput::BOUNDS)
670  readBounds(mps, cset, *cnames, p_intvars);
671 
672  if (mps.section() != MPSInput::ENDATA)
673  mps.syntaxError();
674 
675  if (mps.hasError())
676  clear();
677  else
678  {
679  changeSense(mps.objSense());
680 
681  MSG_INFO2(
682  spxout << "IMPSRD06 Objective sense: "
683  << ((mps.objSense() == MINIMIZE) ? "Minimize" : "Maximize")
684  << std::endl;
685  )
686 
687  added2Set(
688  *(reinterpret_cast<SVSet*>(static_cast<LPRowSet*>(this))),
689  *(reinterpret_cast<SVSet*>(static_cast<LPColSet*>(this))),
690  cset.num());
691  addedCols(cset.num());
692  assert(isConsistent());
693  }
694 
695  if (p_cnames == 0)
696  delete cnames;
697  if (p_rnames == 0)
698  delete rnames;
699 
700  return !mps.hasError();
701 }
702 
703 } // namespace soplex
704 
705 //-----------------------------------------------------------------------------
706 //Emacs Local Variables:
707 //Emacs mode:c++
708 //Emacs c-basic-offset:3
709 //Emacs tab-width:8
710 //Emacs indent-tabs-mode:nil
711 //Emacs End:
712 //-----------------------------------------------------------------------------
© 2003-2013 by Zuse Institute Berlin (ZIB), Imprint Generated on Wed Jan 9 2013 for SoPlex by doxygen