1 /* $Id$
2 *
3 * Name: impliedBounds.cpp
4 * Author: Pietro Belotti
5 * Purpose: backward implied bound search
6 *
7 * (C) Carnegie-Mellon University, 2006-10.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CoinHelperFunctions.hpp"
12
13 #include "CouenneProblem.hpp"
14 #include "CouenneExprVar.hpp"
15
16 using namespace Couenne;
17
18 /// Bound tightening for auxiliary variables
19
impliedBounds(t_chg_bounds * chg_bds) const20 int CouenneProblem::impliedBounds (t_chg_bounds *chg_bds) const {
21
22 int nchg = 0; //< number of bounds changed for propagation
23
24 CouNumber *knownOptimum = optimum_;
25
26 if (optimum_) {
27
28 for (int i=nVars(); i--; knownOptimum++)
29
30 if (*knownOptimum < Lb (i) ||
31 *knownOptimum > Ub (i)) {
32
33 knownOptimum = NULL;
34 break;
35 }
36
37 if (knownOptimum)
38 knownOptimum -= nVars ();
39 }
40
41 if (Jnlst()->ProduceOutput(Ipopt::J_DETAILED, J_BOUNDTIGHTENING)) {
42 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING," backward =====================\n ");
43 int j=0;
44 for (int i=0; i < nVars (); i++)
45 if (variables_ [i] -> Multiplicity () > 0) {
46 Jnlst()->Printf(Ipopt::J_MOREVECTOR, J_BOUNDTIGHTENING,
47 "x_%03d [%+10g %+10g] ", i,
48 domain_.lb (i),
49 domain_.ub (i));
50 if (!(++j % 6)) Jnlst()->Printf(Ipopt::J_MOREVECTOR, J_BOUNDTIGHTENING,"\n ");
51 }
52 if (j % 6) Jnlst()->Printf(Ipopt::J_MOREVECTOR, J_BOUNDTIGHTENING,"\n");
53 }
54
55 for (int ii = nVars (); ii--;) {
56
57 int i = numbering_ [ii];
58
59 if (Lb (i) > Ub (i) &&
60 (Lb (i) < Ub (i) + COUENNE_BOUND_PREC * (1 + CoinMin (fabs (Lb (i)), fabs (Ub (i)))))) {
61
62 // This is to prevent very tiny infeasibilities to propagate
63 // down and make the problem infeasible. Example pointed out in
64 // http://list.coin-or.org/pipermail/couenne/2010-October/000145.html
65
66 CouNumber tmp = Lb (i);
67 Lb (i) = Ub (i);
68 Ub (i) = tmp;
69 }
70
71 if ((variables_ [i] -> Type () == AUX) &&
72 (variables_ [i] -> Multiplicity () > 0)) {
73
74 if (Lb (i) > Ub (i) + COUENNE_BOUND_PREC * (1 + CoinMin (fabs (Lb (i)), fabs (Ub (i))))) {
75 Jnlst () -> Printf (Ipopt::J_DETAILED, J_BOUNDTIGHTENING,
76 " implied bounds: w_%d has infeasible bounds [%g,%g]\n",
77 i, Lb (i), Ub (i));
78 return -1;
79 }
80
81 // TODO: also test if this expression, or any of its indep
82 // variables, have changed. If not, skip
83
84 CouNumber
85 l0 = Lb (i),
86 u0 = Ub (i);
87
88 if (variables_ [i] -> Image () -> impliedBound
89 (variables_ [i] -> Index (), Lb (), Ub (), chg_bds, variables_ [i] -> sign ())) {
90
91 // conservative check for integer variables.
92 /*if (Var (i) -> isInteger ()) {
93 Lb (i) = ceil (Lb (i) - COUENNE_EPS);
94 Ub (i) = floor (Ub (i) + COUENNE_EPS);
95 }*/
96
97 if (Jnlst()->ProduceOutput(Ipopt::J_VECTOR, J_BOUNDTIGHTENING)) {
98 // todo: send all output through journalist
99 Jnlst()->Printf(Ipopt::J_VECTOR, J_BOUNDTIGHTENING,
100 " impli %2d [%15.8g, %15.8g] -> [%15.8g, %15.8g]: ",
101 i, l0, u0, Lb (i), Ub (i));
102
103 variables_ [i] -> print (std::cout);
104
105 if (Jnlst()->ProduceOutput(Ipopt::J_MOREVECTOR, J_BOUNDTIGHTENING)) {
106 Jnlst()->Printf(Ipopt::J_MOREVECTOR, J_BOUNDTIGHTENING," := ");
107 variables_ [i] -> Image () -> print (std::cout);
108 }
109
110 Jnlst()->Printf(Ipopt::J_VECTOR, J_BOUNDTIGHTENING,"\n");
111 }
112
113 if (knownOptimum &&
114 ((knownOptimum [i] < Lb (i) - COUENNE_EPS) ||
115 (knownOptimum [i] > Ub (i) + COUENNE_EPS)))
116
117 Jnlst () -> Printf (Ipopt::J_DETAILED, J_BOUNDTIGHTENING,
118 "#### implied b_%d [%g,%g] cuts optimum %g\n",
119 i, Lb (i), Ub (i),
120 knownOptimum [i]);
121
122 //printf ("impli %2d ", nvar+i);
123
124 /*if (variables_ [i] -> Image () -> Argument () ||
125 variables_ [i] -> Image () -> ArgList ()) {
126
127 expression *arg = variables_ [i] -> Image () -> Argument ();
128
129 if (!arg) {
130 for (int k=0; k < variables_ [i] -> Image () -> nArgs (); k++) {
131 arg = variables_ [i] -> Image () -> ArgList () [k];
132 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING," ");
133 arg -> print (std::cout);
134 if (arg -> Index () >= 0) {
135 int ind = arg -> Index ();
136 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING,
137 " in [%g,%g]",
138 expression::Lbound (ind),
139 expression::Ubound (ind));
140 }
141 }
142 } else {
143 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING," ");
144 arg -> print (std::cout);
145 if (arg -> Index () >= 0) {
146 int ind = arg -> Index ();
147 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING," in [%g,%g]",
148 expression::Lbound (ind),
149 expression::Ubound (ind));
150 }
151 }
152 } else Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING," [no args]");
153 Jnlst()->Printf(Ipopt::J_DETAILED, J_BOUNDTIGHTENING,"\n");*/
154
155 nchg++;
156 }
157 }
158 }
159
160 if (nchg)
161 Jnlst () -> Printf (Ipopt::J_DETAILED, J_BOUNDTIGHTENING, " implied bounds: %d changes\n", nchg);
162
163 return nchg;
164 }
165