Changeset 531


Ignore:
Timestamp:
May 4, 2007 6:18:13 PM (12 years ago)
Author:
pbelotti
Message:

added reduced cost fixing. Separated bound tightening from generateCuts. Started three-way branching, not used yet.

Location:
branches/Couenne/Couenne/src
Files:
3 added
9 edited

Legend:

Unmodified
Added
Removed
  • branches/Couenne/Couenne/src/Makefile.am

    r523 r531  
    1919# List all source files for this library, including headers
    2020libCouenne_la_SOURCES = \
     21        branch/CouenneThreeWayBranchObj.cpp \
    2122        branch/CouenneBranchingObject.cpp \
    2223        branch/CouenneObject.cpp \
     
    7071        convex/CouenneCutGenerator.cpp \
    7172        convex/generateCuts.cpp \
     73        convex/boundTightening.cpp \
    7274        convex/genColCuts.cpp \
    7375        problem/problem.cpp \
     
    146148        ../inc/config_couenne.h \
    147149        branch/CouenneObject.hpp \
     150        branch/CouenneThreeWayBranchObj.hpp \
    148151        branch/CouenneBranchingObject.hpp \
    149152        branch/CouenneChooseVariable.hpp \
  • branches/Couenne/Couenne/src/Makefile.in

    r523 r531  
    7474LTLIBRARIES = $(lib_LTLIBRARIES)
    7575libCouenne_la_LIBADD =
    76 am__libCouenne_la_SOURCES_DIST = branch/CouenneBranchingObject.cpp \
    77         branch/CouenneObject.cpp branch/CouenneChooseVariable.cpp \
    78         branch/getFixVarBinFun.cpp expression/operators/exprAbs.cpp \
     76am__libCouenne_la_SOURCES_DIST = branch/CouenneThreeWayBranchObj.cpp \
     77        branch/CouenneBranchingObject.cpp branch/CouenneObject.cpp \
     78        branch/CouenneChooseVariable.cpp branch/getFixVarBinFun.cpp \
     79        expression/operators/exprAbs.cpp \
    7980        expression/operators/exprDiv.cpp \
    8081        expression/operators/exprExp.cpp \
     
    116117        convex/operators/conv-exprGroup.cpp \
    117118        convex/operators/trigNewton.cpp convex/CouenneCutGenerator.cpp \
    118         convex/generateCuts.cpp convex/genColCuts.cpp \
    119         problem/problem.cpp problem/problemIO.cpp \
    120         problem/constraint.cpp problem/tightenBounds.cpp \
    121         problem/impliedBounds.cpp problem/readASLfg.cpp \
    122         util/drawCuts.cpp util/rootQ.c readnl/readnl.cpp \
    123         readnl/nl2e.cpp readnl/invmap.c
     119        convex/generateCuts.cpp convex/boundTightening.cpp \
     120        convex/genColCuts.cpp problem/problem.cpp \
     121        problem/problemIO.cpp problem/constraint.cpp \
     122        problem/tightenBounds.cpp problem/impliedBounds.cpp \
     123        problem/readASLfg.cpp util/drawCuts.cpp util/rootQ.c \
     124        readnl/readnl.cpp readnl/nl2e.cpp readnl/invmap.c
    124125@COIN_HAS_ASL_TRUE@am__objects_1 = readnl.lo nl2e.lo invmap.lo
    125 am_libCouenne_la_OBJECTS = CouenneBranchingObject.lo CouenneObject.lo \
     126am_libCouenne_la_OBJECTS = CouenneThreeWayBranchObj.lo \
     127        CouenneBranchingObject.lo CouenneObject.lo \
    126128        CouenneChooseVariable.lo getFixVarBinFun.lo exprAbs.lo \
    127129        exprDiv.lo exprExp.lo exprInv.lo exprLog.lo exprMul.lo \
     
    137139        conv-exprInv.lo conv-exprSinCos.lo conv-exprExp.lo \
    138140        conv-exprLog.lo conv-exprGroup.lo trigNewton.lo \
    139         CouenneCutGenerator.lo generateCuts.lo genColCuts.lo \
    140         problem.lo problemIO.lo constraint.lo tightenBounds.lo \
    141         impliedBounds.lo readASLfg.lo drawCuts.lo rootQ.lo \
    142         $(am__objects_1)
     141        CouenneCutGenerator.lo generateCuts.lo boundTightening.lo \
     142        genColCuts.lo problem.lo problemIO.lo constraint.lo \
     143        tightenBounds.lo impliedBounds.lo readASLfg.lo drawCuts.lo \
     144        rootQ.lo $(am__objects_1)
    143145libCouenne_la_OBJECTS = $(am_libCouenne_la_OBJECTS)
    144146depcomp = $(SHELL) $(top_srcdir)/../depcomp
     
    345347
    346348# List all source files for this library, including headers
    347 libCouenne_la_SOURCES = branch/CouenneBranchingObject.cpp \
    348         branch/CouenneObject.cpp branch/CouenneChooseVariable.cpp \
    349         branch/getFixVarBinFun.cpp expression/operators/exprAbs.cpp \
     349libCouenne_la_SOURCES = branch/CouenneThreeWayBranchObj.cpp \
     350        branch/CouenneBranchingObject.cpp branch/CouenneObject.cpp \
     351        branch/CouenneChooseVariable.cpp branch/getFixVarBinFun.cpp \
     352        expression/operators/exprAbs.cpp \
    350353        expression/operators/exprDiv.cpp \
    351354        expression/operators/exprExp.cpp \
     
    387390        convex/operators/conv-exprGroup.cpp \
    388391        convex/operators/trigNewton.cpp convex/CouenneCutGenerator.cpp \
    389         convex/generateCuts.cpp convex/genColCuts.cpp \
    390         problem/problem.cpp problem/problemIO.cpp \
    391         problem/constraint.cpp problem/tightenBounds.cpp \
    392         problem/impliedBounds.cpp problem/readASLfg.cpp \
    393         util/drawCuts.cpp util/rootQ.c $(am__append_1)
     392        convex/generateCuts.cpp convex/boundTightening.cpp \
     393        convex/genColCuts.cpp problem/problem.cpp \
     394        problem/problemIO.cpp problem/constraint.cpp \
     395        problem/tightenBounds.cpp problem/impliedBounds.cpp \
     396        problem/readASLfg.cpp util/drawCuts.cpp util/rootQ.c \
     397        $(am__append_1)
    394398COINLIBS = \
    395399        $(OSIOBJDIR)/src/libOsi.la \
     
    442446        ../inc/config_couenne.h \
    443447        branch/CouenneObject.hpp \
     448        branch/CouenneThreeWayBranchObj.hpp \
    444449        branch/CouenneBranchingObject.hpp \
    445450        branch/CouenneChooseVariable.hpp \
     
    560565@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CouenneCutGenerator.Plo@am__quote@
    561566@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CouenneObject.Plo@am__quote@
     567@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CouenneThreeWayBranchObj.Plo@am__quote@
    562568@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/addEnvelope.Plo@am__quote@
     569@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/boundTightening.Plo@am__quote@
    563570@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/checkNLP.Plo@am__quote@
    564571@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/constraint.Plo@am__quote@
     
    676683@am__fastdepCXX_FALSE@  $(LTCXXCOMPILE) -c -o $@ $<
    677684
     685CouenneThreeWayBranchObj.lo: branch/CouenneThreeWayBranchObj.cpp
     686@am__fastdepCXX_TRUE@   if $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT CouenneThreeWayBranchObj.lo -MD -MP -MF "$(DEPDIR)/CouenneThreeWayBranchObj.Tpo" -c -o CouenneThreeWayBranchObj.lo `test -f 'branch/CouenneThreeWayBranchObj.cpp' || echo '$(srcdir)/'`branch/CouenneThreeWayBranchObj.cpp; \
     687@am__fastdepCXX_TRUE@   then mv -f "$(DEPDIR)/CouenneThreeWayBranchObj.Tpo" "$(DEPDIR)/CouenneThreeWayBranchObj.Plo"; else rm -f "$(DEPDIR)/CouenneThreeWayBranchObj.Tpo"; exit 1; fi
     688@AMDEP_TRUE@@am__fastdepCXX_FALSE@      source='branch/CouenneThreeWayBranchObj.cpp' object='CouenneThreeWayBranchObj.lo' libtool=yes @AMDEPBACKSLASH@
     689@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     690@am__fastdepCXX_FALSE@  $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o CouenneThreeWayBranchObj.lo `test -f 'branch/CouenneThreeWayBranchObj.cpp' || echo '$(srcdir)/'`branch/CouenneThreeWayBranchObj.cpp
     691
    678692CouenneBranchingObject.lo: branch/CouenneBranchingObject.cpp
    679693@am__fastdepCXX_TRUE@   if $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT CouenneBranchingObject.lo -MD -MP -MF "$(DEPDIR)/CouenneBranchingObject.Tpo" -c -o CouenneBranchingObject.lo `test -f 'branch/CouenneBranchingObject.cpp' || echo '$(srcdir)/'`branch/CouenneBranchingObject.cpp; \
     
    10321046@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
    10331047@am__fastdepCXX_FALSE@  $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o generateCuts.lo `test -f 'convex/generateCuts.cpp' || echo '$(srcdir)/'`convex/generateCuts.cpp
     1048
     1049boundTightening.lo: convex/boundTightening.cpp
     1050@am__fastdepCXX_TRUE@   if $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT boundTightening.lo -MD -MP -MF "$(DEPDIR)/boundTightening.Tpo" -c -o boundTightening.lo `test -f 'convex/boundTightening.cpp' || echo '$(srcdir)/'`convex/boundTightening.cpp; \
     1051@am__fastdepCXX_TRUE@   then mv -f "$(DEPDIR)/boundTightening.Tpo" "$(DEPDIR)/boundTightening.Plo"; else rm -f "$(DEPDIR)/boundTightening.Tpo"; exit 1; fi
     1052@AMDEP_TRUE@@am__fastdepCXX_FALSE@      source='convex/boundTightening.cpp' object='boundTightening.lo' libtool=yes @AMDEPBACKSLASH@
     1053@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1054@am__fastdepCXX_FALSE@  $(LIBTOOL) --tag=CXX --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o boundTightening.lo `test -f 'convex/boundTightening.cpp' || echo '$(srcdir)/'`convex/boundTightening.cpp
    10341055
    10351056genColCuts.lo: convex/genColCuts.cpp
  • branches/Couenne/Couenne/src/branch/CouenneBranchingObject.cpp

    r515 r531  
    7878  //       1 if ">=" node
    7979
    80   int way = (!branchIndex_) ? firstBranch_ : !firstBranch_;
     80  int way = (!branchIndex_) ? firstBranch_ : !firstBranch_,
     81      ind = reference_ -> Index ();
     82  CouNumber l = solver -> getColLower () [ind],
     83            u = solver -> getColUpper () [ind];
    8184
    8285  if (way) {
    83 
    84     if (value_ < solver -> getColLower () [reference_ -> Index ()])
    85       printf ("Nonsense   up-branch: [ %f ,(%f)] -> %f\n",
    86               solver -> getColLower () [reference_ -> Index()],
    87               solver -> getColUpper () [reference_ -> Index()], value_);
    88     else
    89       if (value_ < solver -> getColLower () [reference_ -> Index ()] + COUENNE_EPS)
    90         printf ("## WEAK    up-branch: [ %f ,(%f)] -> %f\n",
    91                 solver -> getColLower () [reference_ -> Index()],
    92                 solver -> getColUpper () [reference_ -> Index()], value_);
     86    if      (value_ < l)             printf ("Nonsense up-branch: [ %f ,(%f)] -> %f\n", l,u,value_);
     87    else if (value_ < l+COUENNE_EPS) printf ("## WEAK  up-branch: [ %f ,(%f)] -> %f\n", l,u,value_);
    9388  } else {
    94 
    95     if (value_ > solver -> getColUpper () [reference_ -> Index()])
    96       printf ("Nonsense down-branch: [(%f), %f ] -> %f\n",
    97               solver -> getColLower () [reference_ -> Index()],
    98               solver -> getColUpper () [reference_ -> Index()], value_);
    99     else
    100       if (value_ > solver -> getColUpper () [reference_ -> Index()] + COUENNE_EPS)
    101         printf ("## WEAK  down-branch: [(%f), %f ] -> %f\n",
    102                 solver -> getColLower () [reference_ -> Index()],
    103                 solver -> getColUpper () [reference_ -> Index()], value_);
     89    if      (value_ > u)             printf ("Nonsense dn-branch: [(%f), %f ] -> %f\n", l,u,value_);
     90    else if (value_ > u+COUENNE_EPS) printf ("## WEAK  dn-branch: [(%f), %f ] -> %f\n", l,u,value_);
    10491  }
    10592
    106   if (0)
    107     printf (" [%.6e,%.6e]", solver -> getColLower () [reference_ -> Index ()],
    108                             solver -> getColUpper () [reference_ -> Index ()]);
     93  if (0) printf (" [%.6e,%.6e]", l, u);
    10994
    110   if (way) // ">=" node, set lower bound (round if this variable is integer)
    111     solver -> setColLower (reference_ -> Index (),
    112                            reference_ -> isInteger () ? ceil  (value_) : value_);
    113   else     // "<=" node, set upper bound (ditto)
    114     solver -> setColUpper (reference_ -> Index (),
    115                            reference_ -> isInteger () ? floor (value_) : value_);
     95  // ">=" if way=1, "<=" if way=0 set lower or upper bound (round if this variable is integer)
     96  if (way) solver -> setColLower (ind, reference_ -> isInteger () ? ceil  (value_) : value_);
     97  else     solver -> setColUpper (ind, reference_ -> isInteger () ? floor (value_) : value_);
     98
     99  // TODO: apply bound tightening
    116100
    117101  if (0) {
    118102
    119     printf (" --> [%.6e,%.6e]\n",
    120             solver -> getColLower () [reference_ -> Index ()],
    121             solver -> getColUpper () [reference_ -> Index ()]);
    122 
     103    printf (" --> [%.6e,%.6e]\n", l, u);
    123104    printf ("### Branch: x%d %c= %.12f\n",
    124105            reference_ -> Index (), way ? '>' : '<', value_);
  • branches/Couenne/Couenne/src/branch/CouenneBranchingObject.hpp

    r400 r531  
    2828
    2929  /// Constructor
    30   CouenneBranchingObject (expression *);
     30  CouenneBranchingObject (expression * = NULL);
     31
     32  /// Copy constructor
     33  CouenneBranchingObject (const CouenneBranchingObject &src):
     34    reference_ (src.reference_) {}
    3135
    3236  /// Cloning method
    3337  virtual OsiBranchingObject * clone() const
    34   {return new CouenneBranchingObject (reference_);}
     38  {return new CouenneBranchingObject (*this);}
    3539
    3640  /** \brief Execute the actions required to branch, as specified by the
  • branches/Couenne/Couenne/src/branch/CouenneObject.cpp

    r515 r531  
    1515#define WEI_RANK  0.
    1616#define WEI_MULT  0.
     17
    1718
    1819/// return difference between current value
  • branches/Couenne/Couenne/src/branch/CouenneObject.hpp

    r400 r531  
    1515#include <exprAux.h>
    1616
     17
     18/// OsiObject for auxiliary variables $w=f(x)$. Associated with a
     19/// multi-variate function $f(x)$ and a related infeasibility
     20/// $|w=f(x)|$, creates branches to help restoring feasibility
    1721
    1822class CouenneObject: public OsiObject {
  • branches/Couenne/Couenne/src/convex/generateCuts.cpp

    r525 r531  
    133133  }
    134134
    135   //  OsiBabSolver *auxinfo = dynamic_cast <OsiBabSolver *> (si.getAuxiliaryInfo ());
    136 
    137   int objInd = problem_ -> Obj (0) -> Body () -> Index ();
    138   if (objInd < 0) objInd = 0;
    139 
    140   if (babInfo && (babInfo -> babPtr ())) {
    141 
    142     CouNumber primal  = babInfo  -> babPtr () -> model (). getObjValue(),
    143               dual    = babInfo  -> babPtr () -> model (). getBestPossibleObjValue (),
    144               primal0 = problem_ -> Ub (objInd),
    145               dual0   = problem_ -> Lb (objInd);
    146 
    147     // Bonmin assumes minimization. Hence, primal (dual) is an UPPER
    148     // (LOWER) bound.
    149 
    150     if ((primal <   COUENNE_INFINITY - 1) && (primal < primal0)) { // update primal bound (MIP)
    151       problem_ -> Ub (objInd) = primal;
    152       chg_bds [objInd] = 1;
    153     }
    154 
    155     if ((dual   > - COUENNE_INFINITY + 1) && (dual   > dual0)) { // update dual bound
    156       problem_ -> Lb (objInd) = dual;
    157       chg_bds [objInd] = 1;
    158     }
    159   }
    160  
    161 
    162   //////////////////////// BOUND TIGHTENING ///////////////////////////////////
    163 
    164   int   ntightened = 0,
    165       nbwtightened = 0,
    166       niter = 0, *changed, nchanged;
    167 
    168   do {
    169 
    170     // propagate bounds to auxiliary variables
    171 
    172     ntightened = problem_ -> tightenBounds (chg_bds);
    173 
    174     // implied bounds. Call also at the beginning, as some common
    175     // expression may have non-propagated bounds
    176 
    177     if (ntightened >= 0) // if last call didn't signal infeasibility
    178       nbwtightened = problem_ -> impliedBounds (chg_bds);
    179 
    180     if ((ntightened < 0) || (nbwtightened < 0)) {
    181 
    182       // set infeasibility through a cut 1 <= x0 <= -1
    183 
    184       if (!firstcall_) {
    185 
    186         OsiColCut *infeascut = new OsiColCut;
    187 
    188         if (infeascut) {
    189           int i=0;
    190           double upper = -1., lower = +1.;
    191           infeascut -> setLbs (1, &i, &lower);
    192           infeascut -> setUbs (1, &i, &upper);
    193           cs.insert (infeascut);
    194           delete infeascut;
    195         }
    196       }
    197 
    198       if (babInfo)
    199         babInfo -> setInfeasibleNode (); // set infeasibility for NLP heuristic
    200 
    201       goto end_genCuts;
    202     }
    203   } while (ntightened || nbwtightened && (niter++ < 10));
    204   // need to check if EITHER procedures gave results, as expression
    205   // structure is not a tree any longer.
    206 
     135  int *changed, nchanged;
     136
     137  //////////////////////// Bound tightening ///////////////////////////////////////////
     138
     139  if (! boundTightening (si, cs, chg_bds, babInfo))
     140    goto end_genCuts;
    207141
    208142  //////////////////////// GENERATE CONVEXIFICATION CUTS //////////////////////////////
     
    249183    int ind_obj = problem_ -> Obj (0) -> Body () -> Index ();
    250184
    251     if (ind_obj >= 0)
     185    if (ind_obj >= 0) {
    252186      if (problem_ -> Obj (0) -> Sense () == MINIMIZE) {
    253187        if (problem_ -> Lb (ind_obj) < - LARGE_BOUND)
     
    257191        if (problem_ -> Ub (ind_obj) > LARGE_BOUND)
    258192          problem_ -> Ub (ind_obj) = LARGE_BOUND;
     193    }
    259194  }
    260195
    261196  // change tightened bounds through OsiCuts
    262 
    263197  if (nchanged)
    264198    genColCuts (si, cs, nchanged, changed);
    265199
    266200  // clean up
    267 
    268201  free (changed);
    269202
  • branches/Couenne/Couenne/src/convex/operators/conv-exprSinCos.cpp

    r521 r531  
    173173  else {
    174174
    175     // after  stationary point (i.e., _/ or ~\ ) for left bound,
     175    // after  stationary point (i.e., _/ or ~\ ) for left  bound,
    176176    // before stationary point (i.e., /~ or \_ ) for right bound
    177177 
     
    187187        if (left * (rx1 - tpt) < 0) {
    188188          if (!*s0)
    189             *s0 = cg -> addSegment (cs, wi, xi, x0, sin (rx0), x1, sin (rx1), -up) > 0;
    190         }
    191         else cg -> addSegment (cs, wi, xi, x0, sin (rx0), base + tpt, sin (tpt), -up);
     189            *s0 = cg -> addSegment (cs, wi, xi, x0, sin (rx0), x1,         sin (rx1), -up) > 0;
     190        } else    cg -> addSegment (cs, wi, xi, x0, sin (rx0), base + tpt, sin (tpt), -up);
    192191      }
    193192    } else {
  • branches/Couenne/Couenne/src/include/CouenneCutGenerator.h

    r497 r531  
    1414#include <OsiRowCut.hpp>
    1515#include <CouenneTypes.h>
     16#include "BonAuxInfos.hpp"
    1617
    1718#include <OsiSolverInterface.hpp>
     
    3132 protected:
    3233
    33   /// has generateCuts been called yet?
     34  /// has generateCuts been called before?
    3435  mutable bool firstcall_;
    3536
     
    174175  /// generate OsiColCuts for improved (implied and propagated) bounds
    175176  void genColCuts (const OsiSolverInterface &, OsiCuts &, int, int *) const;
     177
     178  /// tighten bounds using propagation, implied bounds and reduced costs
     179  bool boundTightening (const OsiSolverInterface &, OsiCuts &,
     180                        char *, Bonmin::BabInfo * = NULL) const;
    176181};
    177182
Note: See TracChangeset for help on using the changeset viewer.