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

Last change on this file since 591 was 591, checked in by lou, 13 years ago

Initial commit of cbc-generic source.

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