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

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

restored COUENNE_EPS to 1e-7 -- solves endless branching in nvs19 due to integer infeasibility set to 9e-8 (acceptable for Cbc so should be for Couenne too).

  • Property svn:keywords set to Id
File size: 5.6 KB
Line 
1/* $Id: infeasibility.cpp 569 2011-05-09 03:05:36Z 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  if (reference_ -> isInteger ()) {
87    CouNumber intinfeas = intInfeasibility (info -> solution_ [reference_ -> Index ()]);
88    if (intinfeas > retval) 
89      retval = intinfeas;
90  }
91
92  if (retval < CoinMin (COUENNE_EPS, feas_tolerance_)) 
93    retval = 0.;
94
95  jnlst_ -> Printf (J_DETAILED, J_BRANCHING, 
96                    "infVar x%d ==> returning %e\n", reference_ -> Index (), (reference_ -> isInteger ()) ? 
97                    CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
98                    retval);
99
100  return retval;
101
102  // (reference_ -> isInteger ()) ?
103  //   CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
104  //   retval;
105}
106
107
108/// compute infeasibility of this variable, |w - f(x)|, where w is
109/// the auxiliary variable defined as w = f(x)
110double CouenneVarObject::checkInfeasibility (const OsiBranchingInformation * info) const {
111
112  int index = reference_ -> Index ();
113
114  const std::set <int> &dependence = problem_ -> Dependence () [index];
115
116  if (dependence.size () == 0) { // this is a top level auxiliary,
117                                 // nowhere an independent
118
119    // check first if this variable is fixed. If so, it's useless to branch on it
120    if (fabs (info -> upper_ [index] - 
121              info -> lower_ [index]) / 
122        (1. + fabs (info -> solution_ [index])) < COUENNE_EPS)
123      return 0.;
124
125    // otherwise, return a nonzero infeasibility, if necessary. It
126    // might make sense to branch on it
127    const CouenneObject *obj = problem_ -> Objects () [reference_ -> Index ()];
128
129    double retval = (obj -> Reference ()) ? 
130      (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
131      weiSum * obj -> checkInfeasibility (info) : 0.;
132
133    return retval;
134
135    /*return (reference_ -> isInteger ()) ?
136      CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
137      retval;*/
138
139  } else {
140
141    CouNumber
142      infsum = 0.,
143      infmax = 0.,
144      infmin = COIN_DBL_MAX;
145
146    for (std::set <int>::const_iterator i = dependence.begin ();
147         i != dependence.end (); ++i) {
148
149      // *i is the index of an auxiliary that depends on reference_
150
151      const CouenneObject *obj = problem_ -> Objects () [*i];
152      CouNumber infeas = (obj -> Reference ()) ? obj -> checkInfeasibility (info) : 0.;
153
154      if (infeas > infmax) infmax = infeas;
155      if (infeas < infmin) infmin = infeas;
156      infsum += infeas;
157    }
158
159    double retval = 
160      // neglect it if variable has small bound interval (check
161      // x84=x83/x5 in csched1.nl)
162      (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
163      // to consider maximum, minimum, and sum/avg of the infeasibilities
164      (weiSum * infsum + 
165       weiAvg * (infsum / CoinMax (1., (CouNumber) dependence.size ())) + 
166       weiMin * infmin + 
167       weiMax * infmax);
168
169    return retval;
170
171    /*return (reference_ -> isInteger ()) ?
172      CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
173      retval;*/
174  }
175}
Note: See TracBrowser for help on using the repository browser.