source: trunk/Cbc/src/CbcHeuristicVND.cpp @ 2094

Last change on this file since 2094 was 2094, checked in by forrest, 4 years ago

for memory leaks and heuristics and some experimental stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.1 KB
Line 
1// $Id: CbcHeuristicVND.cpp 2094 2014-11-18 11:15:36Z forrest $
2// Copyright (C) 2006, 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// edwin 12/5/09 carved out of CbcHeuristicRINS
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#  pragma warning(disable:4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16
17#include "OsiSolverInterface.hpp"
18#include "CbcModel.hpp"
19#include "CbcMessage.hpp"
20#include "CbcHeuristicVND.hpp"
21#include "CbcBranchActual.hpp"
22#include "CbcStrategy.hpp"
23#include "CglPreProcess.hpp"
24
25
26// Default Constructor
27CbcHeuristicVND::CbcHeuristicVND()
28        : CbcHeuristic()
29{
30    numberSolutions_ = 0;
31    numberSuccesses_ = 0;
32    numberTries_ = 0;
33    lastNode_ = -999999;
34    howOften_ = 100;
35    decayFactor_ = 0.5;
36    baseSolution_ = NULL;
37    whereFrom_ = 1 + 8 + 255 * 256;
38    stepSize_ = 0;
39    k_ = 0;
40    kmax_ = 0;
41    nDifferent_ = 0;
42}
43
44// Constructor with model - assumed before cuts
45
46CbcHeuristicVND::CbcHeuristicVND(CbcModel & model)
47        : CbcHeuristic(model)
48{
49    numberSolutions_ = 0;
50    numberSuccesses_ = 0;
51    numberTries_ = 0;
52    lastNode_ = -999999;
53    howOften_ = 100;
54    decayFactor_ = 0.5;
55    assert(model.solver());
56    int numberColumns = model.solver()->getNumCols();
57    baseSolution_ = new double [numberColumns];
58    memset(baseSolution_, 0, numberColumns*sizeof(double));
59    whereFrom_ = 1 + 8 + 255 * 256;
60    stepSize_ = 0;
61    k_ = 0;
62    kmax_ = 0;
63    nDifferent_ = 0;
64}
65
66// Destructor
67CbcHeuristicVND::~CbcHeuristicVND ()
68{
69    delete [] baseSolution_;
70}
71
72// Clone
73CbcHeuristic *
74CbcHeuristicVND::clone() const
75{
76    return new CbcHeuristicVND(*this);
77}
78
79// Assignment operator
80CbcHeuristicVND &
81CbcHeuristicVND::operator=( const CbcHeuristicVND & rhs)
82{
83    if (this != &rhs) {
84        CbcHeuristic::operator=(rhs);
85        numberSolutions_ = rhs.numberSolutions_;
86        howOften_ = rhs.howOften_;
87        numberSuccesses_ = rhs.numberSuccesses_;
88        numberTries_ = rhs.numberTries_;
89        lastNode_ = rhs.lastNode_;
90        delete [] baseSolution_;
91        if (model_ && rhs.baseSolution_) {
92            int numberColumns = model_->solver()->getNumCols();
93            baseSolution_ = new double [numberColumns];
94            memcpy(baseSolution_, rhs.baseSolution_, numberColumns*sizeof(double));
95        } else {
96            baseSolution_ = NULL;
97        }
98        stepSize_ = rhs.stepSize_;
99        k_ = rhs.k_;
100        kmax_ = rhs.kmax_;
101        nDifferent_ = rhs.nDifferent_;
102    }
103    return *this;
104}
105
106// Create C++ lines to get to current state
107void
108CbcHeuristicVND::generateCpp( FILE * fp)
109{
110    CbcHeuristicVND other;
111    fprintf(fp, "0#include \"CbcHeuristicVND.hpp\"\n");
112    fprintf(fp, "3  CbcHeuristicVND heuristicVND(*cbcModel);\n");
113    CbcHeuristic::generateCpp(fp, "heuristicVND");
114    if (howOften_ != other.howOften_)
115        fprintf(fp, "3  heuristicVND.setHowOften(%d);\n", howOften_);
116    else
117        fprintf(fp, "4  heuristicVND.setHowOften(%d);\n", howOften_);
118    fprintf(fp, "3  cbcModel->addHeuristic(&heuristicVND);\n");
119}
120
121// Copy constructor
122CbcHeuristicVND::CbcHeuristicVND(const CbcHeuristicVND & rhs)
123        :
124        CbcHeuristic(rhs),
125        numberSolutions_(rhs.numberSolutions_),
126        howOften_(rhs.howOften_),
127        numberSuccesses_(rhs.numberSuccesses_),
128        numberTries_(rhs.numberTries_),
129        lastNode_(rhs.lastNode_)
130{
131    if (model_ && rhs.baseSolution_) {
132        int numberColumns = model_->solver()->getNumCols();
133        baseSolution_ = new double [numberColumns];
134        memcpy(baseSolution_, rhs.baseSolution_, numberColumns*sizeof(double));
135    } else {
136        baseSolution_ = NULL;
137    }
138    stepSize_ = rhs.stepSize_;
139    k_ = rhs.k_;
140    kmax_ = rhs.kmax_;
141    nDifferent_ = rhs.nDifferent_;
142}
143// Resets stuff if model changes
144void
145CbcHeuristicVND::resetModel(CbcModel * /*model*/)
146{
147    //CbcHeuristic::resetModel(model);
148    delete [] baseSolution_;
149    if (model_ && baseSolution_) {
150        int numberColumns = model_->solver()->getNumCols();
151        baseSolution_ = new double [numberColumns];
152        memset(baseSolution_, 0, numberColumns*sizeof(double));
153    } else {
154        baseSolution_ = NULL;
155    }
156}
157/*
158  First tries setting a variable to better value.  If feasible then
159  tries setting others.  If not feasible then tries swaps
160  Returns 1 if solution, 0 if not */
161int
162CbcHeuristicVND::solution(double & solutionValue,
163                          double * betterSolution)
164{
165    numCouldRun_++;
166    int returnCode = 0;
167    const double * bestSolution = model_->bestSolution();
168    if (!bestSolution)
169        return 0; // No solution found yet
170#ifdef HEURISTIC_INFORM
171    printf("Entering heuristic %s - nRuns %d numCould %d when %d\n",
172           heuristicName(),numRuns_,numCouldRun_,when_);
173#endif
174    if (numberSolutions_ < model_->getSolutionCount()) {
175        // new solution - add info
176        numberSolutions_ = model_->getSolutionCount();
177
178        int numberIntegers = model_->numberIntegers();
179        const int * integerVariable = model_->integerVariable();
180
181        int i;
182        for (i = 0; i < numberIntegers; i++) {
183            int iColumn = integerVariable[i];
184            const OsiObject * object = model_->object(i);
185            // get original bounds
186            double originalLower;
187            double originalUpper;
188            getIntegerInformation( object, originalLower, originalUpper);
189            double value = bestSolution[iColumn];
190            if (value < originalLower) {
191                value = originalLower;
192            } else if (value > originalUpper) {
193                value = originalUpper;
194            }
195        }
196    }
197    int numberNodes = model_->getNodeCount();
198    if (howOften_ == 100) {
199        if (numberNodes < lastNode_ + 12)
200            return 0;
201        // Do at 50 and 100
202        if ((numberNodes > 40 && numberNodes <= 50) || (numberNodes > 90 && numberNodes < 100))
203            numberNodes = howOften_;
204    }
205    if ((numberNodes % howOften_) == 0 && (model_->getCurrentPassNumber() <= 1 ||
206                                           model_->getCurrentPassNumber() == 999999)) {
207        lastNode_ = model_->getNodeCount();
208        OsiSolverInterface * solver = model_->solver();
209
210        int numberIntegers = model_->numberIntegers();
211        const int * integerVariable = model_->integerVariable();
212
213        const double * currentSolution = solver->getColSolution();
214        OsiSolverInterface * newSolver = cloneBut(3); // was model_->continuousSolver()->clone();
215        //const double * colLower = newSolver->getColLower();
216        //const double * colUpper = newSolver->getColUpper();
217
218        double primalTolerance;
219        solver->getDblParam(OsiPrimalTolerance, primalTolerance);
220
221        // Sort on distance
222        double * distance = new double [numberIntegers];
223        int * which = new int [numberIntegers];
224
225        int i;
226        int nFix = 0;
227        double tolerance = 10.0 * primalTolerance;
228        for (i = 0; i < numberIntegers; i++) {
229            int iColumn = integerVariable[i];
230            const OsiObject * object = model_->object(i);
231            // get original bounds
232            double originalLower;
233            double originalUpper;
234            getIntegerInformation( object, originalLower, originalUpper);
235            double valueInt = bestSolution[iColumn];
236            if (valueInt < originalLower) {
237                valueInt = originalLower;
238            } else if (valueInt > originalUpper) {
239                valueInt = originalUpper;
240            }
241            baseSolution_[iColumn] = currentSolution[iColumn];
242            distance[i] = fabs(currentSolution[iColumn] - valueInt);
243            which[i] = i;
244            if (fabs(currentSolution[iColumn] - valueInt) < tolerance)
245                nFix++;
246        }
247        CoinSort_2(distance, distance + numberIntegers, which);
248        nDifferent_ = numberIntegers - nFix;
249        stepSize_ = nDifferent_ / 10;
250        k_ = stepSize_;
251        //nFix = numberIntegers-stepSize_;
252        for (i = 0; i < nFix; i++) {
253            int j = which[i];
254            int iColumn = integerVariable[j];
255            const OsiObject * object = model_->object(i);
256            // get original bounds
257            double originalLower;
258            double originalUpper;
259            getIntegerInformation( object, originalLower, originalUpper);
260            double valueInt = bestSolution[iColumn];
261            if (valueInt < originalLower) {
262                valueInt = originalLower;
263            } else if (valueInt > originalUpper) {
264                valueInt = originalUpper;
265            }
266            double nearest = floor(valueInt + 0.5);
267            newSolver->setColLower(iColumn, nearest);
268            newSolver->setColUpper(iColumn, nearest);
269        }
270        delete [] distance;
271        delete [] which;
272        if (nFix > numberIntegers / 5) {
273            //printf("%d integers have samish value\n",nFix);
274            returnCode = smallBranchAndBound(newSolver, numberNodes_, betterSolution, solutionValue,
275                                             model_->getCutoff(), "CbcHeuristicVND");
276            if (returnCode < 0)
277                returnCode = 0; // returned on size
278            else
279                numRuns_++;
280            if ((returnCode&1) != 0)
281                numberSuccesses_++;
282            //printf("return code %d",returnCode);
283            if ((returnCode&2) != 0) {
284                // could add cut
285                returnCode &= ~2;
286                //printf("could add cut with %d elements (if all 0-1)\n",nFix);
287            } else {
288                //printf("\n");
289            }
290            numberTries_++;
291            if ((numberTries_ % 10) == 0 && numberSuccesses_*3 < numberTries_)
292                howOften_ += static_cast<int> (howOften_ * decayFactor_);
293        }
294
295        delete newSolver;
296    }
297    return returnCode;
298}
299// update model
300void CbcHeuristicVND::setModel(CbcModel * model)
301{
302    model_ = model;
303    // Get a copy of original matrix
304    assert(model_->solver());
305    delete [] baseSolution_;
306    int numberColumns = model->solver()->getNumCols();
307    baseSolution_ = new double [numberColumns];
308    memset(baseSolution_, 0, numberColumns*sizeof(double));
309}
310
Note: See TracBrowser for help on using the repository browser.