source: trunk/Cbc/src/CbcGenSolution.cpp

Last change on this file was 2467, checked in by unxusr, 6 months ago

spaces after angles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.3 KB
Line 
1/*
2  Copyright (C) 2007, Lou Hafer, International Business Machines Corporation
3  and others.  All Rights Reserved.
4
5  This code is licensed under the terms of the Eclipse Public License (EPL).
6
7  $Id: CbcGenSolution.cpp 2467 2019-01-03 21:26:29Z tkr $
8*/
9/*
10  This file is part of cbc-generic.
11*/
12
13#include <string>
14#include <cstdio>
15#include <cassert>
16
17#include "CoinHelperFunctions.hpp"
18#include "CoinSort.hpp"
19#include "CoinFileIO.hpp"
20
21#include "CbcGenCtlBlk.hpp"
22#include "CbcGenParam.hpp"
23
24namespace {
25
26char svnid[] = "$Id: CbcGenSolution.cpp 2467 2019-01-03 21:26:29Z tkr $";
27
28}
29
30namespace {
31
32/*
33  Helper routine to generate masks for selecting names to print. Returns true
34  if masks are generated without error, false otherwise.
35
36  This is John Forrest's code, shamelessly stolen from CoinSolve and tweaked
37  just enough to allow it to be yanked out of the main body of CoinSolve.
38
39  Returns the number of generated masks, -1 on error.
40*/
41
42int generateMasks(std::string proto, int longestName,
43  int *&maskStarts, char **&finalMasks)
44
45{
46  int nAst = 0;
47  const char *pMask2 = proto.c_str();
48  char pMask[100];
49  int iChar;
50  int lengthMask = strlen(pMask2);
51  assert(lengthMask < 100);
52
53  int maxMasks = -1;
54
55  maskStarts = 0;
56  finalMasks = 0;
57  /*
58      Remove surrounding matched quotes if present. Abort if unmatched.
59    */
60  if (*pMask2 == '"') {
61    if (pMask2[lengthMask - 1] != '"') {
62      printf("generateMasks: Mismatched \" in mask %s\n", pMask2);
63      return (-1);
64    } else {
65      strcpy(pMask, pMask2 + 1);
66      *strchr(pMask, '"') = '\0';
67    }
68  } else if (*pMask2 == '\'') {
69    if (pMask2[lengthMask - 1] != '\'') {
70      printf("mismatched ' in mask %s\n", pMask2);
71      return (maxMasks);
72    } else {
73      strcpy(pMask, pMask2 + 1);
74      *strchr(pMask, '\'') = '\0';
75    }
76  } else {
77    strcpy(pMask, pMask2);
78  }
79  /*
80      Mask should not be longer than longest name.
81    */
82  if (lengthMask > longestName) {
83    printf("mask %s too long - skipping\n", pMask);
84    return (maxMasks);
85  }
86  /*
87      Expand `*' to multiple masks with varying number of `?' characters.
88    */
89  maxMasks = 1;
90  for (iChar = 0; iChar < lengthMask; iChar++) {
91    if (pMask[iChar] == '*') {
92      nAst++;
93      maxMasks *= (longestName + 1);
94    }
95  }
96  int nEntries = 1;
97  maskStarts = new int[longestName + 2];
98  char **masks = new char *[maxMasks];
99  char **newMasks = new char *[maxMasks];
100  int i;
101  for (i = 0; i < maxMasks; i++) {
102    masks[i] = new char[longestName + 1];
103    newMasks[i] = new char[longestName + 1];
104  }
105  strcpy(masks[0], pMask);
106  for (int iAst = 0; iAst < nAst; iAst++) {
107    int nOldEntries = nEntries;
108    nEntries = 0;
109    for (int iEntry = 0; iEntry < nOldEntries; iEntry++) {
110      char *oldMask = masks[iEntry];
111      char *ast = strchr(oldMask, '*');
112      assert(ast);
113      int length = strlen(oldMask) - 1;
114      int nBefore = ast - oldMask;
115      int nAfter = length - nBefore;
116      // and add null
117      nAfter++;
118      for (int i = 0; i <= longestName - length; i++) {
119        char *maskOut = newMasks[nEntries];
120        memcpy(maskOut, oldMask, nBefore);
121        for (int k = 0; k < i; k++)
122          maskOut[k + nBefore] = '?';
123        memcpy(maskOut + nBefore + i, ast + 1, nAfter);
124        nEntries++;
125        assert(nEntries <= maxMasks);
126      }
127    }
128    char **temp = masks;
129    masks = newMasks;
130    newMasks = temp;
131  }
132  /*
133      Trim trailing blanks and record final length.
134    */
135  int *sort = new int[nEntries];
136  for (i = 0; i < nEntries; i++) {
137    char *maskThis = masks[i];
138    int length = strlen(maskThis);
139    while (maskThis[length - 1] == ' ')
140      length--;
141    maskThis[length] = '\0';
142    sort[i] = length;
143  }
144  /*
145      Sort by length.
146    */
147  CoinSort_2(sort, sort + nEntries, masks);
148  int lastLength = -1;
149  for (i = 0; i < nEntries; i++) {
150    int length = sort[i];
151    while (length > lastLength)
152      maskStarts[++lastLength] = i;
153  }
154  maskStarts[++lastLength] = nEntries;
155  delete[] sort;
156  for (i = 0; i < maxMasks; i++)
157    delete[] newMasks[i];
158  delete[] newMasks;
159
160  finalMasks = masks;
161
162  return (maxMasks);
163}
164
165/*
166  Utility routine to check a string against the array of masks. Borrowed
167  from CoinSolve.
168*/
169
170bool maskMatches(const int *starts, char **masks, const char *checkC)
171
172{
173  int length = strlen(checkC);
174  while (checkC[length - 1] == ' ')
175    length--;
176  for (int i = starts[length]; i < starts[length + 1]; i++) {
177    char *thisMask = masks[i];
178    int k;
179    for (k = 0; k < length; k++) {
180      if (thisMask[k] != '?' && thisMask[k] != checkC[k])
181        break;
182    }
183    if (k == length)
184      return true;
185  }
186  return (false);
187}
188
189} // end unnamed namespace
190
191/*
192  Routine to write out the solution. Minimally adapted from John's code in
193  CoinSolve to break out a few subroutines and use generic OSI functions.
194
195  The print mode is established by the printingOptions command, and the integer
196  coding is established by the order of declaration of the keyword parameters.
197  As of 060920, known modes are
198
199    normal (0)    print nonzero primal variables
200    integer (1)   print nonzero integer primal variables
201    special (2)   print in a format suitable for OsiRowCutDebugger
202    rows (3)      `normal', plus rows with nonzero row activity
203    all (4)       all primal variables and row activities
204*/
205
206int CbcGenParamUtils::doSolutionParam(CoinParam *param)
207
208{
209  assert(param != 0);
210  CbcGenParam *genParam = dynamic_cast< CbcGenParam * >(param);
211  assert(genParam != 0);
212  CbcGenCtlBlk *ctlBlk = genParam->obj();
213  assert(ctlBlk != 0);
214  CbcModel *model = ctlBlk->model_;
215  assert(model != 0);
216  /*
217      Setup to return nonfatal/fatal error (1/-1) by default.
218    */
219  int retval;
220  if (CoinParamUtils::isInteractive()) {
221    retval = 1;
222  } else {
223    retval = -1;
224  }
225  /*
226      It's hard to print a solution we don't have.
227    */
228  if (ctlBlk->bab_.haveAnswer_ == false) {
229    std::cout << "There is no solution available to print." << std::endl;
230    return (retval);
231  }
232  OsiSolverInterface *osi = ctlBlk->bab_.answerSolver_;
233  assert(osi != 0);
234  /*
235      Figure out where we're going to write the solution. As special cases,
236      `$' says `use the previous output file' and `-' says `use stdout'.
237
238      cbc will also accept `no string value' as stdout, but that'd be a real pain
239      in this architecture.
240    */
241  std::string field = genParam->strVal();
242  std::string fileName;
243  if (field == "$") {
244    fileName = ctlBlk->lastSolnOut_;
245    field = fileName;
246  }
247  if (field == "-") {
248    fileName = "stdout";
249    field = fileName;
250  } else {
251    fileName = field;
252  }
253  if (!(fileName == "stdout" || fileName == "stderr")) {
254    if (fileName[0] == '~') {
255      char dirSep = CoinFindDirSeparator();
256      if (fileName[1] == dirSep) {
257        char *environVar = getenv("HOME");
258        if (environVar) {
259          std::string home(environVar);
260          fileName = home + fileName.substr(1);
261        }
262      }
263    }
264    if (!(fileAbsPath(fileName) || fileName.substr(0, 2) == "./")) {
265      fileName = ctlBlk->dfltDirectory_ + fileName;
266    }
267  }
268  /*
269      See if we can open the file. Bail out if the open fails.
270    */
271  FILE *fp;
272  if (fileName == "stdout") {
273    fp = stdout;
274  } else if (fileName == "stderr") {
275    fp = stderr;
276  } else {
277    fp = fopen(fileName.c_str(), "w");
278    fp = fopen(fileName.c_str(), "w");
279  }
280  if (!fp) {
281    std::cout
282      << "Unable to open file `" << fileName
283      << "', original name '" << genParam->strVal() << "'." << std::endl;
284    return (retval);
285  } else {
286    std::cout
287      << "Writing solution to `" << fileName << "'." << std::endl;
288  }
289
290  int m = osi->getNumRows();
291  int n = osi->getNumCols();
292  int iColumn;
293  const double *primalColSolution = osi->getColSolution();
294  /*
295      Separate printing a solution for humans from printing a solution for the
296      row cut debugger. For the row cut debugger, we want to produce C++ code
297      that can be pasted into the debugger's set of known problems.
298    */
299  if (ctlBlk->printMode_ == 2) {
300    int k = 0;
301    bool newLine = true;
302    bool comma = false;
303    fprintf(fp, "  int intIndicesV[] = {");
304    for (iColumn = 0; iColumn < n; iColumn++) {
305      if (fabs(primalColSolution[iColumn]) > 0.5 && osi->isInteger(iColumn)) {
306        if (newLine) {
307          fprintf(fp, "\n\t");
308          newLine = false;
309        } else {
310          fprintf(fp, ", ");
311        }
312        fprintf(fp, "%d", iColumn);
313        if (++k == 10) {
314          k = 0;
315          newLine = true;
316        }
317      }
318    }
319    fprintf(fp, "\n      } ;\n");
320    k = 0;
321    newLine = true;
322    fprintf(fp, "  double intSolnV[] = {");
323    for (iColumn = 0; iColumn < n; iColumn++) {
324      double value = primalColSolution[iColumn];
325      if (fabs(value) > 0.5 && osi->isInteger(iColumn)) {
326        if (newLine) {
327          fprintf(fp, "\n\t");
328          newLine = false;
329        } else {
330          fprintf(fp, ", ");
331        }
332        if (value > 0) {
333          value = floor(value + .5);
334        } else {
335          value = ceil(value - .5);
336        }
337        int ivalue = static_cast< int >(value);
338        fprintf(fp, "%d.0", ivalue);
339        if (++k == 10) {
340          k = 0;
341          newLine = true;
342        }
343      }
344    }
345    fprintf(fp, "\n      } ;\n");
346    return (0);
347  }
348  /*
349      Begin the code to generate output meant for a human.  What's our longest
350      name? Scan the names we're going to print. printMode_ of 3 or 4 requires we
351      scan the row names too. Force between 8 and 20 characters in any event.
352    */
353  int longestName = 0;
354  for (int j = 0; j < n; j++) {
355    int len = osi->getColName(j).length();
356    longestName = CoinMax(longestName, len);
357  }
358  if (ctlBlk->printMode_ >= 3) {
359    for (int i = 0; i < m; i++) {
360      int len = osi->getRowName(i).length();
361      longestName = CoinMax(longestName, len);
362    }
363  }
364  /*
365      Generate masks if we need to do so.
366    */
367  bool doMask = ctlBlk->printMask_ != "";
368  int *maskStarts = NULL;
369  int maxMasks = 0;
370  char **masks = NULL;
371  if (doMask) {
372    maxMasks = generateMasks(ctlBlk->printMask_, longestName, maskStarts, masks);
373    if (maxMasks < 0) {
374      return (retval);
375    }
376  }
377  /*
378      Force the space allocated to names to be between 8 and 20 characters.
379    */
380  if (longestName < 8) {
381    longestName = 8;
382  } else if (longestName > 20) {
383    longestName = 20;
384  }
385  /*
386      Print requested components of the row solution. Only modes 3 (rows) and 4
387      (all) will print row information. For the rows that we print, print both
388      the row activity and the value of the associated dual.
389
390      Which to print? Violated constraints will always be flagged to print.
391      Otherwise, if m < 50 or all rows are requested, print all rows.  Otherwise,
392      print tight constraints (non-zero dual).
393
394      All of this is filtered through printMask, if specified.
395    */
396  double primalTolerance;
397  osi->getDblParam(OsiPrimalTolerance, primalTolerance);
398
399  int iRow;
400  if (ctlBlk->printMode_ >= 3) {
401    const double *dualRowSolution = osi->getRowPrice();
402    const double *primalRowSolution = osi->getRowActivity();
403    const double *rowLower = osi->getRowLower();
404    const double *rowUpper = osi->getRowUpper();
405
406    fprintf(fp, "\n   %7s %-*s%15s%15s\n\n",
407      "Index", longestName, "Row", "Activity", "Dual");
408
409    for (iRow = 0; iRow < m; iRow++) {
410      bool violated = false;
411      bool print = false;
412      if (primalRowSolution[iRow] > rowUpper[iRow] + primalTolerance || primalRowSolution[iRow] < rowLower[iRow] - primalTolerance) {
413        violated = true;
414        print = true;
415      } else {
416        if (m < 50 || ctlBlk->printMode_ >= 4) {
417          print = true;
418        } else if (fabs(dualRowSolution[iRow]) > 1.0e-8) {
419          print = true;
420        }
421      }
422      const char *name = osi->getRowName(iRow).c_str();
423      if (doMask && !maskMatches(maskStarts, masks, name)) {
424        print = false;
425      }
426      if (print) {
427        if (violated) {
428          fprintf(fp, "** ");
429        } else {
430          fprintf(fp, "%3s", " ");
431        }
432        fprintf(fp, "%7d %-*s%15.8g%15.8g\n", iRow, longestName, name,
433          primalRowSolution[iRow], dualRowSolution[iRow]);
434      }
435    }
436    fprintf(fp, "\n");
437  }
438  /*
439      Now do the columns. This first block handles all modes except 2 (special).
440      Out-of-bounds variables are flagged with `**'. If there are less than 50
441      variables, all are printed. All of this is filtered through `integer only'
442      and can be further filtered using printMask.
443    */
444  if (ctlBlk->printMode_ != 2) {
445    const double *columnLower = osi->getColLower();
446    const double *columnUpper = osi->getColUpper();
447    const double *dualColSolution = osi->getReducedCost();
448
449    fprintf(fp, "\n   %7s %-*s%15s%15s\n\n",
450      "Index", longestName, "Column", "Value", "Reduced Cost");
451
452    for (iColumn = 0; iColumn < n; iColumn++) {
453      bool violated = false;
454      bool print = false;
455      if (primalColSolution[iColumn] > columnUpper[iColumn] + primalTolerance || primalColSolution[iColumn] < columnLower[iColumn] - primalTolerance) {
456        violated = true;
457        print = true;
458      } else {
459        if (n < 50 || ctlBlk->printMode_ == 4) {
460          print = true;
461        } else if (fabs(primalColSolution[iColumn]) > 1.0e-8) {
462          if (ctlBlk->printMode_ == 1) {
463            print = osi->isInteger(iColumn);
464          } else {
465            print = true;
466          }
467        }
468      }
469      const char *name = osi->getColName(iColumn).c_str();
470      if (doMask && !maskMatches(maskStarts, masks, name)) {
471        print = false;
472      }
473      if (print) {
474        if (violated) {
475          fprintf(fp, "** ");
476        } else {
477          fprintf(fp, "%3s", " ");
478        }
479        fprintf(fp, "%7d %-*s%15.8g%15.8g\n", iColumn, longestName, name,
480          primalColSolution[iColumn], dualColSolution[iColumn]);
481      }
482    }
483  }
484  /*
485      Close out the file, but don't close stdout. Delete any masks.
486    */
487  if (fp != stdout) {
488    fclose(fp);
489  }
490
491  if (masks) {
492    delete[] maskStarts;
493    for (int i = 0; i < maxMasks; i++)
494      delete[] masks[i];
495    delete[] masks;
496  }
497
498  return (0);
499}
500
501/*
502  Routine to do initial verification of a print mask. We don't generate the
503  full set of print masks here, but we do some verification checks to make sure
504  it's valid.
505*/
506
507int CbcGenParamUtils::doPrintMaskParam(CoinParam *param)
508
509{
510  assert(param != 0);
511  CbcGenParam *genParam = dynamic_cast< CbcGenParam * >(param);
512  assert(genParam != 0);
513  CbcGenCtlBlk *ctlBlk = genParam->obj();
514  assert(ctlBlk != 0);
515  /*
516      Setup to return nonfatal/fatal error (1/-1) by default.
517    */
518  int retval;
519  if (CoinParamUtils::isInteractive()) {
520    retval = 1;
521  } else {
522    retval = -1;
523  }
524  /*
525      Now do a bit of verification of the mask. It should be non-null and, if
526      quoted, the quotes should be matched. Aribtrarily put the absolute maximum
527      length at 50 characters. If we have a model loaded, that'll be tightened to
528      the length of the longest name.
529    */
530  std::string maskProto = param->strVal();
531  int maskLen = maskProto.length();
532  if (maskLen <= 0 || maskLen > 50) {
533    std::cerr
534      << "Mask |" << maskProto
535      << "| is " << maskLen << " characters; should be between "
536      << 0 << " and " << 50 << "." << std::endl;
537    return (retval);
538  }
539  /*
540      Remove surrounding matched quotes if present. Abort if unmatched.
541    */
542  if (maskProto[0] == '"' || maskProto[0] == '\'') {
543    char quoteChar = maskProto[0];
544    if (maskProto[maskLen - 1] != quoteChar) {
545      std::cerr
546        << "Mismatched quotes around mask |" << maskProto
547        << "|." << std::endl;
548      return (retval);
549    } else {
550      maskProto = maskProto.substr(1, maskLen - 2);
551    }
552  }
553  /*
554      Mask should not be longer than longest name. Of course, if we don't have a
555      model, we can't do this check.
556    */
557  if (ctlBlk->goodModel_) {
558    CbcModel *model = ctlBlk->model_;
559    assert(model != 0);
560    OsiSolverInterface *osi = model->solver();
561    assert(osi != 0);
562    int longestName = 0;
563    int n = osi->getNumCols();
564    for (int j = 0; j < n; j++) {
565      int len = osi->getColName(j).length();
566      longestName = CoinMax(longestName, len);
567    }
568    int m = osi->getNumRows();
569    for (int i = 0; i < m; i++) {
570      int len = osi->getRowName(i).length();
571      longestName = CoinMax(longestName, len);
572    }
573    if (maskLen > longestName) {
574      std::cerr
575        << "Mask |" << maskProto << "| has " << maskLen << " chars; this"
576        << " is longer than the longest name (" << longestName
577        << " chars)." << std::endl;
578      return (retval);
579    }
580  }
581
582  ctlBlk->printMask_ = maskProto;
583
584  return (0);
585}
586
587/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
588*/
Note: See TracBrowser for help on using the repository browser.