source: trunk/Couenne/src/bound_tightening/obbt.cpp @ 215

Last change on this file since 215 was 215, checked in by pbelotti, 12 years ago

templatized CouenneSolverInterface?. Fixed a few branching bugs. Every object and branchingObject has CouenneCutGenerator? and CouenneProblem? pointer.

  • Property svn:keywords set to Id
File size: 5.8 KB
Line 
1/* $Id: obbt.cpp 215 2009-07-08 15:43:38Z pbelotti $
2 *
3 * Name:    obbt.cpp
4 * Author:  Pietro Belotti
5 * Purpose: Optimality-Based Bound Tightening
6 *
7 * (C) Carnegie-Mellon University, 2006.
8 * This file is licensed under the Common Public License (CPL)
9 */
10
11#include "CoinHelperFunctions.hpp"
12#include "CglCutGenerator.hpp"
13#include "CouenneCutGenerator.hpp"
14#include "CouenneProblem.hpp"
15#include "OsiClpSolverInterface.hpp"
16
17#define OBBT_EPS 1e-3
18#define MAX_OBBT_LP_ITERATION 100
19
20// minimum #bound changed in obbt to generate further cuts
21#define THRES_NBD_CHANGED 1
22
23// maximum number of obbt iterations
24#define MAX_OBBT_ITER 1
25
26// defined in generateCuts.cpp
27void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
28
29
30// OBBT for one sense (max/min) and one class of variables (orig/aux)
31int CouenneProblem::call_iter (OsiSolverInterface *csi, 
32                               t_chg_bounds *chg_bds, 
33                               const CoinWarmStart *warmstart, 
34                               Bonmin::BabInfo *babInfo,
35                               double *objcoe,
36                               enum nodeType type,
37                               int sense) const {
38
39  int ncols   = csi -> getNumCols (),
40      nimprov = 0;
41
42  for (int ii=0; ii<ncols; ii++) {
43
44    if (CoinCpuTime () > maxCpuTime_)
45      break;
46
47    int i = evalOrder (ii);
48
49    if ((Var (i) -> Type () == type) &&
50        (Var (i) -> Multiplicity () > 0)) {
51
52      int ni = obbt_iter (csi, chg_bds, warmstart, babInfo, objcoe, sense, i);
53
54      if (ni < 0) return ni;
55      nimprov += ni;
56    }
57  }
58
59  return nimprov;
60}
61
62
63/// Optimality based bound tightening -- inner loop
64
65int CouenneProblem::obbtInner (OsiSolverInterface *csi,
66                               OsiCuts &cs,
67                               t_chg_bounds *chg_bds,
68                               Bonmin::BabInfo * babInfo) const {
69
70  // set large bounds to infinity (as per suggestion by JJF)
71
72  int ncols = csi -> getNumCols ();
73  const double *lb = csi -> getColLower (),
74               *ub = csi -> getColUpper ();
75
76  double inf = csi -> getInfinity ();
77
78  for (int i=ncols; i--;) {
79    if (lb [i] < - COUENNE_INFINITY) csi -> setColLower (i, -inf);
80    if (ub [i] >   COUENNE_INFINITY) csi -> setColUpper (i,  inf);
81  }
82
83  //  csi -> setHintParam (OsiDoDualInResolve, false);
84
85  // setup cloned interface for later use
86  csi -> setObjSense (1); // minimization
87  csi -> setIntParam (OsiMaxNumIteration, MAX_OBBT_LP_ITERATION);
88  csi -> applyCuts (cs);   // apply all (row+column) cuts to formulation
89  csi -> initialSolve ();
90
91  const CoinWarmStart *warmstart = csi -> getWarmStart ();
92
93  // improve each bound
94
95  double *objcoe = (double *) malloc (ncols * sizeof (double));
96
97  // set obj function coefficients to zero
98  for (int i=ncols; i--;)
99    *objcoe++ = 0.;
100  objcoe -= ncols;
101
102  csi -> setObjective (objcoe);
103  csi -> setObjSense (1);        // minimization
104
105  int nimprov = 0;
106 
107  const int Infeasible = 1;
108
109  try {
110
111    int ni;
112
113    if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, VAR,  1)) < 0) throw Infeasible;
114    nimprov += ni;
115
116    if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, VAR, -1)) < 0) throw Infeasible;
117    nimprov += ni;
118
119    if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, AUX,  1)) < 0) throw Infeasible;
120    nimprov += ni;
121
122    if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, AUX, -1)) < 0) throw Infeasible;
123    nimprov += ni;
124  }
125
126  catch (int exception) {
127
128    if (exception == Infeasible)
129      nimprov = -1;
130  }
131
132  free (objcoe);
133  delete warmstart;
134
135  return (nimprov);
136}
137
138
139// Optimality based bound tightening -- main loop
140int CouenneProblem::obbt (const CouenneCutGenerator *cg,
141                          const OsiSolverInterface &si,
142                          OsiCuts &cs,
143                          const CglTreeInfo &info,
144                          Bonmin::BabInfo * babInfo,
145                          t_chg_bounds *chg_bds) {
146
147  // Do OBBT if:
148
149  if (doOBBT_ &&                        // flag is checked, AND
150      ((logObbtLev_ != 0) ||               // (parameter is nonzero OR
151       (info.level == 0)) &&               //  we are at root node), AND
152      (info.pass == 0) &&               // at first round of cuts, AND
153      ((logObbtLev_ < 0) ||               // (logObbtLev = -1, OR
154       (info.level <= logObbtLev_) ||     //  depth is lower than COU_OBBT_CUTOFF_LEVEL, OR
155                                          //  probability inversely proportional to the level)
156       (CoinDrand48 () < pow (2., (double) logObbtLev_ - (info.level + 1))))) {
157
158    jnlst_ -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING, "----- OBBT\n");
159
160    // TODO: why check info.pass==0? Why not more than one pass? It
161    // should be anyway checked that info.level be >= 0 as <0 means
162    // first call at root node
163
164    OsiSolverInterface *csi = si.clone (true);
165    //dynamic_cast <CouenneSolverInterface<T> *>
166
167    OsiClpSolverInterface *clpcsi = dynamic_cast <OsiClpSolverInterface *> (csi);
168
169    if (!clpcsi)
170      clpcsi -> setupForRepeatedUse ();
171    //csi -> doingResolve () = false;
172
173    //csi -> setHintParam (OsiDoDualInResolve, false);
174
175    int nImprov, nIter = 0;
176
177    bool notImproved = false;
178
179    while (!notImproved && 
180           (nIter++ < MAX_OBBT_ITER) &&
181           ((nImprov = obbtInner (csi, cs, chg_bds, babInfo)) > 0) &&
182           (CoinCpuTime () < maxCpuTime_)) {
183
184      int nchanged, *changed = NULL;
185
186      /// OBBT has tightened, add improved bounds
187      sparse2dense (nVars (), chg_bds, changed, nchanged);
188      cg -> genColCuts (*csi, cs, nchanged, changed);
189
190      if ((nIter < MAX_OBBT_ITER) && 
191          (nImprov >= THRES_NBD_CHANGED)) {
192
193        // only generate new row cuts if improvents are enough
194        int nCurCuts = cs.sizeRowCuts ();
195        cg -> genRowCuts (*csi, cs, nchanged, changed, chg_bds);
196
197        if (nCurCuts == cs.sizeRowCuts ())
198          notImproved = true; // repeat only if new cuts available
199
200      } else notImproved = true;
201
202      if (changed) 
203        free (changed);
204    }
205
206    //csi -> doingResolve () = true;
207
208    delete csi;
209
210    if (nImprov < 0) {
211      jnlst_->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING, "  Couenne: infeasible node after OBBT\n");
212      return -1;
213    }
214  }
215
216  return 0;
217}
Note: See TracBrowser for help on using the repository browser.