source: trunk/Cbc/src/CbcSolverAnalyze.cpp @ 2071

Last change on this file since 2071 was 2071, checked in by unxusr, 4 years ago

double free, as reported by coverity

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.1 KB
Line 
1/* $Id: CbcSolverAnalyze.cpp 2071 2014-09-14 00:31:24Z unxusr $ */
2// Copyright (C) 2007, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6/*! \file CbcSolverAnalyze.cpp
7
8  Look to see if a constraint is all-integer (variables & coeffs), or could be
9  all integer. Consider whether one or two continuous variables can be declared
10  integer. John's comment is that integer preprocessing might do a better job,
11  so we should consider whether this routine should stay.
12
13  No hurry to get rid of it, in my opinion  -- lh, 091210 --
14
15*/
16
17#include "CbcConfig.h"
18#include "CoinPragma.hpp"
19
20#include "OsiClpSolverInterface.hpp"
21
22#include "ClpMessage.hpp"
23
24#include "CbcModel.hpp"
25
26
27#ifndef CBC_OTHER_SOLVER
28
29int * analyze(OsiClpSolverInterface * solverMod, int & numberChanged,
30                     double & increment, bool changeInt,
31                     CoinMessageHandler * generalMessageHandler, bool noPrinting)
32{
33    bool noPrinting_ = noPrinting;
34    OsiSolverInterface * solver = solverMod->clone();
35    char generalPrint[200];
36    if (0) {
37        // just get increment
38        CbcModel model(*solver);
39        model.analyzeObjective();
40        double increment2 = model.getCutoffIncrement();
41        printf("initial cutoff increment %g\n", increment2);
42    }
43    const double *objective = solver->getObjCoefficients() ;
44    const double *lower = solver->getColLower() ;
45    const double *upper = solver->getColUpper() ;
46    int numberColumns = solver->getNumCols() ;
47    int numberRows = solver->getNumRows();
48    double direction = solver->getObjSense();
49    int iRow, iColumn;
50
51    // Row copy
52    CoinPackedMatrix matrixByRow(*solver->getMatrixByRow());
53    const double * elementByRow = matrixByRow.getElements();
54    const int * column = matrixByRow.getIndices();
55    const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
56    const int * rowLength = matrixByRow.getVectorLengths();
57
58    // Column copy
59    CoinPackedMatrix  matrixByCol(*solver->getMatrixByCol());
60    const double * element = matrixByCol.getElements();
61    const int * row = matrixByCol.getIndices();
62    const CoinBigIndex * columnStart = matrixByCol.getVectorStarts();
63    const int * columnLength = matrixByCol.getVectorLengths();
64
65    const double * rowLower = solver->getRowLower();
66    const double * rowUpper = solver->getRowUpper();
67
68    char * ignore = new char [numberRows];
69    int * changed = new int[numberColumns];
70    int * which = new int[numberRows];
71    double * changeRhs = new double[numberRows];
72    memset(changeRhs, 0, numberRows*sizeof(double));
73    memset(ignore, 0, numberRows);
74    numberChanged = 0;
75    int numberInteger = 0;
76    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
77        if (upper[iColumn] > lower[iColumn] + 1.0e-8 && solver->isInteger(iColumn))
78            numberInteger++;
79    }
80    bool finished = false;
81    while (!finished) {
82        int saveNumberChanged = numberChanged;
83        for (iRow = 0; iRow < numberRows; iRow++) {
84            int numberContinuous = 0;
85            double value1 = 0.0, value2 = 0.0;
86            bool allIntegerCoeff = true;
87            double sumFixed = 0.0;
88            int jColumn1 = -1, jColumn2 = -1;
89            for (CoinBigIndex j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) {
90                int jColumn = column[j];
91                double value = elementByRow[j];
92                if (upper[jColumn] > lower[jColumn] + 1.0e-8) {
93                    if (!solver->isInteger(jColumn)) {
94                        if (numberContinuous == 0) {
95                            jColumn1 = jColumn;
96                            value1 = value;
97                        } else {
98                            jColumn2 = jColumn;
99                            value2 = value;
100                        }
101                        numberContinuous++;
102                    } else {
103                        if (fabs(value - floor(value + 0.5)) > 1.0e-12)
104                            allIntegerCoeff = false;
105                    }
106                } else {
107                    sumFixed += lower[jColumn] * value;
108                }
109            }
110            double low = rowLower[iRow];
111            if (low > -1.0e20) {
112                low -= sumFixed;
113                if (fabs(low - floor(low + 0.5)) > 1.0e-12)
114                    allIntegerCoeff = false;
115            }
116            double up = rowUpper[iRow];
117            if (up < 1.0e20) {
118                up -= sumFixed;
119                if (fabs(up - floor(up + 0.5)) > 1.0e-12)
120                    allIntegerCoeff = false;
121            }
122            if (!allIntegerCoeff)
123                continue; // can't do
124            if (numberContinuous == 1) {
125                // see if really integer
126                // This does not allow for complicated cases
127                if (low == up) {
128                    if (fabs(value1) > 1.0e-3) {
129                        value1 = 1.0 / value1;
130                        if (fabs(value1 - floor(value1 + 0.5)) < 1.0e-12) {
131                            // integer
132                            changed[numberChanged++] = jColumn1;
133                            solver->setInteger(jColumn1);
134                            if (upper[jColumn1] > 1.0e20)
135                                solver->setColUpper(jColumn1, 1.0e20);
136                            if (lower[jColumn1] < -1.0e20)
137                                solver->setColLower(jColumn1, -1.0e20);
138                        }
139                    }
140                } else {
141                    if (fabs(value1) > 1.0e-3) {
142                        value1 = 1.0 / value1;
143                        if (fabs(value1 - floor(value1 + 0.5)) < 1.0e-12) {
144                            // This constraint will not stop it being integer
145                            ignore[iRow] = 1;
146                        }
147                    }
148                }
149            } else if (numberContinuous == 2) {
150                if (low == up) {
151                    /* need general theory - for now just look at 2 cases -
152                       1 - +- 1 one in column and just costs i.e. matching objective
153                       2 - +- 1 two in column but feeds into G/L row which will try and minimize
154                    */
155                    if (fabs(value1) == 1.0 && value1*value2 == -1.0 && !lower[jColumn1]
156                            && !lower[jColumn2]) {
157                        int n = 0;
158                        int i;
159                        double objChange = direction * (objective[jColumn1] + objective[jColumn2]);
160                        double bound = CoinMin(upper[jColumn1], upper[jColumn2]);
161                        bound = CoinMin(bound, 1.0e20);
162                        for ( i = columnStart[jColumn1]; i < columnStart[jColumn1] + columnLength[jColumn1]; i++) {
163                            int jRow = row[i];
164                            double value = element[i];
165                            if (jRow != iRow) {
166                                which[n++] = jRow;
167                                changeRhs[jRow] = value;
168                            }
169                        }
170                        for ( i = columnStart[jColumn1]; i < columnStart[jColumn1] + columnLength[jColumn1]; i++) {
171                            int jRow = row[i];
172                            double value = element[i];
173                            if (jRow != iRow) {
174                                if (!changeRhs[jRow]) {
175                                    which[n++] = jRow;
176                                    changeRhs[jRow] = value;
177                                } else {
178                                    changeRhs[jRow] += value;
179                                }
180                            }
181                        }
182                        if (objChange >= 0.0) {
183                            // see if all rows OK
184                            bool good = true;
185                            for (i = 0; i < n; i++) {
186                                int jRow = which[i];
187                                double value = changeRhs[jRow];
188                                if (value) {
189                                    value *= bound;
190                                    if (rowLength[jRow] == 1) {
191                                        if (value > 0.0) {
192                                            double rhs = rowLower[jRow];
193                                            if (rhs > 0.0) {
194                                                double ratio = rhs / value;
195                                                if (fabs(ratio - floor(ratio + 0.5)) > 1.0e-12)
196                                                    good = false;
197                                            }
198                                        } else {
199                                            double rhs = rowUpper[jRow];
200                                            if (rhs < 0.0) {
201                                                double ratio = rhs / value;
202                                                if (fabs(ratio - floor(ratio + 0.5)) > 1.0e-12)
203                                                    good = false;
204                                            }
205                                        }
206                                    } else if (rowLength[jRow] == 2) {
207                                        if (value > 0.0) {
208                                            if (rowLower[jRow] > -1.0e20)
209                                                good = false;
210                                        } else {
211                                            if (rowUpper[jRow] < 1.0e20)
212                                                good = false;
213                                        }
214                                    } else {
215                                        good = false;
216                                    }
217                                }
218                            }
219                            if (good) {
220                                // both can be integer
221                                changed[numberChanged++] = jColumn1;
222                                solver->setInteger(jColumn1);
223                                if (upper[jColumn1] > 1.0e20)
224                                    solver->setColUpper(jColumn1, 1.0e20);
225                                if (lower[jColumn1] < -1.0e20)
226                                    solver->setColLower(jColumn1, -1.0e20);
227                                changed[numberChanged++] = jColumn2;
228                                solver->setInteger(jColumn2);
229                                if (upper[jColumn2] > 1.0e20)
230                                    solver->setColUpper(jColumn2, 1.0e20);
231                                if (lower[jColumn2] < -1.0e20)
232                                    solver->setColLower(jColumn2, -1.0e20);
233                            }
234                        }
235                        // clear
236                        for (i = 0; i < n; i++) {
237                            changeRhs[which[i]] = 0.0;
238                        }
239                    }
240                }
241            }
242        }
243        for (iColumn = 0; iColumn < numberColumns; iColumn++) {
244            if (upper[iColumn] > lower[iColumn] + 1.0e-8 && !solver->isInteger(iColumn)) {
245                double value;
246                value = upper[iColumn];
247                if (value < 1.0e20 && fabs(value - floor(value + 0.5)) > 1.0e-12)
248                    continue;
249                value = lower[iColumn];
250                if (value > -1.0e20 && fabs(value - floor(value + 0.5)) > 1.0e-12)
251                    continue;
252                bool integer = true;
253                for (CoinBigIndex j = columnStart[iColumn]; j < columnStart[iColumn] + columnLength[iColumn]; j++) {
254                    int iRow = row[j];
255                    if (!ignore[iRow]) {
256                        integer = false;
257                        break;
258                    }
259                }
260                if (integer) {
261                    // integer
262                    changed[numberChanged++] = iColumn;
263                    solver->setInteger(iColumn);
264                    if (upper[iColumn] > 1.0e20)
265                        solver->setColUpper(iColumn, 1.0e20);
266                    if (lower[iColumn] < -1.0e20)
267                        solver->setColLower(iColumn, -1.0e20);
268                }
269            }
270        }
271        finished = numberChanged == saveNumberChanged;
272    }
273    delete [] which;
274    delete [] changeRhs;
275    delete [] ignore;
276    //if (numberInteger&&!noPrinting_)
277    //printf("%d integer variables",numberInteger);
278    if (changeInt) {
279        //if (!noPrinting_) {
280        //if (numberChanged)
281        //  printf(" and %d variables made integer\n",numberChanged);
282        //else
283        //  printf("\n");
284        //}
285        //increment=0.0;
286        if (!numberChanged) {
287            delete [] changed;
288            delete solver;
289            return NULL;
290        } else {
291            for (iColumn = 0; iColumn < numberColumns; iColumn++) {
292                if (solver->isInteger(iColumn))
293                    solverMod->setInteger(iColumn);
294            }
295            delete solver;
296            return changed;
297        }
298    } else {
299        //if (!noPrinting_) {
300        //if (numberChanged)
301        //  printf(" and %d variables could be made integer\n",numberChanged);
302        //else
303        //  printf("\n");
304        //}
305        // just get increment
306        int logLevel = generalMessageHandler->logLevel();
307        CbcModel model(*solver);
308        if (!model.defaultHandler())
309          model.passInMessageHandler(generalMessageHandler);
310        if (noPrinting_)
311            model.setLogLevel(0);
312        model.analyzeObjective();
313        generalMessageHandler->setLogLevel(logLevel);
314        double increment2 = model.getCutoffIncrement();
315        if (increment2 > increment && increment2 > 0.0) {
316            if (!noPrinting_) {
317                sprintf(generalPrint, "Cutoff increment increased from %g to %g", increment, increment2);
318                CoinMessages generalMessages = solverMod->getModelPtr()->messages();
319                generalMessageHandler->message(CLP_GENERAL, generalMessages)
320                << generalPrint
321                << CoinMessageEol;
322            }
323            increment = increment2;
324        }
325        delete solver;
326        numberChanged = 0;
327        delete [] changed;
328        return NULL;
329    }
330}
331#endif  // ifndef CBC_OTHER_SOLVER
332
Note: See TracBrowser for help on using the repository browser.