Changeset 592


Ignore:
Timestamp:
Jun 1, 2011 6:40:25 AM (9 years ago)
Author:
pbelotti
Message:

fixing generation/deletion of cuts in FP. Possibly fixing conditional jump in RecordBestSol?.

Location:
trunk/Couenne/src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/convex/genRowCuts.cpp

    r490 r592  
    5353          (var -> Type () == AUX)) {
    5454
    55         var -> generateCuts (/*si,*/ cs, this, chg);
     55        var -> generateCuts (cs, this, chg);
    5656      }
    5757    }
    5858  else { // chg_bds contains the indices of the variables whose bounds
    5959         // have changed (a -1 follows the last element)
    60 
    61     /*
    62     printf ("# # # # pass = %d, have_NLP = %d. nchanged = %d: {", info.pass, have_NLP, nchanged);
    63 
    64     if (changed)
    65       for (int i=0; (i<nchanged) && (changed [i] >= 0); i++)
    66         printf ("%d ", changed [i]);
    67 
    68     printf ("}\n");
    69     */
    7060
    7161    for (int i = 0, j = problem_ -> nVars (); j--; i++) {
     
    10191          break;
    10292
    103         var -> generateCuts (/*si,*/ cs, this, chg);
     93        var -> generateCuts (cs, this, chg);
    10494      }
    10595    }
  • trunk/Couenne/src/expression/exprAux.cpp

    r564 r592  
    191191// generate cuts for expression associated with this auxiliary
    192192
    193 void exprAux::generateCuts (//const OsiSolverInterface &si,
    194                             OsiCuts &cs, const CouenneCutGenerator *cg,
     193void exprAux::generateCuts (OsiCuts &cs, const CouenneCutGenerator *cg,
    195194                            t_chg_bounds *chg, int,
    196195                            CouNumber, CouNumber) {
     
    256255        image_ -> print (std::cout);
    257256
    258         printf (" [%.7e,%.7e] <--- ",
     257        printf (" %g [%g,%g]. ",
     258                domain_ -> x  (varIndex_),
    259259                domain_ -> lb (varIndex_),
    260260                domain_ -> ub (varIndex_));
     
    263263        if ((image_ -> Argument ()) &&
    264264            ((index = image_ -> Argument () -> Index ()) >= 0))
    265           printf ("[%.7e,%.7e] ",
     265          printf ("%g [%g,%g] ",
     266                  domain_ -> x  (index),
    266267                  domain_ -> lb (index),
    267268                  domain_ -> ub (index));
     
    269270          for (int i=0; i<image_ -> nArgs (); i++)
    270271            if ((index = image_ -> ArgList () [i] -> Index ()) >= 0)
    271               printf ("[%.7e,%.7e] ",
     272              printf ("%g [%g,%g] ",
     273                      domain_ -> x  (index),
    272274                      domain_ -> lb (index),
    273275                      domain_ -> ub (index));
  • trunk/Couenne/src/heuristics/CouenneFPFindSolution.cpp

    r577 r592  
    2424
    2525  /// as found on the notes, these methods can be used, from the most
    26   /// expensive, exact method to a cheap, inexact one:
     26  /// expensive and accurate (exact) method to a cheap, inexact one:
    2727  ///
    2828  /// 1. Solve a MILP relaxation with Manhattan distance as objective
    29   /// 2. Apply RENS on 1
     29  /// 2. Apply RENS to 1
    3030  /// 3. Use Objective FP 2.0 for MILPs
    3131  /// 4. round-and-propagate
    3232  /// 5. choose from pool, see 4
    33   /// 6. random pertubation
     33  /// 6. random perturbation
    3434
    35   // what order should we use? I suggest we use priorities, assigned
     35  // What order should we use? I suggest we use priorities, assigned
    3636  // at the beginning but changeable in the event of multiple failures
    3737  // (or successes) of a given method.
     
    5050  // 4) if H consecutive failutes, ++p[i]
    5151
    52   /// save milp for debugging purposes
    53   milp_ -> writeLp ("fp-milp"); // !!
    54 
    5552  /// solve MILP
    5653  milp_ -> branchAndBound ();
  • trunk/Couenne/src/heuristics/CouenneFPSolveMILP.cpp

    r590 r592  
    6565  // P = beta I + (1-beta) (H + alpha g g')
    6666  //
    67   // so that we can balance the hessian and the distance.
     67  // so that we can balance the Hessian and the distance.
    6868
    6969  CoinPackedMatrix P;
    7070
    71   bool firstCall = false; // true if this is the first call to
    72                           // solveMILP; initialization will be
    73                           // necessary
     71  bool firstCall = (milp_ != NULL); // true if this is the first call to
     72                                    // solveMILP; initialization will be
     73                                    // necessary
    7474
    7575  if (!milp_) {
    76 
    77     firstCall = true;
    7876
    7977    milp_ = model_ -> solver () -> clone ();
     
    130128
    131129    milp_ -> setObjCoeff (problem_ -> Obj (0) -> Body () -> Index (), 0.);
    132 
    133   } else {
    134 
    135     // delete last rows and add them from scratch (common block below)
    136 
    137     int
    138        nDeleted = compDistInt_ ? milp_ -> getNumIntegers () :
    139                                  problem_ -> nVars (),
    140       *deleted  = new int [2*nDeleted],
    141        nCurRow  = milp_ -> getNumRows ();
    142 
    143     for (int i=2*nDeleted; i--;)
    144       deleted [i] = --nCurRow;
    145 
    146     milp_ -> deleteRows (nDeleted, deleted);
    147 
    148     printf ("FP: deleting last lines\n");
    149     milp_ -> writeLp ("fp-milp-del"); // !!
    150 
    151     delete [] deleted;
    152130  }
    153131
    154   printf ("FP: add MILP ineq\n");
    155   milp_ -> writeLp ("fp-milp0");
    156 
    157132  // Add 2q inequalities
     133
     134  int nInitRows = milp_ -> getNumRows ();
     135
     136  CouNumber * nlpSolExp;
     137
     138  if (nSol0) {
     139
     140    nlpSolExp = new CouNumber [problem_ -> nVars ()];
     141
     142    CoinCopyN (nSol0, problem_ -> nOrigVars (), nlpSolExp);
     143    problem_ -> getAuxs (nlpSolExp);
     144
     145  } else
     146    nlpSolExp = CoinCopyOfArray (milp_ -> getColSolution (),
     147                                 problem_ -> nVars ());
     148
     149  CoinPackedVector x0 (problem_ -> nVars (), nlpSolExp);
    158150
    159151  for (int i=0, j=problem_ -> nVars (), k = problem_ -> nVars (); k--; i++)
     
    170162      }
    171163
    172       CoinPackedVector x0 (problem_ -> nVars (), milp_ -> getColSolution ());
    173 
    174164      // right-hand side equals <P^i,x^0>
    175165      double PiX0 = sparseDotProduct (vec, x0);
     
    180170      ++j; // index of variable within problem (plus nVars_)
    181171    }
     172
     173  int nFinalRows = milp_ -> getNumRows ();
    182174
    183175  // The MILP is complete. We have several ways of solving it, or
    184176  // better, to find feasible solutions to it. We have to interface
    185177  // with each of them once at the very beginning, and later we loop
    186   // through them in order to find a feasible solution
     178  // through them in order to find a feasible solution.
    187179
    188180  if (firstCall)
     
    190182
    191183  findSolution ();
    192 
    193184  iSol = CoinCopyOfArray (milp_ -> getColSolution (),
    194185                          problem_ -> nVars ());
    195186
     187  // delete last rows and add them from scratch (common block below)
     188
     189  int
     190     nDeleted = nFinalRows - nInitRows,
     191    *deleted  = new int [nDeleted],
     192     nCurRow  = nInitRows;
     193
     194  for (int i = nDeleted; i--;)
     195    deleted [i] = nCurRow++;
     196
     197  milp_ -> deleteRows (nDeleted, deleted);
     198
     199  delete [] deleted;
     200
    196201  return milp_ -> getObjValue ();
    197202}
  • trunk/Couenne/src/heuristics/CouenneFeasPump.cpp

    r590 r592  
    2424using namespace Couenne;
    2525
     26/// When the current IP (non-NLP) point is not MINLP feasible, linear
     27/// cuts are added and the IP is re-solved not more than this times
     28const int numConsCutPasses = 5;
     29
    2630// Solve
    2731int CouenneFeasPump::solution (double &objVal, double *newSolution) {
     
    8286  expression *origObj = problem_ -> Obj (0) -> Body ();
    8387
    84   int objInd = problem_ -> Obj (0) -> Body () -> Index ();
     88  int
     89    objInd = problem_ -> Obj (0) -> Body () -> Index (),
     90    nSep;
    8591
    8692  do {
    8793
    88     printf ("FP: main loop\n");
     94    printf ("FP: main loop ------------ \n");
     95
     96    CouNumber curcutoff = problem_ -> getCutOff ();
    8997
    9098    // INTEGER PART /////////////////////////////////////////////////////////
     
    93101    // l-1 distance from. If nSol==NULL, the MILP is created using the
    94102    // original milp's LP solution.
     103
    95104    double z = solveMILP (nSol, iSol);
    96105
     
    110119    if (isChecked) {
    111120
    112       printf ("FP: solution found is MINLP-feasible! Comparing now %g with cutoff %g\n",
    113               z, problem_ -> getCutOff ());
    114 
    115       // solution is MINLP feasible!
    116       // Save
     121      printf ("FP: MINLP-feasible solution (%g vs. %g)\n",
     122              z, curcutoff);
     123
     124      // solution is MINLP feasible! Save it.
    117125
    118126      if (z < problem_ -> getCutOff ()) {
    119 
    120         printf ("FP: (and it is better than the cutoff)\n");
    121127
    122128        retval = 1;
     
    165171    } else {
    166172
    167       printf ("FP: MINLP-infeasible, try some cuts\n");
    168 
    169173      // solution non MINLP feasible, it might get cut by
    170174      // linearization cuts. If so, add a round of cuts and repeat.
    171175
    172176      OsiCuts cs;
     177
     178      problem_ -> domain () -> push (milp_);
    173179      // remaining three arguments at NULL by default
    174180      couenneCG_ -> genRowCuts (*milp_, cs, 0, NULL);
     181      problem_ -> domain () -> pop ();
    175182
    176183      if (cs.sizeRowCuts ()) {
    177184
    178         printf ("FP: found cuts\n");
    179    
    180185        // the (integer, NLP infeasible) solution could be separated
    181186
    182187        milp_ -> applyCuts (cs);
    183188
    184         if (milpCuttingPlane_)
    185           continue; // found linearization cut, now re-solve MILP (not quite a FP)
     189        // found linearization cut, now re-solve MILP (not quite a FP)
     190        if (milpCuttingPlane_ && (nSep++ < numConsCutPasses))
     191          continue;
    186192      }
    187193    }
     194
     195    nSep = 0;
    188196
    189197    // NONLINEAR PART ///////////////////////////////////////////////////////
     
    342350
    343351  delete [] iSol;
    344   delete [] nSol; // best is either iSol or nSol, so don't delete [] it
     352  delete [] nSol;
    345353
    346354  // release bounding box
    347355  problem_ -> domain () -> pop (); // pushed in first call to solveMILP
    348356
    349   // milp is deleted at every call since it changes not only in terms
    350   // of variable bounds but also in terms of linearization cuts added
     357  // deleted at every call from Cbc, since it changes not only in
     358  // terms of variable bounds but also in of linearization cuts added
     359
    351360  delete milp_;
     361  milp_ = NULL;
    352362
    353363  return retval;
  • trunk/Couenne/src/heuristics/CouenneFeasPumpConstructors.cpp

    r490 r592  
    4949                                  Ipopt::SmartPtr<Ipopt::OptionsList> options):
    5050
    51   CbcHeuristic         (), //(model),
    52   problem_             (couenne -> clone ()),
     51  CbcHeuristic         (),
     52  problem_             (couenne),
    5353  couenneCG_           (cg),
    5454  nlp_                 (NULL),
     
    7979
    8080  CbcHeuristic         (other),
    81   problem_             (other. problem_ -> clone ()),
     81  problem_             (other. problem_),
    8282  couenneCG_           (other. couenneCG_),
    8383  nlp_                 (other. nlp_),
     
    104104    CbcHeuristic::operator= (rhs);
    105105
    106     problem_             = rhs. problem_ -> clone ();
     106    problem_             = rhs. problem_;
    107107    couenneCG_           = rhs. couenneCG_;
    108108    nlp_                 = rhs. nlp_;
     
    122122
    123123// Destructor ///////////////////////////////////////////////////
    124 CouenneFeasPump::~CouenneFeasPump () {
    125 
    126   if (problem_)
    127     delete problem_;
    128 }
     124CouenneFeasPump::~CouenneFeasPump () {}
    129125
    130126
  • trunk/Couenne/src/problem/CouenneRecordBestSol.cpp

    r575 r592  
    2121
    2222/*************************************************************/
    23   /** Default constructor. */
     23/** Default constructor. */
    2424CouenneRecordBestSol::CouenneRecordBestSol() {
    2525
     
    7777  }
    7878
    79   if(modSol != NULL) {
     79  if (other.modSol != NULL) {
    8080    modSol = new double[other.cardSol];
    8181  }
  • trunk/Couenne/src/problem/checkNLP.cpp

    r576 r592  
    55 * Purpose: check NLP feasibility of incumbent integer solution
    66 *
    7  * (C) Carnegie-Mellon University, 2006-10.
     7 * (C) Carnegie-Mellon University, 2006-11.
    88 * This file is licensed under the Eclipse Public License (EPL)
    99 */
     
    5555                      i, val, domain_.lb (i), domain_.ub (i));
    5656
    57       Jnlst () -> Printf (Ipopt::J_MOREVECTOR, J_PROBLEM, "Done: (0)\n");
     57      Jnlst () -> Printf (Ipopt::J_ALL, J_PROBLEM, "Done: (0)\n");
    5858
    5959      return false;
     
    275275  domain_.pop ();
    276276
    277   Jnlst () -> Printf (Ipopt::J_MOREVECTOR, J_PROBLEM, "Done: %d\n", retval);
     277  Jnlst () -> Printf (Ipopt::J_ALL, J_PROBLEM, "Done: %d\n", retval);
    278278
    279279  return retval;
Note: See TracChangeset for help on using the changeset viewer.