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

Last change on this file since 1566 was 1432, checked in by bjarni, 10 years ago

Added extra return at end of each source file where needed, to remove possible linefeed conflicts (NightlyBuild? errors)

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