Changeset 1063 for trunk


Ignore:
Timestamp:
Feb 2, 2014 2:00:59 PM (6 years ago)
Author:
pbelotti
Message:

matching objective variables with true reformulation variables. Setting correct bounds of distance LP

Location:
trunk/Couenne/src/heuristics
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/heuristics/CouenneFPSolveMILP.cpp

    r1062 r1063  
    4141
    4242/// create clone of MILP and add variables for special objective
    43 OsiSolverInterface *createCloneMILP (const CouenneFeasPump *fp, CbcModel *model, bool isMILP);
     43OsiSolverInterface *createCloneMILP (const CouenneFeasPump *fp, CbcModel *model, bool isMILP, int *match);
    4444
    4545
    4646/// modify MILP or LP to implement distance by adding extra rows (extra cols were already added by createCloneMILP)
    47 void addDistanceConstraints (const CouenneFeasPump *fp, OsiSolverInterface *lp, double *sol, bool isMILP);
     47void addDistanceConstraints (const CouenneFeasPump *fp, OsiSolverInterface *lp, double *sol, bool isMILP, int *match);
    4848
    4949
     
    9797                                    // necessary
    9898
     99  // match [i] contains the i-th extra variable associated with the
     100  // term in the L1 norm for x_i, and -1 otherwise.
     101
    99102  if (firstCall) {
    100103
     104    match_ = new int [problem_ -> nVars ()];
     105
     106    for (int i=problem_ -> nVars (); i--;)
     107      match_ [i] = -1;
     108
    101109    // create MILP
    102110
    103     milp_ = createCloneMILP (this, model_, true);
     111    milp_ = createCloneMILP (this, model_, true, match_);
     112
     113    // the bounds might have improved because of FBBT. Unless a new
     114    // MINLP solution was found (unlikely ...), this should be done only
     115    // at the first call to the FP
     116
     117    for (int i=problem_ -> nVars (); i--;) {
     118      milp_ -> setColLower (i, problem_ -> Lb (i));
     119      milp_ -> setColUpper (i, problem_ -> Ub (i));
     120    }
    104121
    105122    // Post-processing LP: persistent if FP_DIST_POST, created on the
     
    111128
    112129    if ((compDistInt_ == FP_DIST_POST) && !postlp_)
    113       postlp_ = createCloneMILP (this, model_, false);
    114 
    115     // the bounds might have improved because of FBBT. Unless a new
    116     // MINLP solution was found (unlikely ...), this should be done only
    117     // at the first call to the FP
    118 
    119     milp_ -> setColLower (problem_ -> Lb ());
    120     milp_ -> setColUpper (problem_ -> Ub ());
     130      postlp_ = createCloneMILP (this, model_, false, NULL);
    121131  }
     132
     133#if 0
     134  printf ("======================================================================================================================================\n");
     135  for (int i=0,j; i<problem_->nVars (); ++i)
     136    if (match_ [i] >= 0) {
     137      printf ("(%d,%d)", i, match_ [i]);
     138      if ((++j) % 6 == 0) printf ("\n");
     139    }
     140  printf ("======================================================================================================================================\n");
     141#endif
    122142
    123143  int nInitRows = milp_ -> getNumRows ();
     
    137157
    138158  // create constraints to define l_1 distance objective function
    139   addDistanceConstraints (this, milp_, nlpSolExp, true);
     159  addDistanceConstraints (this, milp_, nlpSolExp, true, match_);
     160
     161  //milp_ -> writeLp ("afterAdd");
    140162
    141163  delete [] nlpSolExp;
     
    156178    sprintf (filename, "fp-milp%04d", cntr++);
    157179    milp_ -> writeLp (filename);
     180    printf ("saving FP_MILP %d\n", cntr);
    158181  }
    159182
     
    180203    }
    181204
    182     printf ("FP: after MILP, distance %g, %d nonintegers\n", sqrt (dist), nNonint);
     205    problem_ -> Jnlst () -> Printf ("FP: after MILP, distance %g, %d nonintegers\n", sqrt (dist), nNonint);
    183206  }
    184207
     
    226249
    227250        if (!postlp_)
    228           postlp_ = createCloneMILP (this, model_, false);
     251          postlp_ = createCloneMILP (this, model_, false, NULL);
    229252
    230253        int nvars = postlp_ -> getNumCols ();
     
    252275
    253276        int nInitRowsLP  = postlp_ -> getNumRows ();
    254         addDistanceConstraints (this, postlp_, iSol, false);
     277        addDistanceConstraints (this, postlp_, iSol, false, match_);
    255278        int nFinalRowsLP = postlp_ -> getNumRows ();
    256279
  • trunk/Couenne/src/heuristics/CouenneFPcreateMILP.cpp

    r1062 r1063  
    3333
    3434/// create clone of MILP and add variables for special objective
    35 OsiSolverInterface *createCloneMILP (const CouenneFeasPump *fp, CbcModel *model, bool isMILP) {
     35OsiSolverInterface *createCloneMILP (const CouenneFeasPump *fp, CbcModel *model, bool isMILP, int *match) {
    3636
    3737  OsiSolverInterface *lp = model -> solver () -> clone ();
     
    5353    // TODO: should this really happen? I bet no
    5454
    55     //if (fp -> Problem () -> Var (j) -> Multiplicity () <= 0)
    56     //continue;
     55    if (fp -> Problem () -> Var (j) -> Multiplicity () <= 0)
     56      continue;
    5757
    5858    bool intVar = lp -> isInteger (j);
     
    6060    if ((isMILP && (intVar || (fp -> compDistInt () == CouenneFeasPump::FP_DIST_ALL)))
    6161        ||
    62         (!isMILP && !intVar))
     62        (!isMILP && !intVar)) {
     63
    6364      // (empty) coeff col vector, lb = 0, ub = inf, obj coeff
    6465      lp -> addCol (vec, 0., COIN_DBL_MAX, 1.);
     66
     67      if (match)
     68        match [j] = lp -> getNumCols () - 1;
     69    }
    6570  }
    6671
     
    7984
    8085/// modify MILP or LP to implement distance by adding extra rows (extra cols were already added by createCloneMILP)
    81 void addDistanceConstraints (const CouenneFeasPump *fp, OsiSolverInterface *lp, double *sol, bool isMILP) {
     86void addDistanceConstraints (const CouenneFeasPump *fp, OsiSolverInterface *lp, double *sol, bool isMILP, int *match) {
    8287
    8388  // Construct an (empty) Hessian. It will be modified later, but
     
    148153  for (int i = 0, j = n, k = n; k--; ++i) {
    149154
     155    if (match && match [i] < 0)
     156      continue;
     157
    150158    if (fp -> Problem () -> Var (i) -> Multiplicity () <= 0)
    151159      continue;
     
    170178      // right-hand side equals <P^i,x^0>
    171179      double PiX0 = sparseDotProduct (vec, x0);
     180
     181      assert (!match || match [i] >= 0);
     182
     183      //printf ("adding row %d with %d elements\n", j, vec.getNumElements());
    172184
    173185      // j is the index of the j-th extra variable z_j, used for z_j >=  P (x - x0)  ===> z_j - Px >= - Px_0 ==> -z_j + Px <= Px_0
  • trunk/Couenne/src/heuristics/CouenneFeasPump.cpp

    r1062 r1063  
    4242
    4343  double time0 = CoinCpuTime();
     44
     45  match_ = NULL;
    4446
    4547  if ((nCalls_ == 0) ||                                   // check upper limit on number of runs
     
    917919  milp_ = postlp_ = NULL;
    918920
     921  if (match_) {
     922    delete [] match_;
     923    match_ = NULL;
     924  }
     925
    919926  problem_ -> Jnlst () -> Printf
    920927    (J_WARNING, J_NLPHEURISTIC, "FP: done ===================\n");
  • trunk/Couenne/src/heuristics/CouenneFeasPump.hpp

    r1058 r1063  
    211211    std::set <CouenneFPsolution, compareSol> tabuPool_;
    212212
     213    /// matching between reformulation's variables and L-1 norm variables
     214    int *match_;
     215
    213216    //
    214217    // PARAMETERS
Note: See TracChangeset for help on using the changeset viewer.