Changeset 158


Ignore:
Timestamp:
Jun 24, 2009 10:36:37 AM (12 years ago)
Author:
pbelotti
Message:

added partial treatment of dual infeasibility (of continuous relaxation only...)

Location:
trunk/Couenne
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/configure.ac

    • Property svn:keywords set to Id
    r93 r158  
    33# This file is distributed under the Common Public License.
    44
    5 ## $Id: configure.ac 786 2006-06-01 04:10:46Z andreasw $
     5## $Id$
    66
    77# Author:  Andreas Waechter            IBM    2006-12-06
  • trunk/Couenne/src/convex/generateCuts.cpp

    r141 r158  
    1 /* $Id$ */
    2 /*
     1/* $Id$
     2 *
    33 * Name:    generateCuts.cpp
    44 * Author:  Pietro Belotti
     
    1616#include "CouenneSolverInterface.hpp"
    1717
     18#define Couenne_large_bound2 9.99e30
    1819
    1920// checks bad cuts against known optimum
    2021bool isOptimumCut (const CouNumber *opt, OsiCuts &cs, CouenneProblem *p);
    21 
    2222
    2323// set and lift bound for auxiliary variable associated with objective
     
    2828
    2929  // fictitious bound for initial unbounded lp relaxations
    30   const CouNumber large_bound =  9.999e12;
    31   const CouNumber large_tol = (large_bound / 1e6);
     30  const CouNumber large_tol = (Couenne_large_bound2 / 1e6);
    3231
    3332  // set trivial dual bound to objective function, if there is none
     
    4342  if (action)
    4443    //if (sense<0)
    45       {if (p -> Lb (ind_obj) < - large_bound) p -> Lb (ind_obj) = - large_bound;}
    46   //else         {if (p -> Ub (ind_obj) >   large_bound) p -> Ub (ind_obj) =   large_bound;}
     44      {if (p -> Lb (ind_obj) < - Couenne_large_bound2) p -> Lb (ind_obj) = - Couenne_large_bound2;}
     45  //else         {if (p -> Ub (ind_obj) >   large_bound2) p -> Ub (ind_obj) =   large_bound2;}
    4746  else
    48     //if (sense>0) {if (fabs (p->Ub(ind_obj)-large_bound)<large_tol) p->Ub(ind_obj)=COUENNE_INFINITY;}
     47    //if (sense>0) {if (fabs (p->Ub(ind_obj)-large_bound2)<large_tol) p->Ub(ind_obj)=COUENNE_INFINITY;}
    4948    //else         
    50       {if (fabs (p->Lb(ind_obj)+large_bound)<large_tol) p->Lb(ind_obj) =-COUENNE_INFINITY;}
     49      {if (fabs (p->Lb(ind_obj)+Couenne_large_bound2)<large_tol) p->Lb(ind_obj) =-COUENNE_INFINITY;}
    5150}
    5251
  • trunk/Couenne/src/expression/CouennePrecisions.hpp

    r141 r158  
    3737#define MAX_BOUND 1.e45
    3838
     39/// used to declare LP unbounded
     40const double Couenne_large_bound =  9.999e12;
     41
    3942#endif
  • trunk/Couenne/src/expression/operators/exprQuad.cpp

    r154 r158  
    469469
    470470
     471/// Redirect variables to proper variable vector
     472void exprQuad::realign (const CouenneProblem *p) {
     473
     474  for (sparseQ::iterator row = matrix_.begin (); row != matrix_.end (); ++row) {
     475
     476    exprVar * &vr = row -> first;
     477    int indVar;
     478
     479    // substitute variable representing this row with its newest version
     480
     481    if (((vr -> Type () == VAR) ||
     482         (vr -> Type () == AUX)) &&
     483        (vr -> Original () != p -> Var (indVar = vr -> Index ()))) {
     484
     485      expression *trash = vr;
     486      row -> first = p -> Var (indVar);
     487      delete trash;
     488    }
     489
     490    // substitute each variable of this row with its newest version
     491
     492    for (sparseQcol::iterator col = row -> second.begin (); col != row -> second.end (); ++col) {
     493
     494      exprVar * &vc = col -> first;
     495      int indVar;
     496
     497      // substitute variable representing this row with its newest version
     498
     499      if (((vc -> Type () == VAR) ||
     500           (vc -> Type () == AUX)) &&
     501          (vc -> Original () != p -> Var (indVar = vc -> Index ()))) {
     502
     503        expression *trash = vc;
     504        col -> first = p -> Var (indVar);
     505        delete trash;
     506      }
     507    }
     508  }
     509}
     510
     511
    471512/// compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
    472513void exprQuad::closestFeasible (expression *varind,
     
    474515                                CouNumber &left,
    475516                                CouNumber &right) const {
    476   assert (false);
     517
     518  fprintf (stderr, "exprQuad::closestFeasible() not available for VT\n");
     519  exit (-1);
    477520}
    478521
  • trunk/Couenne/src/expression/operators/exprQuad.hpp

    r154 r158  
    258258  virtual void replace (exprVar *x, exprVar *w);
    259259
     260  /// replace variable x with new (aux) w
     261  virtual void realign (const CouenneProblem *p);
     262
    260263  /// implied bound processing
    261264  virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *);
  • trunk/Couenne/src/problem/CouenneSolverInterface.cpp

    r154 r158  
    2222  knowInfeasible_(false),
    2323  knowOptimal_(false),
     24  knowDualInfeasible_(false),
    2425  doingResolve_ (true) {
    2526
     
    3637  knowInfeasible_       (src.knowInfeasible_),
    3738  knowOptimal_          (src.knowOptimal_),
     39  knowDualInfeasible_   (src.knowDualInfeasible_),
    3840  doingResolve_         (src.doingResolve_) {}
    3941
     
    5658            cutgen_ -> Problem () -> print ();*/
    5759
    58   knowInfeasible_ =
    59   knowOptimal_    = false;
     60  knowInfeasible_     =
     61  knowOptimal_        =
     62  knowDualInfeasible_ = false;
    6063
    6164  OsiClpSolverInterface::initialSolve ();
    6265  //writeLp ("initialLP");
     66
     67  if (getObjValue () <= - Couenne_large_bound)
     68    knowDualInfeasible_ = true;
    6369
    6470  // some originals may be unused due to their zero multiplicity (that
     
    95101}
    96102
     103bool CouenneSolverInterface::isProvenDualInfeasible() const {
     104  return knowDualInfeasible_ || OsiClpSolverInterface::isProvenDualInfeasible();
     105}
    97106
    98107/// Defined in Couenne/src/convex/generateCuts.cpp
     
    139148  }
    140149
    141   knowInfeasible_ = false;
    142   knowOptimal_    = false;
     150  knowInfeasible_     =
     151  knowOptimal_        =
     152  knowDualInfeasible_ = false;
    143153
    144154  const CoinWarmStart *ws = NULL;
     
    151161  // re-solve problem
    152162  OsiClpSolverInterface::resolve ();
     163
     164  if (getObjValue () <= - Couenne_large_bound)
     165    knowDualInfeasible_ = true;
    153166
    154167  CouNumber objval = getObjValue (),
     
    259272
    260273  //#if 0
    261   knowInfeasible_ = false;
    262   knowOptimal_ = false;
     274  knowInfeasible_     =
     275  knowOptimal_        =
     276  knowDualInfeasible_ = false;
    263277
    264278  /*
     
    345359  resolve();
    346360
     361  if (getObjValue () <= - Couenne_large_bound)
     362    knowDualInfeasible_ = true;
     363
    347364  // some originals may be unused due to their zero multiplicity (that
    348365  // happens when they are duplicates), restore their value
     
    355372  }
    356373
    357   if (isProvenPrimalInfeasible ()) knowInfeasible_ = true;
    358   if (isProvenOptimal ())          knowOptimal_    = true;
     374  if (isProvenPrimalInfeasible ()) knowInfeasible_     = true;
     375  if (isProvenOptimal          ()) knowOptimal_        = true;
     376  if (isProvenDualInfeasible   ()) knowDualInfeasible_ = true;
    359377
    360378  //printf("obj value = %e\n",getObjValue());
  • trunk/Couenne/src/problem/CouenneSolverInterface.hpp

    r154 r158  
    9292  {return doingResolve_;}
    9393
     94  /// is this problem unbounded?
     95  bool isProvenDualInfeasible () const;
     96  //{return knowDualInfeasible_;}
     97
    9498protected:
    9599
     
    105109  bool knowOptimal_;
    106110
     111  /// Flag indicating this problem's continuous relaxation is unbounded
     112  bool knowDualInfeasible_;
     113
    107114  /// flag to indicate this is an LP for the BB, not for (e.g.) strong
    108115  /// branching or OBBT
Note: See TracChangeset for help on using the changeset viewer.