source: trunk/Cbc/src/CbcGenSolution.cpp @ 1899

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

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