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

Last change on this file since 2496 was 2469, checked in by unxusr, 7 months ago

formatting

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