source: branches/devel/Cbc/src/CbcGenSolution.cpp @ 608

Last change on this file since 608 was 608, checked in by lou, 12 years ago

Cbc-generic: Add message handler, separate libCbc and cbc-generic main log
level parameters.

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