source: trunk/Couenne/src/branch/CouenneChooseStrong.cpp @ 930

Last change on this file since 930 was 930, checked in by pbelotti, 8 years ago

using sparse sdp cuts code, cleaned some sdpcuts code. Minor leak in strong branching. Still segfaulting in sdpcuts, will fix

  • Property svn:keywords set to Author Date Id Revision
File size: 27.5 KB
Line 
1/* $Id: CouenneChooseStrong.cpp 930 2012-12-24 00:38:19Z pbelotti $
2 *
3 * Name:    CouenneChooseStrong.cpp
4 * Authors: Andreas Waechter, IBM Corp.
5 *          Pietro Belotti, Lehigh University
6 *          Francois Margot, Carnegie Mellon University
7 * Purpose: Strong branching objects for Couenne
8 *
9 * (C) Carnegie-Mellon University, 2006-11.
10 * This file is licensed under the Eclipse Public License (EPL)
11 */
12
13#include "BonChooseVariable.hpp"
14
15#include "CouenneObject.hpp"
16#include "CouenneChooseStrong.hpp"
17#include "CouenneProblem.hpp"
18#include "CouenneProblemElem.hpp"
19#include "CouenneBranchingObject.hpp"
20#include "CouenneRecordBestSol.hpp"
21
22// The recommended ones:
23#define FM_SORT_STRONG
24#define FM_SEC_SORT_USEFUL
25#define USE_NOT_TRUSTED
26
27//#define TRACE_STRONG
28//#define TRACE_STRONG2
29//#define FM_ALWAYS_SORT
30//#define USE_SMALL_GAP
31//#define OLD_STYLE
32
33using namespace Ipopt;
34using namespace Couenne;
35
36const CouNumber estProdEps = 1e-6;
37
38#ifdef COIN_HAS_NTY
39#include "Nauty.h"
40#endif
41
42  /// constructor
43  CouenneChooseStrong::CouenneChooseStrong (Bonmin::BabSetupBase &b, CouenneProblem* p, JnlstPtr jnlst) :
44
45  Bonmin::BonChooseVariable (b, b.continuousSolver()),
46  problem_          (p),
47  jnlst_            (jnlst),
48  branchtime_       (0.) {
49
50    std::string s;
51
52    b.options () -> GetStringValue ("pseudocost_mult_lp", s, "couenne.");
53    pseudoUpdateLP_ = (s == "yes");     
54
55    b.options () -> GetStringValue ("estimate_select", s, "couenne.");
56    estimateProduct_ = (s == "product");
57
58    b.options () -> GetStringValue ("trust_strong", s, "couenne.");
59
60    // trust solution from strong branching to provide right LB
61
62    setTrustStrongForSolution (s == "yes");
63    setTrustStrongForBound    (s == "yes");
64  }
65
66  /// copy constructor
67  CouenneChooseStrong::CouenneChooseStrong (const CouenneChooseStrong& rhs) :
68    Bonmin::BonChooseVariable (rhs),
69    problem_          (rhs.problem_),
70    pseudoUpdateLP_   (rhs.pseudoUpdateLP_),
71    estimateProduct_  (rhs.estimateProduct_),
72    jnlst_            (rhs.jnlst_),
73    branchtime_       (rhs.branchtime_)
74  {}
75
76  /// destructor
77  CouenneChooseStrong::~CouenneChooseStrong()
78  {if (branchtime_ > 1e-9) jnlst_ -> Printf (J_ERROR, J_BRANCHING, "Strong branching: total time %g\n", branchtime_);}
79
80  /// cloning method
81  OsiChooseVariable *
82  CouenneChooseStrong::clone() const
83  {return new CouenneChooseStrong(*this);}
84
85  /// assignment operator
86  CouenneChooseStrong&
87  CouenneChooseStrong::operator=(const CouenneChooseStrong & rhs)
88  {
89    if (this != &rhs) {
90      Bonmin::BonChooseVariable::operator=(rhs);
91      problem_         = rhs.problem_;
92      pseudoUpdateLP_  = rhs.pseudoUpdateLP_;
93      estimateProduct_ = rhs.estimateProduct_;
94      jnlst_           = rhs.jnlst_;
95      branchtime_      = rhs.branchtime_;
96    }
97    return *this;
98  }
99
100/***********************************************************************/
101int CouenneChooseStrong::goodCandidate(OsiSolverInterface *solver,
102                                       OsiBranchingInformation *info,
103                                       OsiObject **object, const int iObject,
104                                       const double prec) {
105
106  int vInd = object [iObject] -> columnNumber ();
107
108  if (vInd < 0) return 3;  // not a variable object, so deem it good
109
110  bool varIsInt = solver -> isInteger (vInd);
111
112  // all object now are CouenneObjects or derivates (CouenneVarObject,
113  // CouenneSOSObject, etc.)
114
115  //CouenneObject    *co    = dynamic_cast <CouenneObject    *> (object [iObject]);
116  //OsiSimpleInteger *simpl = dynamic_cast <OsiSimpleInteger *> (object [iObject]);
117 
118  // int vInd = -1;
119  // bool varIsInt = false;
120  // if(co) {
121  //   vInd = co->Reference()->Index();
122  //   if(vInd >= 0) {
123  //     varIsInt = co->Reference()->isInteger();
124  //   }
125  // }
126  // else {
127  //   if(simpl) {
128  //     vInd = object[iObject]->columnNumber();
129  //     varIsInt = true;
130  //   }
131  //   else {
132
133  //     // printf("CouenneChooseStrong::goodCandidate: ### ERROR: unknown object\n");
134  //     // exit(1);
135
136  //     // this is probably a SOS object, and anyhow we don't want to
137  //     // exit on it.
138
139  //     return 3;
140  //   }
141  // }
142 
143  int goodCand = 3; // good candidate
144 
145  // Must not call branch() for integer variable vInd with
146  // upper == lower or for OsiSimpleInteger with
147  // info->solution[vInd] not between lower and upper
148  if((vInd >= 0) && varIsInt) {
149    double vUp = solver->getColUpper()[vInd];
150    double vLow = solver->getColLower()[vInd];
151    double infoVal = info->solution_[vInd];
152    double distToInt = fabs(infoVal - floor(infoVal + 0.5));
153    if(distToInt > 0.5) {
154      distToInt = 1 - distToInt;
155    }
156    // if(simpl) {
157    //   goodCand = 0; // bad candidate
158    //   if((distToInt > info->integerTolerance_) &&
159    //      (vUp > vLow + prec)) {
160    //     goodCand = 3; // good candidate
161    //     if((vUp + prec < infoVal) || (infoVal < vLow - prec)) {
162    //       goodCand = 1; // bad candidate
163    //     }
164    //   }
165    // }
166    //if(co) {
167      goodCand = 2;
168      if(vUp > vLow + prec) {
169        goodCand = 3; // good candidate
170      }
171      //}
172  }
173   
174  return(goodCand);
175} /* goodCandidate */
176
177/***********************************************************************/
178bool CouenneChooseStrong::saveBestCand(OsiObject **object, const int iObject, 
179                                       const double value, 
180                                       const double upEstimate, 
181                                       const double downEstimate,
182                                       double &bestVal1, 
183                                       double &bestVal2, int &bestIndex,
184                                       int &bestWay) {
185  bool retval = false;
186  if(value > bestVal1) {
187    retval = true;
188    bestVal1 = value;
189    bestIndex = iObject;
190    bestWay = upEstimate > downEstimate ? 0 : 1;
191    // but override if there is a preferred way
192    const OsiObject * obj = object[iObject];
193    if (obj->preferredWay() >= 0 && obj->infeasibility()) {
194      bestWay = obj->preferredWay();
195    }
196  }
197  return(retval);
198} /* saveBestCand */
199
200/*******************************************************************/
201  /* Choose a variable. Returns:
202
203    -1  Node is infeasible
204     0  Normal termination - we have a candidate
205     1  All look satisfied - no candidate
206     2  We can change the bound on a variable - but we also have a strong branching candidate
207     3  We can change the bound on a variable - but we have a non-strong branching candidate
208     4  We can change the bound on a variable - no other candidates
209
210     We can pick up branch from whichObject() and whichWay()
211     We can pick up a forced branch (can change bound) from whichForcedObject() and whichForcedWay()
212     If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
213  */
214  int CouenneChooseStrong::chooseVariable (OsiSolverInterface * solver,
215                                           OsiBranchingInformation *info,
216                                           bool fixVariables) {
217
218    /// Note: had to copy code from
219    /// BonChooseVariable::chooseVariable() in order to test product
220    /// thing
221
222    problem_ -> domain () -> push
223      (problem_ -> nVars (),
224       info -> solution_,
225       info -> lower_,
226       info -> upper_);
227
228#ifdef TRACE_STRONG2
229    int pv = -1;
230    if(problem_->doPrint_) {
231      if(pv > -1) {
232        printf("CCS: beg: x[%d]: %10.4f  lb: %10.4f  ub: %10.4f\n",
233               pv, solver->getColSolution()[pv], solver->getColLower()[pv], solver->getColUpper()[pv]);
234        printf("CCS: info: x[%d]: %10.4f  lb: %10.4f  ub: %10.4f\n",
235               pv, info->solution_[pv], info->lower_[pv], info->upper_[pv]);
236        printf("CCS: problem: lb: %10.4f  ub: %10.4f\n",
237               problem_->Lb(pv), problem_->Ub(pv));
238      }
239    }
240 #endif                                                                         
241
242    int retval;
243    const double prec = problem_->getFeasTol();
244
245    //int retval = BonChooseVariable::chooseVariable (solver, info, fixVariables);
246
247    // COPY of Bonmin starts here ////////////////////////////////////////////
248
249    // We assume here that chooseVariable is called once at the very
250    // beginning with fixVariables set to true.  This is then the root
251    // node.
252
253    bool isRoot = isRootNode(info);
254    int numberStrong = numberStrong_;
255
256    if (isRoot) {
257      numberStrong = CoinMax(numberStrong_, numberStrongRoot_);
258    }
259
260    if (numberUnsatisfied_) {
261      int cardIndForPseudo = 0, 
262        *indForPseudo = new int[numberUnsatisfied_];
263      OsiObject ** object = solver->objects();
264      const double* upTotalChange = pseudoCosts_.upTotalChange();
265      const double* downTotalChange = pseudoCosts_.downTotalChange();
266      const int* upNumber = pseudoCosts_.upNumber();
267      const int* downNumber = pseudoCosts_.downNumber();
268      int numberBeforeTrusted = pseudoCosts_.numberBeforeTrusted();
269
270      // number of objects to be chosen by doStrongBranching()
271      int numberLeft = CoinMin (numberStrong - numberStrongDone_, numberUnsatisfied_);
272
273      results_.clear();
274      int returnCode = 0;
275      int returnCodeSB = 0;
276      bestObjectIndex_ = -1;
277      bestWhichWay_ = -1;
278      firstForcedObjectIndex_ = -1;
279      firstForcedWhichWay_ =-1;
280      double bestTrustedVal1 = -COIN_DBL_MAX;
281      double bestTrustedVal2 = -COIN_DBL_MAX;
282
283      bool smallGap = false;
284      bool sbObjPosImp = false; // true if an object on which strong branching
285                                // was performed has a positive improvement
286                                // in both branches; used only when gap is
287                                // deemed small
288
289#ifdef USE_SMALL_GAP
290      int objInd = problem_ -> Obj (0) -> Body () -> Index ();
291      double lbGap = objInd >= 0 ? info -> lower_ [objInd] : problem_ -> Obj (0) -> Body () -> Value ();
292      double ubGap = problem_ -> getCutOff ();
293      double currentGap = 
294        (ubGap >  COUENNE_INFINITY    / 10 ||
295         lbGap < -Couenne_large_bound / 10) ? 1e3 : 
296        fabs (ubGap - lbGap) / (1.e-3 + CoinMin (fabs (ubGap), fabs (lbGap)));
297
298      if(currentGap < 1e-3) {
299        smallGap = true;
300      }
301#endif
302
303#ifdef TRACE_STRONG
304      if((problem_->doPrint_) && (number_not_trusted_ > 0)) {
305        printf("number_not_trusted: %d\n", number_not_trusted_);
306      }
307#endif
308
309      for (int i=0;i<numberLeft;i++) {
310        int iObject = list_[i];
311        if (numberBeforeTrusted == 0||
312            i < minNumberStrongBranch_ ||
313            (
314              only_pseudo_when_trusted_ && number_not_trusted_>0 ) ||
315              ( !isRoot && (upNumber[iObject]<numberBeforeTrusted ||
316                          downNumber[iObject]<numberBeforeTrusted ))||
317              ( isRoot && (!upNumber[iObject] && !downNumber[iObject])) ) {
318         
319#ifdef TRACE_STRONG
320          if(problem_->doPrint_) {
321            printf("Push object %d for strong branch\n", iObject);
322          }
323#endif
324          results_.push_back (Bonmin::HotInfo (solver, info, object, iObject));
325        }
326        else {
327
328#ifdef TRACE_STRONG
329          if(problem_->doPrint_) {
330            printf("Use pseudo cost for object %d\n", iObject);
331          }
332#endif
333          indForPseudo[cardIndForPseudo] = iObject;
334          cardIndForPseudo++;
335        }
336      }
337
338      int numberFixed=0;
339
340      if (results_.size() > 0) {
341
342        //
343        // do strong branching
344        //
345
346        returnCodeSB = doStrongBranching (solver, info, results_.size(), 1);
347
348        if (bb_log_level_>=3) {
349          const char* stat_msg[] = {"NOTDON", "FEAS", "INFEAS", "NOFINI"};
350          message(SB_HEADER)<<CoinMessageEol;
351          for (unsigned int i = 0; i< results_.size(); i++) {
352            double up_change = results_[i].upChange();
353            double down_change = results_[i].downChange();
354            int up_status = results_[i].upStatus();
355            int down_status = results_[i].downStatus();
356            message(SB_RES)<<(int) i<<stat_msg[down_status+1]<<down_change
357            <<stat_msg[up_status+1]<< up_change<< CoinMessageEol;
358          }
359        }
360
361        if (returnCodeSB >= 0 && returnCodeSB <= 2) { // 1, 2: some can be fixed
362          if(returnCodeSB > 0) {
363            returnCode = 4; // no bestObject yet
364          }
365          else {
366            returnCode = 0;
367          }
368          for (unsigned int i=0;i < results_.size (); i++) {
369
370            if((results_[i].upStatus() < 0) || (results_[i].downStatus() < 0))
371              continue;
372
373            // if((results_[i].upStatus() < 0) || (results_[i].downStatus() < 0)) {
374            //   continue;
375            // }
376
377            int iObject = results_[i].whichObject();
378            const OsiObject * obj = object[iObject];
379            int needBranch = goodCandidate(solver, info, object, iObject, prec);
380
381            ///////////////////////////////////////////////////////////////////
382
383            double upEstimate;
384
385            if (results_[i].upStatus()!=1) {
386              assert (results_[i].upStatus()>=0);
387              upEstimate = results_[i].upChange();
388            }
389            else {
390              // infeasible - just say expensive
391              if (info->cutoff_<1.0e50)
392                upEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
393              else
394                upEstimate = 2.0*fabs(info->objectiveValue_);
395              if (firstForcedObjectIndex_ <0) {
396                // first fixed variable
397                firstForcedObjectIndex_ = iObject;
398                firstForcedWhichWay_ =0;
399              }
400
401              numberFixed++;
402              if (fixVariables) {
403                if(needBranch >= 2) { // for OsiSimpleInteger: do not branch
404                  // if upper == lower or if info value is outside bounds
405                  // for other objects: branch
406                  OsiBranchingObject * branch = 
407                                        obj->createBranch(solver, info, 0);
408                  branch -> branch (solver);
409                  delete branch;
410                }
411              }
412            }
413
414            ///////////////////////////////////////////////////////////////////
415
416            double downEstimate;
417
418            if (results_[i].downStatus()!=1) {
419              assert (results_[i].downStatus()>=0);
420              downEstimate = results_[i].downChange();
421            }
422            else {
423              // infeasible - just say expensive
424              if (info->cutoff_<1.0e50)
425                downEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
426              else
427                downEstimate = 2.0*fabs(info->objectiveValue_);
428              if (firstForcedObjectIndex_ <0) {
429                firstForcedObjectIndex_ = iObject;
430                firstForcedWhichWay_ =1;
431              }
432              numberFixed++;
433              if (fixVariables) {
434                if(needBranch >= 2) { // for OsiSimpleInteger: do not branch
435                  // if upper == lower or if info value is outside bounds
436                  // for other objects: branch
437                  OsiBranchingObject * branch = 
438                                         obj->createBranch(solver, info, 1);
439                  branch -> branch (solver);
440                  delete branch;
441                }
442              }
443            }
444         
445            double
446              MAXMIN_CRITERION = maxminCrit (info),
447              minVal, maxVal, value;
448
449            if (downEstimate < upEstimate) {
450              minVal = downEstimate;
451              maxVal = upEstimate;
452            } else {
453              minVal = upEstimate;
454              maxVal = downEstimate;
455            }
456
457            if(smallGap) { // use change in objective value
458              value = minVal;
459            }
460            else {
461              value = 
462                estimateProduct_ ? 
463                ((estProdEps + minVal) * maxVal) :
464                (       MAXMIN_CRITERION  * minVal + 
465                        (1.0 - MAXMIN_CRITERION) * maxVal);
466            }
467
468            if((needBranch == 3) &&
469               saveBestCand(object, iObject, value, upEstimate, downEstimate,
470                            bestTrustedVal1, 
471                            bestTrustedVal2, bestObjectIndex_, bestWhichWay_)) {
472              if(returnCodeSB) { // 1 or 2
473                returnCode = 2; 
474              }
475
476#ifdef USE_SMALL_GAP
477              if(smallGap && (minVal > 1e-3)) {
478                sbObjPosImp = true;
479              }
480#endif
481
482            }
483          }
484        }
485        else { // returnCodeSB is -1 or 3
486          if (returnCodeSB == 3) { // max time - just choose one
487            if(bestObjectIndex_ < 0) {
488              // should not select an integer var with fixed bounds
489              // taken care of below
490              bestObjectIndex_ = list_[0];
491              bestWhichWay_ = 0;
492              returnCode = 0;
493            }
494          }
495          else {
496            returnCode = -1;
497          }
498        }
499#ifdef OLD_STYLE
500        if(bestObjectIndex_ < 0) {
501          bestObjectIndex_ = list_[0];
502        }
503        cardIndForPseudo = 0; // do not scan other vars using pseudo costs
504#endif
505      }
506
507      if((returnCodeSB != -1) && 
508         ((returnCode != 0) || (!sbObjPosImp))) { 
509                  // if returnCodeSB == -1 (i.e. problem is infeasible)
510                  // no need to scan objects with pseudocosts
511                  // if returnCode == 0 and sbObjPOsImp is true
512                  // we want to branch on that object
513                  // to be sure to improve the lower bound
514       
515        // to keep best object skipped on basis of bounds and branching value
516        int bestObjectIndex2 = -1;
517        int bestWhichWay2 = 0;
518        double bestTrusted2Val1 = -COIN_DBL_MAX;
519        double bestTrusted2Val2 = -COIN_DBL_MAX;
520       
521        for(int ips=0; ips<cardIndForPseudo; ips++) {
522          int iObject = indForPseudo[ips];
523          const OsiObject * obj = object[iObject];
524          int needBranch = goodCandidate(solver, info, object, iObject, prec);
525
526          double
527            upEstimate       = (upTotalChange   [iObject] * obj -> upEstimate   ()) / upNumber   [iObject],
528            downEstimate     = (downTotalChange [iObject] * obj -> downEstimate ()) / downNumber [iObject],
529            MAXMIN_CRITERION = maxminCrit (info),
530            minVal, maxVal, value;
531         
532          if (downEstimate < upEstimate) {
533            minVal = downEstimate;
534            maxVal = upEstimate;
535          } else {
536            minVal = upEstimate;
537            maxVal = downEstimate;
538          }
539         
540          value = 
541            estimateProduct_ ? 
542            ((estProdEps + minVal) * maxVal) :
543            (       MAXMIN_CRITERION  * minVal + 
544                    (1.0 - MAXMIN_CRITERION) * maxVal);
545         
546         
547          // store bad candidates in secondary best
548          if(needBranch != 3) {
549            if(saveBestCand(object, iObject, value, 
550                            upEstimate, downEstimate,
551                            bestTrusted2Val1, 
552                            bestTrusted2Val2, bestObjectIndex2, 
553                            bestWhichWay2)) {
554              // no returnCode change
555            }
556
557#ifdef TRACE_STRONG
558            if(problem_->doPrint_) {
559              printf("Object %d skip pseudocost\n", iObject);
560            }
561#endif
562          }
563          else {
564            if(saveBestCand(object, iObject, value, 
565                            upEstimate, downEstimate,
566                            bestTrustedVal1, 
567                            bestTrustedVal2, bestObjectIndex_, bestWhichWay_)) {
568              returnCode = (returnCode ? 3 : 0); // if returnCode was 2 or 3
569                                                 // it becomes 3
570            }
571
572#ifdef TRACE_STRONG
573            if(problem_->doPrint_) {
574              printf("Object %d use pseudocost\n", iObject);
575            }
576#endif
577          }
578        }
579   
580        if((bestObjectIndex_ < 0) && (bestObjectIndex2 >= 0)) {
581          bestObjectIndex_ = bestObjectIndex2;
582          bestWhichWay_ = bestWhichWay2;
583          bestTrustedVal1 = bestTrusted2Val1;
584          returnCode = 4;
585        }
586      }
587
588      int objectVarInd = -1;
589      if(bestObjectIndex_ >= 0) {
590        OsiObject * obj = object[bestObjectIndex_];
591        obj->setWhichWay(bestWhichWay_);
592        // CouenneObject *co =  dynamic_cast <CouenneObject *>(object[bestObjectIndex_]);
593        // if(co) {
594        //   objectVarInd = co->Reference()->Index();
595        // }
596        // else {
597        objectVarInd = obj->columnNumber();
598        //}
599
600        message(BRANCH_VAR)<<bestObjectIndex_<< bestWhichWay_ <<CoinMessageEol;
601
602#ifdef TRACE_STRONG
603        if(problem_->doPrint_) {
604          if(objectVarInd >= 0) {
605            double vUb = solver->getColUpper()[objectVarInd];
606            double vLb = solver->getColLower()[objectVarInd];
607            double vSolI = info->solution_[objectVarInd];
608            double vSolS = solver->getColSolution()[objectVarInd];
609            printf("Branch on object %d (var: %d): solInfo: %10.4f  SolSolver: %10.4f low: %10.4f  up: %10.4f\n",
610                   bestObjectIndex_, objectVarInd, vSolI, vSolS, vLb, vUb);
611          }
612          else {
613            printf("Branch on object %d (var: -1)\n", bestObjectIndex_);
614          }
615        }
616#endif
617      }
618      message(CHOSEN_VAR)<<bestObjectIndex_<<CoinMessageEol;
619   
620      if (numberFixed==numberUnsatisfied_&&numberFixed)
621        returnCode=4;
622
623      if((returnCode == 2) || (returnCode == 3)) {
624        if((objectVarInd > -1) && 
625           (goodCandidate(solver, info, object, bestObjectIndex_, prec) != 2)) {
626          // Can occur: two objects for same var, first scanned object
627          // has both branches feasible and is saved as bestObjectIndex_,
628          // second scanned object fixes the variable
629          returnCode = 4;
630        }
631      }
632      retval = returnCode;
633
634      delete[] indForPseudo;
635    }
636    else {
637      retval = 1;
638    }
639
640    // COPY of Bonmin ends here //////////////////////////////////////////////
641
642
643#ifdef TRACE_STRONG2
644    if(problem_->doPrint_) {
645      if(pv > -1) {
646        printf("CCS: end: x[%d]: %10.4f  lb: %10.4f  ub: %10.4f\n",
647               pv, solver->getColSolution()[pv], solver->getColLower()[pv], solver->getColUpper()[pv]);
648        printf("CCS: info: x[%d]: %10.4f  lb: %10.4f  ub: %10.4f\n",
649               pv, info->solution_[pv], info->lower_[pv], info->upper_[pv]);
650        printf("CCS: problem: lb: %10.4f  ub: %10.4f\n",
651               problem_->Lb(pv), problem_->Ub(pv));
652      }
653    }
654#endif
655
656#ifdef TRACE_STRONG
657    if(problem_->doPrint_) {
658      printf("CouenneChooseStrong::ChooseVariable(): retval: %d\n", retval);
659    }
660#endif
661 
662    problem_ -> domain () -> pop ();
663
664    return retval;
665  }
666
667void eliminateIntegerObjects (OsiSolverInterface *model);
668void eliminateIntegerObjects (CbcModel           *model);
669
670/*******************************************************************/
671  // Sets up strong list and clears all if initialize is true.
672  // Returns number of infeasibilities.
673  int CouenneChooseStrong::setupList (OsiBranchingInformation *info, bool initialize) {
674
675    static bool
676      firstCall = true,
677      warned    = false;
678
679    if (firstCall) {
680
681      eliminateIntegerObjects (const_cast <OsiSolverInterface *> (solver_));
682      eliminateIntegerObjects (const_cast <OsiSolverInterface *> (info -> solver_));
683
684      firstCall = false;
685    }
686
687    initialize = true; // to avoid failed assert in BonChooseVariable::setupList()
688
689    problem_ -> domain () -> push
690      (problem_ -> nVars (),
691       info -> solution_, 
692       info -> lower_, 
693       info -> upper_); // have to alloc+copy
694
695    jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
696                      "----------------- (strong) setup list\n");
697
698    if (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING)) {
699      for (int i=0; i<problem_ -> domain () -> current () -> Dimension (); i++)
700        printf ("%4d %20.4g [%20.4g %20.4g]\n", i,
701                info -> solution_ [i], info -> lower_ [i], info -> upper_ [i]);
702    }
703
704#ifdef TRACE_STRONG
705    OsiObject ** object = info->solver_->objects();
706    if(problem_->doPrint_) {
707      printObjViol(info);
708    }
709#endif
710
711    // int way;
712    // for (int i=0; i<info->solver_->numberObjects(); ++i)
713    //   printf ("[%d:%d,%g] ",
714    //        info -> solver_ -> objects () [i] -> columnNumber (),
715    //        info -> solver_ -> objects () [i] -> priority (),
716    //        info -> solver_ -> objects () [i] -> infeasibility (info,way));
717    // printf ("\n");
718
719    //
720    // Real list setup
721    //
722
723    int retval = gutsOfSetupList (info, initialize);
724
725    if (retval == 0) { // No branching is possible
726
727#ifdef FM_CHECKNLP2
728      if(!(problem_->checkNLP2(info->solution_, 
729                               info->objectiveValue_, true, // care about obj
730                               false, // do not stop at first viol
731                               true, // checkAll
732                               problem_->getFeasTol()))) {
733                                // false for NOT stopping at first violation
734        if (!warned) {
735          printf("CouenneChooseStrong::setupList(): ### WARNING: checkNLP2() returns infeasible, no branching object selected\n");
736          warned = true;
737        }
738      }
739#else /* not FM_CHECKNLP2 */
740      double ckObj = info->objectiveValue_;
741      if(!(problem_->checkNLP(info->solution_, ckObj, true))) {
742        if (!warned) {
743          printf("CouenneChooseStrong::setupList(): ### WARNING: checkNLP() returns infeasible, no branching object selected\n");
744          warned = true;
745        }
746      }
747#endif /* not FM_CHECKNLP2 */
748       
749#ifdef FM_TRACE_OPTSOL
750#ifdef FM_CHECKNLP2
751      problem_->getRecordBestSol()->update();
752#else /* not FM_CHECKNLP2 */
753      problem_->getRecordBestSol()->update(info->solution_, problem_->nVars(),
754                                           ckObj, problem_->getFeasTol());
755#endif /* not FM_CHECKNLP2 */
756#endif
757    }
758
759#ifdef TRACE_STRONG
760    if(problem_->doPrint_) {
761      printf("Strong list: (obj_ind var_ind priority useful)\n");
762      printf("numberStrong: %d  numberStrongRoot: %d  retval: %d\n", 
763             numberStrong_, numberStrongRoot_, retval);
764      for(int i=0; i<retval; i++) {
765        // CouenneObject *co =  dynamic_cast <CouenneObject *>(object[list_[i]]);
766        int objectInd = -1;
767        // if(co) {
768        //   objectInd = co->Reference()->Index();
769        // }
770        // else {
771          objectInd = object[list_[i]]->columnNumber();
772        // }
773        printf(" (%d %d %d %6.4f)", list_[i], objectInd, 
774               object[list_[i]]->priority(), useful_[i]);
775      }
776      printf("\n");
777    }
778#endif
779
780    // for (int i=0; i < (numberStrong_ ? CoinMin (numberStrong_, solver_ -> numberObjects ()) : 1); i++) {
781    //   printf ("list %3d: %3d ", i, list_ [i]);
782    //   if (!((i+1) % 12)) printf ("\n");
783    // }
784
785    jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
786                      "----------------- (strong) setup list done - %d infeasibilities\n", retval);
787
788    problem_ -> domain () -> pop ();
789    return retval;
790  }
791
792/****************************************************************************/
793  /// Add list of options to be read from file ////////////////////////////////////////
794  void CouenneChooseStrong::registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
795
796    roptions -> AddStringOption6
797      ("pseudocost_mult",
798       "Multipliers of pseudocosts for estimating and update estimation of bound",
799       "interval_br_rev",
800
801       "infeasibility", "infeasibility returned by object",
802
803       "projectDist",   "distance between current LP point and resulting branches' LP points",
804
805       "interval_lp",   "width of the interval between bound and current lp point",
806       "interval_lp_rev",   "similar to interval_lp, reversed",
807
808       "interval_br",   "width of the interval between bound and branching point",
809       "interval_br_rev",   "similar to interval_br, reversed");
810
811    roptions -> AddStringOption2
812      ("pseudocost_mult_lp",
813       "Use distance between LP points to update multipliers of pseudocosts " 
814       "after simulating branching",
815       "no",
816       "yes", "",
817       "no",  "");
818
819    roptions -> AddStringOption2
820      ("estimate_select",
821       "How the min/max estimates of the subproblems' bounds are used in strong branching",
822       "normal",
823       "normal",   "as usual in literature",
824       "product",  "use their product");
825
826    roptions -> AddStringOption2
827      ("trust_strong",
828       "Fathom strong branching LPs when their bound is above the cutoff",
829       "yes",
830       "yes", "",
831       "no",  "");
832  }
833
834
835  // Returns true if solution looks feasible against given objects
836  bool CouenneChooseStrong::feasibleSolution (const OsiBranchingInformation * info,
837                                              const double * solution,
838                                              int numberObjects,
839                                              const OsiObject ** objects) {
840
841#ifdef FM_CHECKNLP2
842    return problem_ -> checkNLP2 (solution, 0, false, true, true, 
843                                  problem_->getFeasTol());
844#else
845    int indobj = problem_ -> Obj (0) -> Body () -> Index ();
846    return problem_ -> checkNLP (solution, indobj >= 0 ? solution [indobj] : problem_ -> Obj (0) -> Body () -> Value ());
847#endif
848  }
849
850/****************************************************************************/
851  void CouenneChooseStrong::printObjViol(OsiBranchingInformation *info) {
852
853    OsiObject ** object = info->solver_->objects();
854    int numberObjects = info->solver_->numberObjects();
855
856    printf("CouenneChooseStrong::printObjViol(): Object violations: (obj_ind  var_ind  violation)");
857    double maxViol = 0;
858    double minPosViol = 1e50;
859    for(int i=0; i<numberObjects; i++) {
860      //CouenneObject *co =  dynamic_cast <CouenneObject *>(object[i]);
861      int indVar = -1;
862      // if(co) {
863      //        indVar = co->Reference()->Index();
864      // }
865      // else {
866      indVar = object[i]->columnNumber();
867      // }
868      int way;
869      double value = object[i]->infeasibility(info,way);
870      //double value = object[i]->checkInfeasibility(info);
871      maxViol = (value > maxViol ? value : maxViol);
872      if(value > 0.0) {
873        printf("(%d %d %f)", i, indVar, value);
874        minPosViol = (value < minPosViol ? value : minPosViol);
875      }
876    }
877    printf("\nmaxViol: %g  minPosViol: %g\n", maxViol, minPosViol);
878
879  } /* printObjViol */
880
881//}
Note: See TracBrowser for help on using the repository browser.