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

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

Merging some of the latest changes from Bonmin/branches/Couenne: added Complementarity objects, disjunctive cuts, SOS (these don't work yet). Fixed some output. Improved cut-optimum checking. Sparser initial problem by replacing constraints ax-b>=0, w=ax-b with equivalent w>=0, w=ax-b. Fixed some bugs in new getBounds.

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