Changeset 577


Ignore:
Timestamp:
May 21, 2011 4:38:48 PM (9 years ago)
Author:
pbelotti
Message:

restoring FP for tests. Changing branching point on integer variables with integer value. Fixing large branching points for variables with large (upper/lower) bounds and large LP values. Added debug code to twoImplBounds for check against optimal solutions. Added fictitious objective function of 0 when none is defined. Redeclared size_t in invmap.cpp for compatibility with MSVS.

Location:
trunk/Couenne/src
Files:
15 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/branch/BranchCore.cpp

    r541 r577  
    6161              (brpt                               < problem_ -> bestSol () [indVar]))
    6262
    63             printf ("Branching EXCLUDES optimal solution\n");
     63            printf ("Branching rule EXCLUDES optimal solution\n");
    6464          else
    6565            for (int i=0; i<problem_ -> nVars (); i++)
     
    6868                  (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
    6969
    70                 {printf ("This node EXCLUDES optimal solution\n"); break;}
     70                {printf ("This node does not include optimal solution\n"); break;}
    7171        }
    7272      }
     
    133133      if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
    134134        if (brExclude)   printf (" (Branching EXCLUDES optimal solution)");
    135         if (nodeExclude) printf (" (This node EXCLUDES optimal solution)");
     135        if (nodeExclude) printf (" (This node does not contain optimal solution)");
    136136        printf ("\n");
    137137      }
     
    166166                (solver -> getColUpper () [i] < problem_ -> bestSol () [i] - COUENNE_EPS))
    167167
    168               {printf ("This node EXCLUDES optimal solution\n"); break;}
     168              {printf ("This node does not contain optimal solution\n"); break;}
    169169      }
    170170    }
     
    197197                (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
    198198
    199               {printf ("This node EXCLUDES optimal solution\n"); break;}
     199              {printf ("This node does not contain optimal solution\n"); break;}
    200200      }
    201201    }
  • trunk/Couenne/src/branch/CouenneBranchingObject.cpp

    r532 r577  
    162162
    163163  if (integer &&
    164       (::isInteger (brpt)) &&
    165       (way==!firstBranch_))
    166 
    167     brpt += 1.;
     164      ::isInteger (brpt)) {
     165
     166    // Careful here. We should look at all possible cases (l,u are
     167    // bounds, b is the branching point. l,u,b all integer):
     168    //
     169    // 1) l <  b <  u: first branch on b +/- 1 depending on branch
     170    // direction, right branch on b;
     171    //
     172    // 2) l <= b <  u: LEFT branch on b, RIGHT branch on b+1
     173    //
     174    // 3) l <  b <= u: LEFT branch on b-1, RIGHT branch on b
     175
     176    assert ((brpt - l > .5) ||
     177            (u - brpt > .5));
     178
     179    if ((brpt - l > .5) &&
     180        (u - brpt > .5)) { // brpt is integer interior point of [l,u]
     181
     182      if (firstBranch_) {
     183        if (!way) brpt -= 1.;
     184        else      brpt += 1.;
     185      }
     186     
     187    }
     188    else if (u - brpt > .5) {if  (way) brpt += 1.;}
     189    else if (brpt - l > .5) {if (!way) brpt -= 1.;}
     190  }
    168191
    169192  if (way) {
  • trunk/Couenne/src/branch/CouenneChooseStrong.cpp

    r575 r577  
    1919#include "CouenneRecordBestSol.hpp"
    2020
    21 #define TRACE_STRONG
     21//#define TRACE_STRONG
    2222
    2323using namespace Couenne;
  • trunk/Couenne/src/branch/CouenneVarObject.cpp

    r521 r577  
    8484    // cuts, for instance.
    8585
     86    // Actually, even smaller values (such as 1e10) can trigger bad BB
     87    // tree development (see wall in test files, not globallib/wall)
     88
     89#define LARGE_VALUE 1e8
     90
     91    if ((l < - LARGE_VALUE) &&
     92        (u >   LARGE_VALUE) &&
     93        (fabs (brpt) > LARGE_VALUE / 10))
     94      brpt = 0;
     95
    8696    if (l < - COUENNE_INFINITY) l = - 2 * fabs (brpt);
    8797    if (u >   COUENNE_INFINITY) u =   2 * fabs (brpt);
  • trunk/Couenne/src/convex/operators/conv-exprInv.cpp

    r490 r577  
    7777                            t_chg_bounds *chg, int wind,
    7878                            CouNumber lbw, CouNumber ubw) {
     79
     80  // TODO: if a<=w<=b, c<=x<=d, there is a diamond enclosing the whole
     81  // convexification
     82
    7983  CouNumber l, u;
    8084  argument_ -> getBounds (l, u);
  • trunk/Couenne/src/convex/operators/conv-exprPow.cpp

    r513 r577  
    230230      else if (l < q * u) { // lower x is before "turning point", add upper envelope
    231231        addPowEnvelope        (cg, cs, w_ind, x_ind, x, w, k, l, q*u, -sign);
    232         cg      -> addSegment     (cs, w_ind, x_ind, q*u, safe_pow (q*u,k), u, safe_pow (u,k), -sign);
     232        cg -> addSegment     (cs, w_ind, x_ind, q*u, safe_pow (q*u,k), u, safe_pow (u,k), -sign);
    233233      } else {
    234234        cg -> addSegment     (cs, w_ind, x_ind, l,   safe_pow (l,k),   u, safe_pow (u,k), -sign);
     
    262262        cg -> addSegment (cs, w_ind, arglist_ [0] -> Index (),
    263263                          l, safe_pow (l,k), u, safe_pow (u,k), +1);
     264
     265      // TODO: if a<=w<=b, c<=x<=d, there is a diamond enclosing the
     266      // whole convexification
     267
    264268      return;
    265269    }
  • trunk/Couenne/src/disjunctive/generateDisjCuts.cpp

    r501 r577  
    3939      (info.level > depthStopSeparate_))  // check if too deep for adding these cuts
    4040    return;
     41
     42  int nInitCuts = nrootcuts_;
    4143
    4244  if ((info.level <= 0) && !(info.inTree)) {
     
    291293    if ((info.level <= 0) && !(info.inTree))
    292294      jnlst_ -> Printf (J_ERROR, J_COUENNE,
    293                         "%d cuts (total)\n", CoinMax (0, nrootcuts_));
     295                        "%d cuts\n", CoinMax (0, nrootcuts_ - nInitCuts));
    294296    else if (deltaNcuts)
    295297      jnlst_ -> Printf (J_WARNING, J_COUENNE,
  • trunk/Couenne/src/heuristics/CouenneFPFindSolution.cpp

    r490 r577  
    3333  /// 6. random pertubation
    3434
    35 
    3635  // what order should we use? I suggest we use priorities, assigned
    3736  // at the beginning but changeable in the event of multiple failures
  • trunk/Couenne/src/heuristics/CouenneFeasPump.hpp

    r490 r577  
    111111
    112112    //
    113     // essential tools for the FP: a problem pointer and one for the
     113    // Essential tools for the FP: a problem pointer and one for the
    114114    // linearization cut generator
    115115    //
     
    122122
    123123    //
    124     // Persistent objects -- not necessary to identify FP, but it's
     124    // PERSISTENT OBJECTS -- not necessary to identify FP, but it's
    125125    // useful to keep them between calls
    126126    //
     
    139139    /// Pool of solutions
    140140    std::priority_queue <std::pair <CouNumber *, CouNumber> > pool_;
     141
     142    /// These methods can be used to solve the MILP, from the most
     143    /// expensive, exact method to a cheap, inexact one:
     144    ///
     145    /// 1. Solve a MILP relaxation with Manhattan distance as objective
     146    /// 2. Apply RENS on 1
     147    /// 3. Use Objective FP 2.0 for MILPs
     148    /// 4. round-and-propagate
     149    /// 5. choose from pool, see 4
     150    /// 6. random pertubation
     151
     152    enum Methods {SOLVE_MILP,       APPLY_RENS,  USE_FP_2, ROUND_N_PROPAGATE,
     153                  CHOOSE_FROM_POOL, RND_PERTURB, NUM_METHODS};
     154
     155    /// array of NUM_METHODS elements containing a number indicating
     156    /// the recent successes of the corresponding algorithm (see enum
     157    /// right above). The larger method_success_ [i], the more often
     158    /// the i-th method should be used.
     159
     160    int *method_success_;
    141161
    142162    //
     
    161181    /// maximum iterations per call
    162182    int maxIter_;
     183
    163184  };
    164185}
  • trunk/Couenne/src/main/BonCouenne.cpp

    r575 r577  
    7272  //saveSignal = signal (SIGINT, signal_handler);
    7373
    74     printf ("Couenne %s --  an Open-Source exact solver for Mixed Integer Nonlinear Optimization\n\
     74    printf ("Couenne %s --  an Open-Source solver for Mixed Integer Nonlinear Optimization\n\
    7575Mailing list: couenne@list.coin-or.org\n\
    7676Instructions: http://www.coin-or.org/Couenne\n",
  • trunk/Couenne/src/main/BonCouenneSetup.cpp

    r575 r577  
    536536  options () -> GetEnumValue ("feas_pump_heuristic", doHeuristic, "couenne.");
    537537
    538   if (false && doHeuristic) {
     538  if (doHeuristic) {
    539539
    540540    int numSolve;
  • trunk/Couenne/src/readnl/invmap.cpp

    r490 r577  
    1 /* $Id$ */
    2 /*
     1/* $Id$
     2 *
    33 * Name:    invmap.cpp
    44 * Author:  Pietro Belotti
     
    66 *          inversely map e->op fields into constant operators
    77 *
    8  * (C) Carnegie-Mellon University, 2006-09.
     8 * (C) Carnegie-Mellon University, 2006-11.
    99 * This file is licensed under the Eclipse Public License (EPL)
    1010 */
     
    3333  /* FIX! weak cast for 64 bit machines */
    3434
    35   register int f1 = Intcast (((AslCouPair *) p1) -> fp);
    36   register int f2 = Intcast (((AslCouPair *) p2) -> fp);
     35  register size_t f1 = Intcast (((AslCouPair *) p1) -> fp);
     36  register size_t f2 = Intcast (((AslCouPair *) p2) -> fp);
    3737
    3838  if      (f1 < f2) return -1;
     
    4949/* binary search to get operator number from its efunc2* (the type of e->op) */
    5050
    51 int getOperator (efunc *f) {
     51size_t getOperator (efunc *f) {
    5252
    5353  static char first_call = 1;
    5454  AslCouPair key, *res;
    5555
    56   /* FIX cast fo 64 bit machines */
     56  /* FIX cast for 64 bit machines */
    5757
    5858  if ((Intcast f <  N_OPS) &&
  • trunk/Couenne/src/readnl/readnl.cpp

    r490 r577  
    230230  // objective functions /////////////////////////////////////////////////////////////
    231231
     232  if (n_obj == 0) {
     233
     234    // strange, no objective function. Add one equal to zero
     235
     236    jnlst_ -> Printf (Ipopt::J_ERROR, J_COUENNE, "Couenne: warning, no objective function found\nAdded fictitious function f(x)=0\n");     
     237    addObjective (new exprConst (0.), "min");
     238  }
     239
    232240  for (int i = 0; i < n_obj; i++) {
    233241
  • trunk/Couenne/src/two_implied_bt/CouenneTwoImplied.hpp

    r501 r577  
    121121 
    122122     0) if  \f$ c_j = c_i \f$  then
    123      - compute VL =  \f$ \lim_{c_j \to \alpha} L_i (\alpha) \f$
     123     - compute \f$ VL = \lim_{c_j \to \alpha} L_i (\alpha) \f$
    124124     - if  \f$ =  +\infty  \f$ , infeasible
    125125     else compute derivative DL (should be   \f$ +\infty \f$  )
     
    137137     2) if  \f$ c_{j+1} = c_i \f$  then
    138138
    139      - compute VR =  \f$ \lim_{\alpha \to c_{j+1}} L_i (\alpha) \f$
     139     - compute \f$ VR = \lim_{\alpha \to c_{j+1}} L_i (\alpha) \f$
    140140
    141141     - if =  \f$ +\infty  \f$  , infeasible else compute derivative DR (should be
  • trunk/Couenne/src/two_implied_bt/TwoImpliedGenCuts.cpp

    r551 r577  
    698698      if (clb [i] > oldLB [i]) {
    699699
     700        if (problem_ -> bestSol () &&
     701            problem_ -> bestSol () [i] > oldLB [i] &&
     702            problem_ -> bestSol () [i] < clb   [i]) {
     703
     704          jnlst_ -> Printf (J_ERROR, J_COUENNE,
     705                            "Warning, twoImplBounds new LB cuts optimal solution: LB x_%d = %g --> %g, opt %g\n",
     706                            i, oldLB [i], clb [i], problem_ -> bestSol () [i]);
     707
     708        }
     709
    700710        //printf ("L %4d: %g -> %g\n", i, oldLB [i], clb [i]);
    701711        indLB [ntightenedL]   = i;
     
    704714
    705715      if (cub [i] < oldUB [i]) {
     716
     717        if (problem_ -> bestSol () &&
     718            problem_ -> bestSol () [i] > oldUB [i] &&
     719            problem_ -> bestSol () [i] < cub   [i]) {
     720
     721          jnlst_ -> Printf (J_ERROR, J_COUENNE,
     722                            "Warning, twoImplBounds new UB cuts optimal solution: UB x_%d = %g --> %g, opt %g\n",
     723                            i, oldUB [i], cub [i], problem_ -> bestSol () [i]);
     724
     725        }
    706726
    707727        //printf ("U %4d: %g -> %g\n", i, oldUB [i], cub [i]);
Note: See TracChangeset for help on using the changeset viewer.