source: stable/0.3/Couenne/src/branch/infeasibility.cpp @ 581

Last change on this file since 581 was 581, checked in by pbelotti, 9 years ago

intInfeasibility() checks lower/upper bounds to avoid non-null infeasibility upon out-of-bounds values, which triggers infeasibility in Couenne but not in Cbc, and this in turn makes the BB loop

  • Property svn:keywords set to Id
File size: 5.8 KB
Line 
1/* $Id: infeasibility.cpp 581 2011-05-22 11:37:33Z pbelotti $
2 *
3 * Name:    infeasibility.cpp
4 * Authors: Pietro Belotti, Carnegie Mellon University
5 * Purpose: Compute infeasibility of a variable, looking at all expressions it appears in
6 *
7 * (C) Carnegie-Mellon University, 2008-09.
8 * This file is licensed under the Common Public License (CPL)
9 */
10
11#include "CoinHelperFunctions.hpp"
12
13#include "CouenneProblem.hpp"
14#include "CouenneVarObject.hpp"
15
16/// weights for computing infeasibility
17const CouNumber weiMin = 0.8; // for minimum of infeasibilities of nonlinear objects
18const CouNumber weiMax = 1.3; //     maximum
19const CouNumber weiSum = 0.1; //     sum
20const CouNumber weiAvg = 0.0; //     average
21
22
23/// compute infeasibility of this variable, |w - f(x)| (where w is
24/// the auxiliary variable defined as w = f(x))
25/// TODO: suggest way
26double CouenneVarObject::infeasibility (const OsiBranchingInformation *info, int &way) const {
27
28  assert (reference_);
29  int index = reference_ -> Index ();
30
31  /*printf ("===INFEAS %d = %g [%g,%g]\n",
32          index,
33          info -> solution_ [index],
34          info -> lower_ [index],
35          info -> upper_ [index]);*/
36
37  /*if (info -> lower_ [index] >=
38      info -> upper_ [index] - CoinMin (COUENNE_EPS, feas_tolerance_))
39    return (reference_ -> isInteger ()) ?
40    intInfeasibility (info -> solution_ [index]) : 0.;*/
41
42  problem_ -> domain () -> push
43    (problem_ -> nVars (),
44     info -> solution_, 
45     info -> lower_, 
46     info -> upper_);
47
48  const std::set <int> &dependence = problem_ -> Dependence () [index];
49
50  //////////////////////////////////////////////
51  CouNumber retval = checkInfeasibility (info);
52  //////////////////////////////////////////////
53
54  if (//(retval > CoinMin (COUENNE_EPS, feas_tolerance_)) &&
55      (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING))) {
56    printf ("infeasVar x%d %-10g [", reference_ -> Index (), retval);
57    reference_             -> print (); 
58    if ((dependence.size () == 0) && (reference_ -> Image ())) { // if no list, print image
59      printf (" := ");
60      reference_ -> Image () -> print ();
61    }
62    printf ("]\n");
63  }
64
65  // add term to stop branching on very tiny intervals
66
67  // Compute the up and down estimates here
68  // TODO: We probably only have to do that if pseudo costs option has
69  // been chosen
70
71  const CouenneObject *obj_ignored = NULL; // only care about it in CouenneVarObject.cpp
72
73  CouNumber brkPt = computeBranchingPoint (info, way, obj_ignored);
74
75  if (pseudoMultType_ != PROJECTDIST)
76    setEstimates (info, &retval, &brkPt);
77
78  jnlst_ -> Printf (J_DETAILED, J_BRANCHING,
79                    "index = %d up = %e down = %e bounds [%e,%e] brpt = %e\n", 
80                    index, upEstimate_, downEstimate_, 
81                    info -> lower_ [index],
82                    info -> upper_ [index], brkPt);
83
84  problem_ -> domain () -> pop (); // domain not used below
85
86  int refInd = reference_ -> Index (); 
87
88  if (reference_ -> isInteger ()) {
89    CouNumber intinfeas = intInfeasibility (info -> solution_ [refInd],
90                                            info -> lower_    [refInd],
91                                            info -> upper_    [refInd]);
92    if (intinfeas > retval) 
93      retval = intinfeas;
94  }
95
96  if (retval < CoinMin (COUENNE_EPS, feas_tolerance_)) 
97    retval = 0.;
98
99  jnlst_ -> Printf (J_DETAILED, J_BRANCHING, 
100                    "infVar x%d ==> returning %e\n", reference_ -> Index (), (reference_ -> isInteger ()) ? 
101                    CoinMax (retval, intInfeasibility (info -> solution_ [refInd],
102                                                       info -> lower_    [refInd],
103                                                       info -> upper_    [refInd])) :
104                    retval);
105
106  return retval;
107
108  // (reference_ -> isInteger ()) ?
109  //   CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
110  //   retval;
111}
112
113
114/// compute infeasibility of this variable, |w - f(x)|, where w is
115/// the auxiliary variable defined as w = f(x)
116double CouenneVarObject::checkInfeasibility (const OsiBranchingInformation * info) const {
117
118  int index = reference_ -> Index ();
119
120  const std::set <int> &dependence = problem_ -> Dependence () [index];
121
122  if (dependence.size () == 0) { // this is a top level auxiliary,
123                                 // nowhere an independent
124
125    // check first if this variable is fixed. If so, it's useless to branch on it
126    if (fabs (info -> upper_ [index] - 
127              info -> lower_ [index]) / 
128        (1. + fabs (info -> solution_ [index])) < COUENNE_EPS)
129      return 0.;
130
131    // otherwise, return a nonzero infeasibility, if necessary. It
132    // might make sense to branch on it
133    const CouenneObject *obj = problem_ -> Objects () [reference_ -> Index ()];
134
135    double retval = (obj -> Reference ()) ? 
136      (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
137      weiSum * obj -> checkInfeasibility (info) : 0.;
138
139    return retval;
140
141    /*return (reference_ -> isInteger ()) ?
142      CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
143      retval;*/
144
145  } else {
146
147    CouNumber
148      infsum = 0.,
149      infmax = 0.,
150      infmin = COIN_DBL_MAX;
151
152    for (std::set <int>::const_iterator i = dependence.begin ();
153         i != dependence.end (); ++i) {
154
155      // *i is the index of an auxiliary that depends on reference_
156
157      const CouenneObject *obj = problem_ -> Objects () [*i];
158      CouNumber infeas = (obj -> Reference ()) ? obj -> checkInfeasibility (info) : 0.;
159
160      if (infeas > infmax) infmax = infeas;
161      if (infeas < infmin) infmin = infeas;
162      infsum += infeas;
163    }
164
165    double retval = 
166      // neglect it if variable has small bound interval (check
167      // x84=x83/x5 in csched1.nl)
168      (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
169      // to consider maximum, minimum, and sum/avg of the infeasibilities
170      (weiSum * infsum + 
171       weiAvg * (infsum / CoinMax (1., (CouNumber) dependence.size ())) + 
172       weiMin * infmin + 
173       weiMax * infmax);
174
175    return retval;
176
177    /*return (reference_ -> isInteger ()) ?
178      CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
179      retval;*/
180  }
181}
Note: See TracBrowser for help on using the repository browser.