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

Last change on this file since 1432 was 1432, checked in by bjarni, 9 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.