limp-cbc-0.3.2.0: cbits/coin/CbcBranchDefaultDecision.cpp
// $Id: CbcBranchDefaultDecision.cpp 1902 2013-04-10 16:58:16Z stefan $
// Copyright (C) 2002, International Business Machines
// Corporation and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
// Edwin 11/10/2009-- carved out of CbcBranchActual
#if defined(_MSC_VER)
// Turn off compiler warning about long names
# pragma warning(disable:4786)
#endif
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cfloat>
//#define CBC_DEBUG
#include "CoinTypes.hpp"
#include "OsiSolverInterface.hpp"
#include "OsiSolverBranch.hpp"
#include "CbcModel.hpp"
#include "CbcMessage.hpp"
#include "CbcBranchDefaultDecision.hpp"
#include "CbcBranchActual.hpp"
#include "CoinSort.hpp"
#include "CoinError.hpp"
//##############################################################################
// Default Constructor
CbcBranchDefaultDecision::CbcBranchDefaultDecision()
: CbcBranchDecision()
{
bestCriterion_ = 0.0;
bestChangeUp_ = 0.0;
bestNumberUp_ = 0;
bestChangeDown_ = 0.0;
bestObject_ = NULL;
bestNumberDown_ = 0;
}
// Copy constructor
CbcBranchDefaultDecision::CbcBranchDefaultDecision (
const CbcBranchDefaultDecision & rhs)
: CbcBranchDecision(rhs)
{
bestCriterion_ = rhs.bestCriterion_;
bestChangeUp_ = rhs.bestChangeUp_;
bestNumberUp_ = rhs.bestNumberUp_;
bestChangeDown_ = rhs.bestChangeDown_;
bestNumberDown_ = rhs.bestNumberDown_;
bestObject_ = rhs.bestObject_;
model_ = rhs.model_;
}
CbcBranchDefaultDecision::~CbcBranchDefaultDecision()
{
}
// Clone
CbcBranchDecision *
CbcBranchDefaultDecision::clone() const
{
return new CbcBranchDefaultDecision(*this);
}
// Initialize i.e. before start of choosing at a node
void
CbcBranchDefaultDecision::initialize(CbcModel * model)
{
bestCriterion_ = 0.0;
bestChangeUp_ = 0.0;
bestNumberUp_ = 0;
bestChangeDown_ = 0.0;
bestNumberDown_ = 0;
bestObject_ = NULL;
model_ = model;
}
/*
Simple default decision algorithm. Compare based on infeasibility (numInfUp,
numInfDn) until a solution is found by search, then switch to change in
objective (changeUp, changeDn). Note that bestSoFar is remembered in
bestObject_, so the parameter bestSoFar is unused.
*/
int
CbcBranchDefaultDecision::betterBranch(CbcBranchingObject * thisOne,
CbcBranchingObject * /*bestSoFar*/,
double changeUp, int numInfUp,
double changeDn, int numInfDn)
{
bool beforeSolution = cbcModel()->getSolutionCount() ==
cbcModel()->getNumberHeuristicSolutions();;
int betterWay = 0;
if (beforeSolution) {
if (!bestObject_) {
bestNumberUp_ = COIN_INT_MAX;
bestNumberDown_ = COIN_INT_MAX;
}
// before solution - choose smallest number
// could add in depth as well
int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
if (numInfUp < numInfDn) {
if (numInfUp < bestNumber) {
betterWay = 1;
} else if (numInfUp == bestNumber) {
if (changeUp < bestCriterion_)
betterWay = 1;
}
} else if (numInfUp > numInfDn) {
if (numInfDn < bestNumber) {
betterWay = -1;
} else if (numInfDn == bestNumber) {
if (changeDn < bestCriterion_)
betterWay = -1;
}
} else {
// up and down have same number
bool better = false;
if (numInfUp < bestNumber) {
better = true;
} else if (numInfUp == bestNumber) {
if (CoinMin(changeUp, changeDn) < bestCriterion_)
better = true;;
}
if (better) {
// see which way
if (changeUp <= changeDn)
betterWay = 1;
else
betterWay = -1;
}
}
} else {
if (!bestObject_) {
bestCriterion_ = -1.0;
}
// got a solution
if (changeUp <= changeDn) {
if (changeUp > bestCriterion_)
betterWay = 1;
} else {
if (changeDn > bestCriterion_)
betterWay = -1;
}
}
if (betterWay) {
bestCriterion_ = CoinMin(changeUp, changeDn);
bestChangeUp_ = changeUp;
bestNumberUp_ = numInfUp;
bestChangeDown_ = changeDn;
bestNumberDown_ = numInfDn;
bestObject_ = thisOne;
// See if user is overriding way
if (thisOne->object() && thisOne->object()->preferredWay())
betterWay = thisOne->object()->preferredWay();
}
return betterWay;
}
/* Sets or gets best criterion so far */
void
CbcBranchDefaultDecision::setBestCriterion(double value)
{
bestCriterion_ = value;
}
double
CbcBranchDefaultDecision::getBestCriterion() const
{
return bestCriterion_;
}
/* Compare N branching objects. Return index of best
and sets way of branching in chosen object.
This routine is used only after strong branching.
*/
int
CbcBranchDefaultDecision::bestBranch (CbcBranchingObject ** objects, int numberObjects,
int numberUnsatisfied,
double * changeUp, int * numberInfeasibilitiesUp,
double * changeDown, int * numberInfeasibilitiesDown,
double objectiveValue)
{
int bestWay = 0;
int whichObject = -1;
if (numberObjects) {
CbcModel * model = cbcModel();
// at continuous
//double continuousObjective = model->getContinuousObjective();
//int continuousInfeasibilities = model->getContinuousInfeasibilities();
// average cost to get rid of infeasibility
//double averageCostPerInfeasibility =
//(objectiveValue-continuousObjective)/
//(double) (abs(continuousInfeasibilities-numberUnsatisfied)+1);
/* beforeSolution is :
0 - before any solution
n - n heuristic solutions but no branched one
-1 - branched solution found
*/
int numberSolutions = model->getSolutionCount();
double cutoff = model->getCutoff();
int method = 0;
int i;
if (numberSolutions) {
int numberHeuristic = model->getNumberHeuristicSolutions();
if (numberHeuristic < numberSolutions) {
method = 1;
} else {
method = 2;
// look further
for ( i = 0 ; i < numberObjects ; i++) {
int numberNext = numberInfeasibilitiesUp[i];
if (numberNext < numberUnsatisfied) {
int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
double perUnsatisfied = changeUp[i] / static_cast<double> (numberUp);
double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
if (estimatedObjective < cutoff)
method = 3;
}
numberNext = numberInfeasibilitiesDown[i];
if (numberNext < numberUnsatisfied) {
int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
double perUnsatisfied = changeDown[i] / static_cast<double> (numberDown);
double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
if (estimatedObjective < cutoff)
method = 3;
}
}
}
method = 2;
} else {
method = 0;
}
// Uncomment next to force method 4
//method=4;
// FIXME This should be an enum. It will be easier to
// understand in the code than numbers.
/* Methods :
0 - fewest infeasibilities
1 - largest min change in objective
2 - as 1 but use sum of changes if min close
3 - predicted best solution
4 - take cheapest up branch if infeasibilities same
*/
int bestNumber = COIN_INT_MAX;
double bestCriterion = -1.0e50;
double alternativeCriterion = -1.0;
double bestEstimate = 1.0e100;
switch (method) {
case 0:
// could add in depth as well
for ( i = 0 ; i < numberObjects ; i++) {
int thisNumber = CoinMin(numberInfeasibilitiesUp[i], numberInfeasibilitiesDown[i]);
if (thisNumber <= bestNumber) {
int betterWay = 0;
if (numberInfeasibilitiesUp[i] < numberInfeasibilitiesDown[i]) {
if (numberInfeasibilitiesUp[i] < bestNumber) {
betterWay = 1;
} else {
if (changeUp[i] < bestCriterion)
betterWay = 1;
}
} else if (numberInfeasibilitiesUp[i] > numberInfeasibilitiesDown[i]) {
if (numberInfeasibilitiesDown[i] < bestNumber) {
betterWay = -1;
} else {
if (changeDown[i] < bestCriterion)
betterWay = -1;
}
} else {
// up and down have same number
bool better = false;
if (numberInfeasibilitiesUp[i] < bestNumber) {
better = true;
} else if (numberInfeasibilitiesUp[i] == bestNumber) {
if (CoinMin(changeUp[i], changeDown[i]) < bestCriterion)
better = true;;
}
if (better) {
// see which way
if (changeUp[i] <= changeDown[i])
betterWay = 1;
else
betterWay = -1;
}
}
if (betterWay) {
bestCriterion = CoinMin(changeUp[i], changeDown[i]);
bestNumber = thisNumber;
whichObject = i;
bestWay = betterWay;
}
}
}
break;
case 1:
for ( i = 0 ; i < numberObjects ; i++) {
int betterWay = 0;
if (changeUp[i] <= changeDown[i]) {
if (changeUp[i] > bestCriterion)
betterWay = 1;
} else {
if (changeDown[i] > bestCriterion)
betterWay = -1;
}
if (betterWay) {
bestCriterion = CoinMin(changeUp[i], changeDown[i]);
whichObject = i;
bestWay = betterWay;
}
}
break;
case 2:
for ( i = 0 ; i < numberObjects ; i++) {
double change = CoinMin(changeUp[i], changeDown[i]);
double sum = changeUp[i] + changeDown[i];
bool take = false;
if (change > 1.1*bestCriterion)
take = true;
else if (change > 0.9*bestCriterion && sum + change > bestCriterion + alternativeCriterion)
take = true;
if (take) {
if (changeUp[i] <= changeDown[i]) {
if (changeUp[i] > bestCriterion)
bestWay = 1;
} else {
if (changeDown[i] > bestCriterion)
bestWay = -1;
}
bestCriterion = change;
alternativeCriterion = sum;
whichObject = i;
}
}
break;
case 3:
for ( i = 0 ; i < numberObjects ; i++) {
int numberNext = numberInfeasibilitiesUp[i];
if (numberNext < numberUnsatisfied) {
int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
double perUnsatisfied = changeUp[i] / static_cast<double> (numberUp);
double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
if (estimatedObjective < bestEstimate) {
bestEstimate = estimatedObjective;
bestWay = 1;
whichObject = i;
}
}
numberNext = numberInfeasibilitiesDown[i];
if (numberNext < numberUnsatisfied) {
int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
double perUnsatisfied = changeDown[i] / static_cast<double> (numberDown);
double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
if (estimatedObjective < bestEstimate) {
bestEstimate = estimatedObjective;
bestWay = -1;
whichObject = i;
}
}
}
break;
case 4:
// if number infeas same then cheapest up
// first get best number or when going down
// now choose smallest change up amongst equal number infeas
for ( i = 0 ; i < numberObjects ; i++) {
int thisNumber = CoinMin(numberInfeasibilitiesUp[i], numberInfeasibilitiesDown[i]);
if (thisNumber <= bestNumber) {
int betterWay = 0;
if (numberInfeasibilitiesUp[i] < numberInfeasibilitiesDown[i]) {
if (numberInfeasibilitiesUp[i] < bestNumber) {
betterWay = 1;
} else {
if (changeUp[i] < bestCriterion)
betterWay = 1;
}
} else if (numberInfeasibilitiesUp[i] > numberInfeasibilitiesDown[i]) {
if (numberInfeasibilitiesDown[i] < bestNumber) {
betterWay = -1;
} else {
if (changeDown[i] < bestCriterion)
betterWay = -1;
}
} else {
// up and down have same number
bool better = false;
if (numberInfeasibilitiesUp[i] < bestNumber) {
better = true;
} else if (numberInfeasibilitiesUp[i] == bestNumber) {
if (CoinMin(changeUp[i], changeDown[i]) < bestCriterion)
better = true;;
}
if (better) {
// see which way
if (changeUp[i] <= changeDown[i])
betterWay = 1;
else
betterWay = -1;
}
}
if (betterWay) {
bestCriterion = CoinMin(changeUp[i], changeDown[i]);
bestNumber = thisNumber;
whichObject = i;
bestWay = betterWay;
}
}
}
bestCriterion = 1.0e50;
for ( i = 0 ; i < numberObjects ; i++) {
int thisNumber = numberInfeasibilitiesUp[i];
if (thisNumber == bestNumber && changeUp) {
if (changeUp[i] < bestCriterion) {
bestCriterion = changeUp[i];
whichObject = i;
bestWay = 1;
}
}
}
break;
}
// set way in best
if (whichObject >= 0) {
CbcBranchingObject * bestObject = objects[whichObject];
if (bestObject->object() && bestObject->object()->preferredWay())
bestWay = bestObject->object()->preferredWay();
bestObject->way(bestWay);
} else {
COIN_DETAIL_PRINT(printf("debug\n"));
}
}
return whichObject;
}