source: trunk/Cbc/examples/CbcBranchUser.cpp @ 1574

Last change on this file since 1574 was 1574, checked in by lou, 8 years ago

Change to EPL license notice.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.7 KB
Line 
1// $Id: CbcBranchUser.cpp 1574 2011-01-05 01:13:55Z lou $
2// Copyright (C) 2002, 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#if defined(_MSC_VER)
7// Turn off compiler warning about long names
8#  pragma warning(disable:4786)
9#endif
10#include <cassert>
11#include <cmath>
12#include <cfloat>
13
14#include "OsiSolverInterface.hpp"
15#include "CbcModel.hpp"
16#include "CbcMessage.hpp"
17#include "CbcBranchUser.hpp"
18#include "CoinSort.hpp"
19
20// Default Constructor // Default Constructor
21CbcBranchUserDecision::CbcBranchUserDecision()
22  :CbcBranchDecision()
23{
24}
25
26// Copy constructor
27CbcBranchUserDecision::CbcBranchUserDecision (
28                                    const CbcBranchUserDecision & rhs)
29  :CbcBranchDecision(rhs)
30{
31}
32
33CbcBranchUserDecision::~CbcBranchUserDecision()
34{
35}
36
37// Clone
38CbcBranchDecision * 
39CbcBranchUserDecision::clone() const
40{
41  return new CbcBranchUserDecision(*this);
42}
43
44// Initialize i.e. before start of choosing at a node
45void 
46CbcBranchUserDecision::initialize(CbcModel * model)
47{
48}
49
50
51/* Returns nonzero if branching on first object is "better" than on
52   second (if second NULL first wins). User can play with decision object.
53   This is only used after strong branching.  The initial selection
54   is done by infeasibility() for each CbcObject
55   return code +1 for up branch preferred, -1 for down
56   
57*/
58int
59CbcBranchUserDecision::betterBranch(CbcBranchingObject * thisOne,
60                            CbcBranchingObject * bestSoFar,
61                            double changeUp, int numberInfeasibilitiesUp,
62                            double changeDown, int numberInfeasibilitiesDown)
63{
64  printf("Now obsolete CbcBranchUserDecision::betterBranch\n");
65  abort();
66  return 0;
67}
68/* Compare N branching objects. Return index of best
69   and sets way of branching in chosen object.
70   
71   This routine is used only after strong branching.
72   This is reccommended version as it can be more sophisticated
73*/
74
75int
76CbcBranchUserDecision::bestBranch (CbcBranchingObject ** objects, int numberObjects,
77                                   int numberUnsatisfied,
78                                   double * changeUp, int * numberInfeasibilitiesUp,
79                                   double * changeDown, int * numberInfeasibilitiesDown,
80                                   double objectiveValue) 
81{
82
83  int bestWay=0;
84  int whichObject = -1;
85  if (numberObjects) {
86    CbcModel * model = objects[0]->model();
87    // at continuous
88    //double continuousObjective = model->getContinuousObjective();
89    //int continuousInfeasibilities = model->getContinuousInfeasibilities();
90   
91    // average cost to get rid of infeasibility
92    //double averageCostPerInfeasibility =
93    //(objectiveValue-continuousObjective)/
94    //(double) (abs(continuousInfeasibilities-numberUnsatisfied)+1);
95    /* beforeSolution is :
96       0 - before any solution
97       n - n heuristic solutions but no branched one
98       -1 - branched solution found
99    */
100    int numberSolutions = model->getSolutionCount();
101    double cutoff = model->getCutoff();
102    int method=0;
103    int i;
104    if (numberSolutions) {
105      int numberHeuristic = model->getNumberHeuristicSolutions();
106      if (numberHeuristic<numberSolutions) {
107        method = 1;
108      } else {
109        method = 2;
110        // look further
111        for ( i = 0 ; i < numberObjects ; i++) {
112          int numberNext = numberInfeasibilitiesUp[i];
113         
114          if (numberNext<numberUnsatisfied) {
115            int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
116            double perUnsatisfied = changeUp[i]/(double) numberUp;
117            double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
118            if (estimatedObjective<cutoff) 
119              method=3;
120          }
121          numberNext = numberInfeasibilitiesDown[i];
122          if (numberNext<numberUnsatisfied) {
123            int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
124            double perUnsatisfied = changeDown[i]/(double) numberDown;
125            double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
126            if (estimatedObjective<cutoff) 
127              method=3;
128          }
129        }
130      }
131      method=2;
132    } else {
133      method = 0;
134    }
135    // Uncomment next to force method 4
136    //method=4;
137    /* Methods :
138       0 - fewest infeasibilities
139       1 - largest min change in objective
140       2 - as 1 but use sum of changes if min close
141       3 - predicted best solution
142       4 - take cheapest up branch if infeasibilities same
143    */
144    int bestNumber=COIN_INT_MAX;
145    double bestCriterion=-1.0e50;
146    double alternativeCriterion = -1.0;
147    double bestEstimate = 1.0e100;
148    switch (method) {
149    case 0:
150      // could add in depth as well
151      for ( i = 0 ; i < numberObjects ; i++) {
152        int thisNumber = CoinMin(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]);
153        if (thisNumber<=bestNumber) {
154          int betterWay=0;
155          if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) {
156            if (numberInfeasibilitiesUp[i]<bestNumber) {
157              betterWay = 1;
158            } else {
159              if (changeUp[i]<bestCriterion)
160                betterWay=1;
161            }
162          } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) {
163            if (numberInfeasibilitiesDown[i]<bestNumber) {
164              betterWay = -1;
165            } else {
166              if (changeDown[i]<bestCriterion)
167                betterWay=-1;
168            }
169          } else {
170            // up and down have same number
171            bool better=false;
172            if (numberInfeasibilitiesUp[i]<bestNumber) {
173              better=true;
174            } else if (numberInfeasibilitiesUp[i]==bestNumber) {
175              if (CoinMin(changeUp[i],changeDown[i])<bestCriterion)
176                better=true;;
177            }
178            if (better) {
179              // see which way
180              if (changeUp[i]<=changeDown[i])
181                betterWay=1;
182              else
183                betterWay=-1;
184            }
185          }
186          if (betterWay) {
187            bestCriterion = CoinMin(changeUp[i],changeDown[i]);
188            bestNumber = thisNumber;
189            whichObject = i;
190            bestWay = betterWay;
191          }
192        }
193      }
194      break;
195    case 1:
196      for ( i = 0 ; i < numberObjects ; i++) {
197        int betterWay=0;
198        if (changeUp[i]<=changeDown[i]) {
199          if (changeUp[i]>bestCriterion)
200            betterWay=1;
201        } else {
202          if (changeDown[i]>bestCriterion)
203            betterWay=-1;
204        }
205        if (betterWay) {
206          bestCriterion = CoinMin(changeUp[i],changeDown[i]);
207          whichObject = i;
208          bestWay = betterWay;
209        }
210      }
211      break;
212    case 2:
213      for ( i = 0 ; i < numberObjects ; i++) {
214        double change = CoinMin(changeUp[i],changeDown[i]);
215        double sum = changeUp[i] + changeDown[i];
216        bool take=false;
217        if (change>1.1*bestCriterion) 
218          take=true;
219        else if (change>0.9*bestCriterion&&sum+change>bestCriterion+alternativeCriterion) 
220          take=true;
221        if (take) {
222          if (changeUp[i]<=changeDown[i]) {
223            if (changeUp[i]>bestCriterion)
224              bestWay=1;
225          } else {
226            if (changeDown[i]>bestCriterion)
227              bestWay=-1;
228          }
229          bestCriterion = change;
230          alternativeCriterion = sum;
231          whichObject = i;
232        }
233      }
234      break;
235    case 3:
236      for ( i = 0 ; i < numberObjects ; i++) {
237        int numberNext = numberInfeasibilitiesUp[i];
238       
239        if (numberNext<numberUnsatisfied) {
240          int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
241          double perUnsatisfied = changeUp[i]/(double) numberUp;
242          double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
243          if (estimatedObjective<bestEstimate) {
244            bestEstimate = estimatedObjective;
245            bestWay=1;
246            whichObject=i;
247          }
248        }
249        numberNext = numberInfeasibilitiesDown[i];
250        if (numberNext<numberUnsatisfied) {
251          int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
252          double perUnsatisfied = changeDown[i]/(double) numberDown;
253          double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
254          if (estimatedObjective<bestEstimate) {
255            bestEstimate = estimatedObjective;
256            bestWay=-1;
257            whichObject=i;
258          }
259        }
260      }
261      break;
262    case 4:
263      // if number infeas same then cheapest up
264      // first get best number or when going down
265      // now choose smallest change up amongst equal number infeas
266      for ( i = 0 ; i < numberObjects ; i++) {
267        int thisNumber = CoinMin(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]);
268        if (thisNumber<=bestNumber) {
269          int betterWay=0;
270          if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) {
271            if (numberInfeasibilitiesUp[i]<bestNumber) {
272              betterWay = 1;
273            } else {
274              if (changeUp[i]<bestCriterion)
275                betterWay=1;
276            }
277          } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) {
278            if (numberInfeasibilitiesDown[i]<bestNumber) {
279              betterWay = -1;
280            } else {
281              if (changeDown[i]<bestCriterion)
282                betterWay=-1;
283            }
284          } else {
285            // up and down have same number
286            bool better=false;
287            if (numberInfeasibilitiesUp[i]<bestNumber) {
288              better=true;
289            } else if (numberInfeasibilitiesUp[i]==bestNumber) {
290              if (CoinMin(changeUp[i],changeDown[i])<bestCriterion)
291                better=true;;
292            }
293            if (better) {
294              // see which way
295              if (changeUp[i]<=changeDown[i])
296                betterWay=1;
297              else
298                betterWay=-1;
299            }
300          }
301          if (betterWay) {
302            bestCriterion = CoinMin(changeUp[i],changeDown[i]);
303            bestNumber = thisNumber;
304            whichObject = i;
305            bestWay = betterWay;
306          }
307        }
308      }
309      bestCriterion=1.0e50;
310      for ( i = 0 ; i < numberObjects ; i++) {
311        int thisNumber = numberInfeasibilitiesUp[i];
312        if (thisNumber==bestNumber&&changeUp) {
313          if (changeUp[i]<bestCriterion) {
314            bestCriterion = changeUp[i];
315            whichObject = i;
316            bestWay = 1;
317          }
318        }
319      }
320      break;
321    }
322    // set way in best
323    if (whichObject>=0)
324      objects[whichObject]->way(bestWay);
325  }
326  return whichObject;
327}
328/** Default Constructor
329
330  Equivalent to an unspecified binary variable.
331*/
332CbcSimpleIntegerFixed::CbcSimpleIntegerFixed ()
333  : CbcSimpleInteger()
334{
335}
336
337/** Useful constructor
338
339  Loads actual upper & lower bounds for the specified variable.
340*/
341CbcSimpleIntegerFixed::CbcSimpleIntegerFixed (CbcModel * model,
342                                    int iColumn, double breakEven)
343  : CbcSimpleInteger(model,iColumn,breakEven)
344{
345}
346// Constructor from simple
347CbcSimpleIntegerFixed::CbcSimpleIntegerFixed (const CbcSimpleInteger & rhs)
348  : CbcSimpleInteger(rhs)
349{
350}
351
352// Copy constructor
353CbcSimpleIntegerFixed::CbcSimpleIntegerFixed ( const CbcSimpleIntegerFixed & rhs)
354  :CbcSimpleInteger(rhs)
355
356{
357}
358
359// Clone
360CbcObject *
361CbcSimpleIntegerFixed::clone() const
362{
363  return new CbcSimpleIntegerFixed(*this);
364}
365
366// Assignment operator
367CbcSimpleIntegerFixed & 
368CbcSimpleIntegerFixed::operator=( const CbcSimpleIntegerFixed& rhs)
369{
370  if (this!=&rhs) {
371    CbcSimpleInteger::operator=(rhs);
372  }
373  return *this;
374}
375
376// Destructor
377CbcSimpleIntegerFixed::~CbcSimpleIntegerFixed ()
378{
379}
380
381// Infeasibility - large is 0.5
382double 
383CbcSimpleIntegerFixed::infeasibility(int & preferredWay) const
384{
385  OsiSolverInterface * solver = model_->solver();
386  const double * solution = model_->testSolution();
387  const double * lower = solver->getColLower();
388  const double * upper = solver->getColUpper();
389  double value = solution[columnNumber_];
390  value = CoinMax(value, lower[columnNumber_]);
391  value = CoinMin(value, upper[columnNumber_]);
392  /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
393    solution[columnNumber_],upper[columnNumber_]);*/
394  double nearest = floor(value+(1.0-breakEven_));
395  assert (breakEven_>0.0&&breakEven_<1.0);
396  double integerTolerance = 
397    model_->getDblParam(CbcModel::CbcIntegerTolerance);
398  if (nearest>value) 
399    preferredWay=1;
400  else
401    preferredWay=-1;
402  if (preferredWay_)
403    preferredWay=preferredWay_;
404  double weight = fabs(value-nearest);
405  // normalize so weight is 0.5 at break even
406  if (nearest<value)
407    weight = (0.5/breakEven_)*weight;
408  else
409    weight = (0.5/(1.0-breakEven_))*weight;
410  if (fabs(value-nearest)<=integerTolerance) {
411    if (upper[columnNumber_]==lower[columnNumber_])
412      return 0.0;
413    else
414      return 1.0e-5;
415  } else {
416    return weight;
417  }
418}
419// Creates a branching object
420CbcBranchingObject * 
421CbcSimpleIntegerFixed::createBranch(OsiSolverInterface * solver,
422                                            const OsiBranchingInformation * info, int way) 
423{
424  const double * solution = model_->testSolution();
425  const double * lower = solver->getColLower();
426  const double * upper = solver->getColUpper();
427  double value = solution[columnNumber_];
428  value = CoinMax(value, lower[columnNumber_]);
429  value = CoinMin(value, upper[columnNumber_]);
430  assert (upper[columnNumber_]>lower[columnNumber_]);
431  if (!model_->hotstartSolution()) {
432    double nearest = floor(value+0.5);
433    double integerTolerance = 
434    model_->getDblParam(CbcModel::CbcIntegerTolerance);
435    if (fabs(value-nearest)<integerTolerance) {
436      // adjust value
437      if (nearest!=upper[columnNumber_])
438        value = nearest+2.0*integerTolerance;
439      else
440        value = nearest-2.0*integerTolerance;
441    }
442  } else {
443    const double * hotstartSolution = model_->hotstartSolution();
444    double targetValue = hotstartSolution[columnNumber_];
445    if (way>0)
446      value = targetValue-0.1;
447    else
448      value = targetValue+0.1;
449  }
450  CbcBranchingObject * branch = new CbcIntegerBranchingObject(model_,columnNumber_,way,
451                                             value);
452  branch->setOriginalObject(this);
453  return branch;
454}
Note: See TracBrowser for help on using the repository browser.