Changeset 3029


Ignore:
Timestamp:
May 1, 2020 10:50:53 AM (2 months ago)
Author:
unxusr
Message:

C interface: reuse last feasible solution if still feasible

Location:
trunk/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/Cbc_C_Interface.cpp

    r3025 r3029  
    217217
    218218  enum OptimizationTask lastOptimization;
     219
     220  /* if number of columns didn't changed since previous
     221   * MIP optimization, try to reuse */
     222  int lastOptNCols;
     223  double *lastOptMIPSol;
    219224
    220225
     
    10441049 
    10451050  model->lastOptimization = ModelNotOptimized;
     1051  model->lastOptNCols = 0;
     1052  model->lastOptMIPSol = NULL;
    10461053
    10471054  model->icAppData = NULL;
     
    10791086    free(model->sosType);
    10801087  }
     1088
     1089  if (model->lastOptMIPSol)
     1090    delete[] model->lastOptMIPSol;
    10811091
    10821092#ifdef CBC_THREAD
     
    13671377Cbc_getNumElements(Cbc_Model *model)
    13681378{
     1379  int tmpNZCols = 0, tmpNZRows = 0;
     1380  if (model->cStart)
     1381    tmpNZCols = model->cStart[model->nCols];
     1382
     1383  if (model->rStart)
     1384    tmpNZRows = model->rStart[model->nRows];
     1385
    13691386  return model->solver_->getNumElements() +
    1370     model->cStart[model->nCols] +
    1371     model->rStart[model->nRows];
     1387    tmpNZCols + tmpNZRows;
    13721388}
    13731389
     
    17991815  OsiClpSolverInterface *linearProgram = dynamic_cast<OsiClpSolverInterface *>( model->solver_->clone() );
    18001816  model->lastOptimization = IntegerOptimization;
     1817  model->lastOptNCols = Cbc_getNumCols(model);
    18011818  CbcModel *cbcModel = model->cbcModel_ = new CbcModel( *linearProgram );
    18021819
     
    18801897    if ( model->dbl_param[DBL_PARAM_CUTOFF] != COIN_DBL_MAX )
    18811898      cbcModel->setCutoff( model->dbl_param[DBL_PARAM_CUTOFF] );
     1899
     1900    // trying to reuse integer solution found in previous optimization
     1901    if (model->lastOptNCols == model->solver_->getNumCols() && model->lastOptMIPSol) {
     1902      const double *x = model->lastOptMIPSol;
     1903      double maxViolRow, maxViolCol;
     1904      int idxRow, idxCol;
     1905      if (Cbc_checkFeasibility(model, x, &maxViolRow, &idxRow, &maxViolCol, &idxCol)) {
     1906        double obj = 0;
     1907        for ( int j=0 ; j<Cbc_getNumCols(model) ; ++j )
     1908          obj += Cbc_getColObj(model, j)*x[j];
     1909        cbcModel->setBestSolution(x, Cbc_getNumCols(model), obj);
     1910      }
     1911    } // try to reuse solution found in last optimization
    18821912
    18831913    std::vector< string > argv;
     
    19331963    CbcMain1( nargs, args, *model->cbcModel_, cbc_callb, cbcData );
    19341964
    1935     if (model->int_param[INT_PARAM_ROUND_INT_VARS]) {
    1936       model->cbcModel_->roundIntVars();
     1965    if (Cbc_numberSavedSolutions(model)) {
     1966      if (model->int_param[INT_PARAM_ROUND_INT_VARS]) {
     1967        model->cbcModel_->roundIntVars();
     1968      }
     1969
     1970      if (model->lastOptMIPSol && (model->lastOptNCols < Cbc_getNumCols(model))) {
     1971        delete[] model->lastOptMIPSol;
     1972        model->lastOptMIPSol = NULL;
     1973      }
     1974      if (!model->lastOptMIPSol)
     1975        model->lastOptMIPSol = new double[Cbc_getNumCols(model)];
     1976
     1977      memcpy(model->lastOptMIPSol, cbcModel->bestSolution(), sizeof(double)*Cbc_getNumCols(model) );
     1978      model->lastOptNCols = Cbc_getNumCols(model);
    19371979    }
    19381980
     
    23252367}
    23262368
     2369/** @brief Upper bound of ranged constraint
     2370  *
     2371  * @param model problem object
     2372  * @param row row index
     2373  * @return row upper bound
     2374  **/
     2375double
     2376Cbc_getRowUB(Cbc_Model *model, int row) {
     2377  if (row<model->solver_->getNumRows()) {
     2378    return model->solver_->getRowUpper()[row];
     2379  } else {
     2380    int nridx = row - model->solver_->getNumRows();
     2381    return model->rUB[nridx];
     2382  }
     2383}
     2384
     2385/** @brief Lower bound of ranged constraint
     2386  *
     2387  * @param model problem object
     2388  * @param row row index
     2389  * @return row lower bound
     2390  **/
     2391CBCSOLVERLIB_EXPORT double CBC_LINKAGE
     2392Cbc_getRowLB(Cbc_Model *model, int row) {
     2393  if (row<model->solver_->getNumRows()) {
     2394    return model->solver_->getRowLower()[row];
     2395  } else {
     2396    int nridx = row - model->solver_->getNumRows();
     2397    return model->rLB[nridx];
     2398  }
     2399}
     2400
     2401char Cbc_checkFeasibility(Cbc_Model *model, const double x[],
     2402    double *maxViolRow, int *rowIdx,
     2403    double *maxViolCol, int *colIdx) {
     2404  *maxViolRow = *maxViolCol = -1.0;
     2405  *rowIdx = *colIdx = -1;
     2406  const double primalTol = model->dbl_param[DBL_PARAM_PRIMAL_TOL];
     2407  const double intTol = model->dbl_param[DBL_PARAM_INT_TOL];
     2408
     2409  char feasible = 1;
     2410  int nRows = Cbc_getNumRows(model);
     2411  for ( int i=0 ; (i<nRows) ; ++i ) {
     2412    int nzRow = Cbc_getRowNz(model, i);
     2413    const int *cidx = Cbc_getRowIndices(model, i);
     2414    const double *coef = Cbc_getRowCoeffs(model, i);
     2415
     2416    double lhs = 0.0;
     2417    for ( int j=0 ; (j<nzRow) ; ++j ) {
     2418      int ic = cidx[j];
     2419      lhs += x[ic] * coef[j];
     2420    }
     2421
     2422    double rowUB = Cbc_getRowUB(model, i);
     2423    double rowLB = Cbc_getRowLB(model, i);
     2424
     2425    double viol = 0.0;
     2426   
     2427    if (lhs>rowUB) {
     2428      viol = lhs-rowUB;
     2429    } else {
     2430      if (lhs<rowLB) {
     2431        viol = rowLB-lhs;
     2432      }
     2433    }
     2434
     2435    if (viol>(*maxViolRow)) {
     2436      if (viol>primalTol)
     2437        feasible = 0;
     2438      *maxViolRow = viol;
     2439      *rowIdx = i;
     2440    }
     2441  } // all rows
     2442 
     2443  int nCols = Cbc_getNumCols(model);
     2444  for ( int j=0 ; (j<nCols) ; ++j ) {
     2445    const double clb = Cbc_getColLB(model, j);   
     2446    const double cub = Cbc_getColUB(model, j);
     2447 
     2448    double viol = 0.0;
     2449    if (x[j]>cub) {
     2450      viol = x[j] - cub;
     2451    } else {
     2452      if (x[j]<clb) {
     2453        viol = clb-x[j];
     2454      }
     2455    }
     2456    if (viol>primalTol)
     2457      feasible = 0;
     2458
     2459    if (Cbc_isInteger(model, j)) {
     2460      double vint = floor(x[j] + 0.5);
     2461      double intviol = fabs(x[j]-vint);
     2462      if (intviol > intTol)
     2463        feasible = 0;
     2464      viol = std::max(viol, intTol);
     2465    }
     2466
     2467    if ( viol > *maxViolCol ) {
     2468      *maxViolCol = viol;
     2469      *colIdx = j;
     2470    }
     2471  } // all columns
     2472
     2473  return feasible;
     2474}
    23272475
    23282476int CBC_LINKAGE
     
    27342882
    27352883  result->lastOptimization = model->lastOptimization;
     2884  result->lastOptNCols = model->lastOptNCols;
     2885  if (model->lastOptMIPSol) {
     2886    result->lastOptMIPSol = new double[model->lastOptNCols];
     2887    memcpy(result->lastOptMIPSol, model->lastOptMIPSol, sizeof(double)*model->lastOptNCols );
     2888  }
    27362889
    27372890  result->icAppData = model->icAppData;
  • trunk/src/Cbc_C_Interface.h

    r3017 r3029  
    587587Cbc_getRowRHS(Cbc_Model *model, int row);
    588588
     589/** @brief Upper bound of ranged constraint
     590  *
     591  * @param model problem object
     592  * @param row row index
     593  * @return row upper bound
     594  **/
     595CBCSOLVERLIB_EXPORT double CBC_LINKAGE
     596Cbc_getRowUB(Cbc_Model *model, int row);
     597
     598/** @brief Lower bound of ranged constraint
     599  *
     600  * @param model problem object
     601  * @param row row index
     602  * @return row lower bound
     603  **/
     604CBCSOLVERLIB_EXPORT double CBC_LINKAGE
     605Cbc_getRowLB(Cbc_Model *model, int row);
     606
     607
     608
     609
    589610/** @brief Sense of a row
    590611  *
     
    10051026Cbc_getColSolution(Cbc_Model *model);
    10061027
     1028
     1029/** @brief Checks feasibility of one solution
     1030  *
     1031  * @param model problem object
     1032  * @param x solution vector
     1033  * @param maxViolRow pointer to double where max violation in rows will be stored
     1034  * @param rowIdx pointer to integer where index of most violated row will be stored
     1035  * @param maxViolCol pointer to double where max violation in columns will be stored
     1036  * @param colIdx pointer to integer where index of most violated column will be stored
     1037  * @return 1 if feasible, 0 otherwise
     1038  **/
     1039CBCSOLVERLIB_EXPORT char CBC_LINKAGE
     1040Cbc_checkFeasibility(Cbc_Model *model, const double x[],
     1041    double *maxViolRow, int *rowIdx,
     1042    double *maxViolCol, int *colIdx);
     1043
    10071044/** @brief Best known bound on the optimal objective value
    10081045  *
Note: See TracChangeset for help on using the changeset viewer.