Changeset 4094

Show
Ignore:
Timestamp:
10/09/06 09:35:13 (2 years ago)
Author:
caphill
Message:

Add a new randomized rounding heuristic and fix one major problem with
the new Osi cplex interface. Specifically:

— When we moved to the new version of coin, we were able to compile
cplex-related Osi code by switching to using getLpPtr() instead of a previous
private method. I changed all the many calls to this method to use the
optional argument to prevent freeing of cached objects within the
OsiCpxSolverInterface? object. Without it, the solver interface was freeing
object out from under PICO pointers, causing seg faults and general mayhem.

— More efficient default implementation of
PicoLPInterface::getRowSense(char *, int, int)
The new version only gets a pointer to the row sense vector
once and doesn't go through unnecessary conversions to and from
PicoConstraintSense?.

— Added a new method bool PicoLPInterface::checkFeasibility(DoubleVector? &).
This uses Osi matrix-vector multiplication methods to check the feasibility
of a solution. We currently use this in the randomized rounding heuristic,
but we should be able to use it (at least sometimes) in the solution
recheck in updateIncumbent (avoiding LP calls which could be slower and
might wreck LP solver state). This method returns true of all the
constraints are met within constraintFeasTolerance (default 1e-7)

— A new randomized rounding heuristic for general MIPs. We now have
a new parameter PICOMIPHeuristics, which when false, disables all
PICO built-in general heuristics. For now, this is randomized rounding (RR)
and the Eckstein-Nediak heuristic. It will (soon) include the decomposition
heuristic and things like feasibility pumps. The new parameter to control
only the Eckstein-Nediak heuristic is called bhhMIPHeuristic (enabled if
true). I used the prefix from the other parameters for this heuristic.
The randomized rounding heuristic uses the LP relaxation. For a binary
variable with fractional value f, it rounds to 1 with probability f and
to 0 with probability 1-f. For a general integer variable with non-integer
fractional value v.f (f is the fractional part), round to v+1 with probability
f and to v with probability 1-f. If there are continuous variables,
it sets them with the LP if possible after all integer variables are set.
Setting the continous variables is a virtual method, since I expect
customized solvers may know better ways to set them. Once we make solutions
more abstract, we will likely change this to allow not filling in continous
variables if we don't need to and just implementing a virtual feasibility
check. The randomized rounding heuristic is run on nodes up to depth
maxRRDepth (default 1, 0 disables) and each call runs numRRTrialsPerCall
trials (default 1). In general if there are a small number k of real
constraints (like with water sensor placement problems), you would expect
a feasible solution in 2k flips, provided the constraints are all
inequalities (chances of satisfying an equality this way are vanishingly
small). In particular, if all settings of integer variables that obey the
bounds are feasible, this will give an immediate incumbent (and pass the
ho ho test). Right now, the heuristic is called once after bounding and once
after separation and we run each time if the level is OK.

( Links to Acro-related mail archives at http://software.sandia.gov/Acro/ )

Location:
pico/trunk/src
Files:
8 modified

Legend:

Unmodified
Added
Removed

  • pico/trunk/src/lp/pico/PicoCpxLP.h

    r4085 r4094  
    6161{ 
    6262  //int stat = CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), getMutableLpPtr() ); 
    63 int stat = CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     63int stat = CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    6464#if (CPX_VERSION >= 800) 
    6565return stat == CPXMIP_TIME_LIM_INFEAS || stat == CPXMIP_TIME_LIM_FEAS; 
    … …  
    7373bool PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>::isProvenPrimalUnbounded() const 
    7474{ 
    75 int stat = CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     75int stat = CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    7676#if (CPX_VERSION >= 800) 
    7777return stat == CPX_STAT_UNBOUNDED; 
    7878#else 
    79 int method = CPXgetmethod(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     79int method = CPXgetmethod(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    8080// stat for version < 8 is relative to solver. If running dual simplex and stat is 
    8181// infeasible, we do not necessarily know the primal is unbounded (could be infeasible). 
    … …  
    9393int stat =  
    9494#endif 
    95 CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     95CPXgetstat( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    9696#if (CPX_VERSION >= 800) 
    9797return false; 
    9898#else 
    99 int method = CPXgetmethod(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     99int method = CPXgetmethod(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    100100// stat for version < 8 is relative to solver. If running primal simplex and stat is 
    101101// infeasible, we do not necessarily know the dual is unbounded (could be infeasible). 
    … …  
    109109{ 
    110110double ans; 
    111 CPXgetlb(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&ans,whichVariable,whichVariable); 
     111CPXgetlb(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&ans,whichVariable,whichVariable); 
    112112return ans; 
    113113} 
    … …  
    118118{ 
    119119double ans; 
    120 CPXgetub(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&ans,whichVariable,whichVariable); 
     120CPXgetub(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&ans,whichVariable,whichVariable); 
    121121return ans; 
    122122} 
    … …  
    127127{ 
    128128char sense; 
    129 CPXgetsense(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&sense,whichVariable,whichVariable); 
     129CPXgetsense(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&sense,whichVariable,whichVariable); 
    130130double rhs; 
    131 CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&rhs,whichVariable,whichVariable); 
     131CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&rhs,whichVariable,whichVariable); 
    132132double range; 
    133 CPXgetrngval(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&range,whichVariable,whichVariable); 
     133CPXgetrngval(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&range,whichVariable,whichVariable); 
    134134double lower, upper; 
    135135convertSenseToBound(sense, rhs, range, lower, upper); 
    … …  
    142142{ 
    143143char sense; 
    144 CPXgetsense(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&sense,whichVariable,whichVariable); 
     144CPXgetsense(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&sense,whichVariable,whichVariable); 
    145145double rhs; 
    146 CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&rhs,whichVariable,whichVariable); 
     146CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&rhs,whichVariable,whichVariable); 
    147147double range; 
    148 CPXgetrngval(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&range,whichVariable,whichVariable); 
     148CPXgetrngval(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&range,whichVariable,whichVariable); 
    149149double lower, upper; 
    150150convertSenseToBound(sense, rhs, range, lower, upper); 
    … …  
    157157{ 
    158158double rhs; 
    159 CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&rhs,whichConstraint,whichConstraint); 
     159CPXgetrhs(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&rhs,whichConstraint,whichConstraint); 
    160160return rhs; 
    161161} 
    162162 
    163  
    164163template<> 
    165164PicoLPInterface::constraintSense PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>::getRowSense(int whichConstraint) const 
    166165{ 
    167166char csense; 
    168 CPXgetsense( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), &csense, whichConstraint, whichConstraint); 
     167CPXgetsense( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), &csense, whichConstraint, whichConstraint); 
    169168 
    170169PicoLPInterface::constraintSense sense = notRestricted; 
    … …  
    186185{ 
    187186double ans; 
    188 int err = CPXgetobj(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&ans,whichVariable,whichVariable); 
     187int err = CPXgetobj(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&ans,whichVariable,whichVariable); 
    189188checkCPXerror( err, "CPXgetobj", "getObjCoefficient" ); 
    190189return ans; 
    … …  
    196195{ 
    197196double ans = 0.0; 
    198 int probType = CPXgetprobtype(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr()); 
     197int probType = CPXgetprobtype(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL)); 
    199198#if (CPX_VERSION >= 800) 
    200199if ( probType == CPXPROB_MILP ) { 
    … …  
    202201if ( probType == CPXPROB_MIP ) { 
    203202#endif 
    204    int err = CPXgetmipx( (const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr()), (const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr()), &ans, whichCol, whichCol); 
     203   int err = CPXgetmipx( (const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr()), (const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL)), &ans, whichCol, whichCol); 
    205204   if ( err == CPXERR_NO_INT_SOLN ) 
    206205      ans = 0.0; 
    … …  
    209208   } 
    210209else { 
    211    int err = CPXgetx( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), &ans, whichCol, whichCol ); 
     210   int err = CPXgetx( const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), &ans, whichCol, whichCol ); 
    212211   if ( err == CPXERR_NO_SOLN ) 
    213212      ans = 0.0; 
    … …  
    223222{ 
    224223double ans; 
    225 int err = CPXgetpi(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&ans,whichRow,whichRow); 
     224int err = CPXgetpi(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&ans,whichRow,whichRow); 
    226225if (err == CPXERR_NO_SOLN) 
    227226   ans = 0.0; 
    … …  
    236235{ 
    237236double ans; 
    238 int err = CPXgetdj(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),&ans,whichCol,whichCol); 
     237int err = CPXgetdj(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),&ans,whichCol,whichCol); 
    239238if (err == CPXERR_NO_SOLN) 
    240239   ans = 0.0; 
    … …  
    251250int basisSize = numCols + getNumRows(); 
    252251utilib::IntVector tempBasis(basisSize); 
    253 int tmp = CPXgetbase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),(int*)(tempBasis.data()),(int*)(&tempBasis[numCols])); 
     252int tmp = CPXgetbase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),(int*)(tempBasis.data()),(int*)(&tempBasis[numCols])); 
    254253if (tmp) 
    255254   EXCEPTION_MNGR(std::runtime_error,"CPLEX would not retreive basis"); 
    … …  
    267266int numCols = getNumCols(); 
    268267utilib::IntVector tempBasis(numCols + getNumRows()); 
    269 int tmp = CPXgetbase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), 
     268int tmp = CPXgetbase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), 
    270269                (int*)(tempBasis.data()),(int*)(&tempBasis[numCols])); 
    271270if (tmp) 
    … …  
    306305  } 
    307306 
    308 status = CPXcopybase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(),(int*)(tempBasis.data()), 
     307status = CPXcopybase(const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getEnvironmentPtr(),const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL),(int*)(tempBasis.data()), 
    309308                                        (int*)(&tempBasis[getNumCols() ])); 
    310309if (status && lpWarnings) 
    … …  
    403402  // Going to getting lp pointer with default values rather than 
    404403  // OsiCpxSolverInterface::FREECACHED_COLUMN, for debugging 
    405   int err = CPXchgbds( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), len, indexList, &c, upperBounds); 
     404  int err = CPXchgbds( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), len, indexList, &c, upperBounds); 
    406405  checkCPXerror( err, "CPXchgbds", "setColUpper" ); 
    407406} 
    … …  
    411410{ 
    412411  char c = 'L'; 
    413   int err = CPXchgbds( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), len, indexList, &c, lowerBounds); 
     412  int err = CPXchgbds( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), len, indexList, &c, lowerBounds); 
    414413  checkCPXerror( err, "CPXchgbds", "setColLower" ); 
    415414} 
    … …  
    426425    // doesn't give the real variable names (etc) to the cplex solver, 
    427426    // it will be equivalent to the "REW" filetype = generic names 
    428   writeStatus = CPXwriteprob(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), filename, "MPS"); 
     427  writeStatus = CPXwriteprob(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), filename, "MPS"); 
    429428  if (writeStatus) 
    430429    ucout << "Error writing lp to file\n"; 
    … …  
    433432if (format == lp_format) 
    434433  { 
    435   writeStatus = CPXwriteprob(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), filename, "LP"); 
     434  writeStatus = CPXwriteprob(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), filename, "LP"); 
    436435  if (status) 
    437436    ucout << "Error writing lp to file\n"; 
    … …  
    445444void PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>::printBrokenInfo() 
    446445{ 
    447     int stat = CPXgetstat( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr() ); 
     446    int stat = CPXgetstat( getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL) ); 
    448447    ucout << "Broken LP has cplex status " << stat << "\n"; 
    449448} 
    … …  
    452451void PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>::setMatrixCoeff(int row, int col, double newValue) 
    453452{ 
    454     int stat = CPXchgcoef(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(), row, col, newValue); 
     453    int stat = CPXchgcoef(getEnvironmentPtr(), const_cast<PicoLPSubclass<OsiCpxSolverInterface,PicoLPCutMngmnt>*>(this)->OsiCpxSolverInterface::getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL), row, col, newValue); 
    455454    if (stat != 0) EXCEPTION_MNGR(std::runtime_error, "Cplex error setting matrix coefficient for (" << row << ", " << col << ")") 
    456455} 

  • pico/trunk/src/lp/pico/PicoLPInterface.cpp

    r4073 r4094  
    518518} 
    519519 
     520void PicoLPInterface::getRowSense(char* constr, int first, int last) const 
     521{ 
     522  if (last==-1) last=getNumRows()-1; 
     523  const char *tmp = getRowSense(); 
     524  for (int i=first; i<=last; i++) 
     525    *(constr++) = tmp[i]; 
     526} 
    520527 
    521528PicoLPInterface::constraintSense PicoLPInterface::getRowSense(int whichConstraint) const 
    … …  
    583590} 
    584591 
     592/// Returns true if vecToCheck is feasible for this LP problem (satisfies Ax=b,                                                     
     593/// or Ax <= b, etc) within tolerance.  Returns false if infeasible.    
     594 
     595bool PicoLPInterface::checkFeasibility(DoubleVector & vecToCheck) 
     596{ 
     597  bool isFeasible = true; 
     598  int numRows = getNumRows(); 
     599  DoubleVector Ax(numRows); // Matrix-vector product 
     600  getMatrixByCol()->timesMajor(vecToCheck.data(), Ax.data()); 
     601  const double *rhs = getRightHandSide(); 
     602  constraintSense thisConstraintSense; 
     603  for (int i = 0; i < numRows; i++) 
     604    { 
     605      thisConstraintSense = getRowSense(i); 
     606      switch (thisConstraintSense) { 
     607      case lessOrEqual: 
     608        if (Ax[i] > rhs[i] + constraintFeasTolerance) 
     609            isFeasible = false; 
     610            break; 
     611      case greaterOrEqual: 
     612        if (Ax[i] < rhs[i] - constraintFeasTolerance) 
     613          isFeasible = false; 
     614        break; 
     615      case equal: 
     616        if (Ax[i] < rhs[i] - constraintFeasTolerance || Ax[i] > rhs[i] + constraintFeasTolerance) 
     617          isFeasible = false; 
     618        break; 
     619      case ranged: 
     620        EXCEPTION_MNGR(runtime_error,"PicoLPInterface::checkFeasibility -- Need to implement checking of ranged rows\n"); 
     621      }; 
     622      if (!isFeasible) 
     623        break; 
     624    } 
     625  return(isFeasible); 
     626} 
    585627 
    586628void PicoLPInterface::getInfo(BasicArray<Ereal<double> >& objCoefs, 

  • pico/trunk/src/lp/pico/PicoLPInterface.h

    r4070 r4094  
    237237  int lpWarnings; 
    238238 
     239  // Our tolerance for constraint feasibility when we explicitly test a vector 
     240  // for feasibility.  We currently do not coordinate this with tolerances within 
     241  // LP solvers. 
     242 
     243  double constraintFeasTolerance; 
     244 
    239245  /// A flag to indicate this is a pure LP.  PICO can be used just as an interface to an LP solver 
    240246  /// via OSI.  In this case, the various MILP-related data structures will not be initialized. 
    … …  
    624630      virtual constraintSense getRowSense(int whichConstraint) const = 0; 
    625631 
    626       /// 
    627       virtual void getRowSense(char* constr, int first=0, int last=-1) const 
    628                 { 
    629                 if (last==-1) last=getNumRows()-1; 
    630                 for (int i=first; i<=last; i++) 
    631                   *(constr++) = getRowSense(i); 
    632                 } 
     632      // TODO: This seems very inefficient.  Also is relying on coersion from constraintSense. 
     633      /// 
     634      virtual void getRowSense(char* constr, int first=0, int last=-1) const; 
    633635   
    634636      /// 
    … …  
    687689      /// 
    688690      virtual void getMatrixByCol(CMSparseMatrix<Ereal<double> >& mat) const; 
     691 
     692      /// Returns true if vecToCheck is feasible for this LP problem (satisfies Ax=b, 
     693      /// or Ax <= b, etc) within tolerance.  Returns false if infeasible. 
     694      virtual bool checkFeasibility(DoubleVector & vecToCheck); 
    689695 
    690696      /// Get the LP information all at once 
    … …  
    13541360          lpWarnings(2), 
    13551361      solving(false), 
    1356       pureLP(true) 
     1362      pureLP(true), 
     1363      constraintFeasTolerance(1e-7) 
    13571364        { 
    13581365        create_parameter("LPdebug",LPdebug, 
    … …  
    13641371                "Controls the warnings level used within the LP", 
    13651372                utilib::ParameterNonnegative<int>()); 
     1373        create_parameter("constraintFeasTolerance", constraintFeasTolerance, 
     1374                         "<double>", "1e-07", "tolerance for constraint (in)feasibility when we test the feasibility of a vector", utilib::ParameterNonnegative<double>()); 
    13661375        resetInfo(); 
    13671376        reset(); 

  • pico/trunk/src/milp/pico/MILPProblem.cpp

    r4093 r4094  
    306306const int *AIndices = A->getIndices(); 
    307307const CoinBigIndex *AVectorStarts = A->getVectorStarts(); 
     308 
    308309CharString rowType(numRows); 
    309310lp()->getRowSense(rowType.data()); 
     311 
    310312// To record the row number of the special rows we find 
    311313BasicArray<CoinBigIndex> specialRows(numRows); 

  • pico/trunk/src/milp/pico/milp.cpp

    r4092 r4094  
    116116namespace pico { 
    117117 
    118 MILP::MILP() 
    119  : running_with_ampl(false) 
     118  MILP::MILP(): RR_RNG(0), RRUniform(&RR_RNG), 
     119                running_with_ampl(false) 
    120120{ 
    121121version_info += ", PICO 1.0"; 
    … …  
    195195        utilib::ParameterLowerBound<double>(0.0)); 
    196196 
    197  mipHeuristic=false; 
    198  ParameterSet::create_parameter("mipHeuristic",mipHeuristic, 
     197 PICOMIPHeuristics=true; 
     198 ParameterSet::create_parameter("PICOMIPHeuristics", PICOMIPHeuristics, 
     199 "<bool>","true", 
     200 "If this is false, disable all PICO general MIP heuristics."); 
     201 
     202 bhhMIPHeuristic=false; 
     203 ParameterSet::create_parameter("bhhMIPHeuristic",bhhMIPHeuristic, 
    199204 "<bool>","false", 
    200205 "Use Nediak/Eckstein heuristic to find feasible MIP solutions."); 
     206 
     207maxRRDepth = 1; 
     208ParameterSet::create_parameter("maxRRDepth",maxRRDepth,"<int>","1", 
     209                "Apply the randomized rounding heuristic up to this depth in the search tree.\n-1 means no limit. 0 turns off the heuristic"); 
     210 
     211numRRTrialsPerCall = 1; 
     212ParameterSet::create_parameter("numRRTrialsPerCall",numRRTrialsPerCall,"<int>","1", 
     213                "Apply randomized rounding this many times whenever the randomized rounding heuristic\nis invoked. 0 turns off the heuristic."); 
     214 
     215RRSeed = 0; 
     216ParameterSet::create_parameter("RRSeed",RRSeed,"<int>","0", 
     217                "Seed for random number generator within the randomized rounding heuristic"); 
    201218  
    202219preprocessIP=true; 
    … …  
    374391void MILP::MILPResetGuts() 
    375392{ 
     393  // Remember.  Everything that depends on a parameter that might be reset from a 
     394  // command line should be dealt with here (rather than in the initialization code) 
     395  if (RRSeed != 0) 
     396    RR_RNG.reseed(RRSeed); 
    376397cache.sense = sense; 
    377398if (EnumerationRelTolerance >= 0.0) 
    … …  
    532553  initializeBranchingPriorities(); 
    533554 
    534   if (mipHeuristic) 
     555  if (bhhMIPHeuristic) 
    535556    mipHeuristicPtr = new MIPHeuristic(this, heurCfg.bbhCanonicalOnly, debug); 
    536557 

  • pico/trunk/src/milp/pico/milp.h

    r4052 r4094  
    168168 
    169169  BBHConfig     heurCfg; 
    170   bool          mipHeuristic; 
     170  // If false, disable all general PICO MIP heuristics 
     171  bool          PICOMIPHeuristics; 
     172 
     173  // If false, disable Nediak/Eckstin MIP heuristic 
     174  bool bhhMIPHeuristic; 
    171175  MIPHeuristic* mipHeuristicPtr; 
     176 
     177  // Parameters for simple randomized rounding 
     178 
     179  int maxRRDepth;  // Apply randomized rounding up through this depth of the search tree 
     180 
     181// Number of randomized rounding trials per call.  I say "per call" rather than "per node" 
     182// because one might want to try this multiple times on a node when there is significant cutting. 
     183 
     184  int numRRTrialsPerCall;  
     185 
     186  // Seed for the randomized rounding random number generator. 
     187  int RRSeed; 
     188 
     189  // Random number generator for the randomized rounding heuristic.  This generates numbers between 
     190  // 0 and 1 pseudorandomly (with the goal of a uniform distribution) 
     191 
     192  utilib::PM_LCG  RR_RNG; 
     193  utilib::Uniform RRUniform; 
    172194 
    173195  // For debugging (check for fathoming of solutions we should keep) 
    … …  
    270292 
    271293 
    272   virtual bool haveIncumbentHeuristic() { return mipHeuristic; }  
     294  // We have an incumbent heuristic as long as we have not disabled all general PICO MIP 
     295  // heuristics (with the first parameter).  We must also have one individually enabled. 
     296  // Currently there are two choices: the Nediak/Eckstein heuristic and a simple randomized 
     297  // rounding heuristic. 
     298 
     299  virtual bool haveIncumbentHeuristic() 
     300    { return (PICOMIPHeuristics && (bhhMIPHeuristic || 
     301                                    (maxRRDepth != 0 && numRRTrialsPerCall >= 1))); }  
    273302 
    274303  virtual void updateIncumbent(DoubleVector& newSolution, double solutionValue); 

  • pico/trunk/src/milp/pico/milpNode.cpp

    r4075 r4094  
    11221122 
    11231123 
    1124 // Apply the incumbent heuristic.  This may be overridden! 
    1125  
    11261124void MILPNode::incumbentHeuristic() 
     1125{ 
     1126  // Call all enabled incumbent heuristics in order. 
     1127  // They are expected to police themselves.  This should 
     1128  // not be called if all heuristics are disabled. 
     1129 
     1130  if (mGlobal()->numRRTrialsPerCall > 0) 
     1131    RRheuristic(); 
     1132  if (mGlobal()->mipHeuristicPtr) 
     1133    BBHincumbentHeuristic(); 
     1134} 
     1135 
     1136  // A randomized rounding heuristic.  Round based on the LP 
     1137  // relaxation.  For a binary variable with fractional value f, round 
     1138  // to 0 with probability f and to 1 with probability (1-f).  For a 
     1139  // general integer variable with non-integer value v.f (f is the 
     1140  // fractional part), round to v with probability f and to v+1 with 
     1141  // probability (1-f).  If there are continuous variables, set them 
     1142  // with the LP if possible after all integer variables are set. 
     1143  // Apply to every node up to depth maxRRDepth.  At each node, do 
     1144  // numRRTrialsPerCall trials.  Default is trying once at the root 
     1145  // for every LP solve.  TODO: consider whether we only want to do once per 
     1146  // node, or at start/end, etc. 
     1147  // Currently we do this many trials after each LP bounding,  
     1148  // This will give an immediate incumbent for IPs where every setting 
     1149  // of the integer variables is feasible. 
     1150 
     1151void MILPNode::RRheuristic() 
     1152{ 
     1153  if (mGlobal()->maxRRDepth != -1 && depth > mGlobal()->maxRRDepth) 
     1154    return; 
     1155  MILPProblem* localMipRef = mip(); 
     1156  int numVars = localMipRef->numAllVars(); 
     1157  DoubleVector  heuristicSolution(numVars); 
     1158  int numTrials = mGlobal()->numRRTrialsPerCall; 
     1159  bool pureInteger, solnKnownFeasible, success; 
     1160  int numInts = localMipRef->numIntegerVars(); 
     1161  int j, intVal; 
     1162  size_type k; 
     1163  double currVal, randToss, fracPart; 
     1164 
     1165  if (numVars - localMipRef->numIntegerVars() == 0) 
     1166    pureInteger = true; 
     1167  else pureInteger = false; 
     1168  for (size_type i = 0; i < numTrials; i++) 
     1169    { 
     1170      for (k=0; k < numInts; k++) { 
     1171        j = localMipRef->integerVarNdx[k]; // get LP var# for this int var # 
     1172        currVal = solution[k]; 
     1173        if (isInteger(currVal)) 
     1174          intVal = lround(currVal); 
     1175        else 
     1176          { 
     1177            fracPart = currVal - floor(currVal); 
     1178            randToss = mGlobal()->RRUniform(); 
     1179            // fractional portion is the probability of rounding up.  So a toss 
     1180            // between 0 and the fractional value rounds up. 
     1181            if (fracPart >= randToss) 
     1182              intVal = (int)ceil(currVal); 
     1183            else intVal = (int)floor(currVal); 
     1184          } 
     1185        heuristicSolution[j] = intVal; 
     1186      } 
     1187      if (!pureInteger) 
     1188        { 
     1189          success = setContinuousVars(heuristicSolution, solnKnownFeasible); 
     1190          if (!success) // Couldn't set the continuous variables 
     1191            continue; 
     1192          if (solnKnownFeasible) 
     1193            { 
     1194              mGlobal()->updateIncumbent(heuristicSolution, lp->evalVector(heuristicSolution)); 
     1195#ifdef ACRO_VALIDATING 
     1196              if(lp->checkFeasibility(heuristicSolution)) 
     1197                ucout << "Verified feasibility of heuristic solution\n"; 
     1198              else  
     1199                EXCEPTION_MNGR(runtime_error, "Supposedly feasible heuristic solution failed feasibility test\n"); 
     1200#endif 
     1201              DEBUGPR(10, ucout << "RR incumbent with value " << lp->evalVector(heuristicSolution) << "\n"); 
     1202              continue; 
     1203            } 
     1204        } 
     1205      // Either a pure integer problem or we set the continous variables in the heuristic 
     1206      // solution, but still need it checked. 
     1207      if (lp->checkFeasibility(heuristicSolution)) 
     1208        { 
     1209        mGlobal()->updateIncumbent(heuristicSolution, lp->evalVector(heuristicSolution)); 
     1210        DEBUGPR(10, ucout << "RR incumbent with value " << lp->evalVector(heuristicSolution) << "\n"); 
     1211        } 
     1212    } 
     1213} 
     1214 
     1215  // Used by the randomized rounding heuristic, and possibly useful 
     1216  // for user-defined incumbent heuristics.  Takes a partial (full) 
     1217  // solution where all integer variables have been set to viable 
     1218  // integer values and sets the continuous variables in the solution. 
     1219  // Returns true if the method succeeds in setting the continuous 
     1220  // variables.  Sets solnKnownFeasible to true if the resulting 
     1221  // solution vector is known to be feasible.  The default behavior is 
     1222  // to use an LP to set the continuous variables.  In this case, 
     1223  // succeeding in setting the variables and knowing the solution is 
     1224  // feasible is the same test (LP solve).  More generally, in an 
     1225  // application with more structure, a user might know of a way to 
     1226  // set the continous variables from the integer variables without 
     1227  // using an LP.  If the user has a problem-specific feasibility 
     1228  // test, they can either set solnKnownFeasible (if it succeeds) or 
     1229  // return false if it fails. 
     1230 
     1231bool MILPNode::setContinuousVars(DoubleVector &partialSolution, bool &solnKnownFeasible) 
     1232{ 
     1233  MILPProblem* localMipRef = mip(); 
     1234  int numInts = localMipRef->numIntegerVars(); 
     1235  int valToSet, j; 
     1236  DoubleVector origLB(numInts), origUB(numInts); 
     1237  // Save current bounds on the integer variables so we can restore them 
     1238  lp->getColLower(origLB.data(), localMipRef->integerVarNdx.data(), numInts); 
     1239  lp->getColUpper(origUB.data(), localMipRef->integerVarNdx.data(), numInts); 
     1240 
     1241  for (size_type i=0; i < numInts; i++) 
     1242    { 
     1243        j = localMipRef->integerVarNdx[i]; // get LP var# for this int var # 
     1244#ifdef ACRO_VALIDATING 
     1245        if (!isInteger(partialSolution[j])) 
     1246          EXCEPTION_MNGR(runtime_error, "MILPNode::setContinuousVars:  partial solution integer variable " << i << " has value " << partialSolution[j] << " but should be an integer.\n"); 
     1247#endif 
     1248        // coersion is to remove a compiler warning.  Variables that should be integer should 
     1249        // have integer values in the vector and it will be checked above if validation is on. 
     1250        valToSet = (int)partialSolution[j]; 
     1251        lp->setColLower(j, valToSet); 
     1252        lp->setColUpper(j, valToSet); 
     1253    } 
     1254  PicoLPInterface::problemState solvedState = recheckSolution(); 
     1255 
     1256  bool setvars; 
     1257 
     1258  if (solvedState == PicoLPInterface::solved) 
     1259    { 
     1260      // Will redundantly set integer variables.  We could consider just setting the continous 
     1261      // ones at some point. 
     1262      lp->getColSolution(partialSolution.data()); 
     1263      solnKnownFeasible = true; 
     1264      setvars= true; 
     1265    } 
     1266  else 
     1267    { 
     1268      solnKnownFeasible = false; 
     1269      setvars = false; 
     1270    } 
     1271 
     1272  // reset the bounds on integer variables. 
     1273 
     1274  lp->setColLower(origLB.data(), localMipRef->integerVarNdx.data(), numInts); 
     1275  lp->setColUpper(origUB.data(), localMipRef->integerVarNdx.data(), numInts); 
     1276 
     1277  return (setvars); 
     1278} 
     1279 
     1280// Apply the Nediak/Eckstein incumbent heuristic. 
     1281 
     1282void MILPNode::BBHincumbentHeuristic() 
    11271283{ 
    11281284  DEBUGPR(100,ucout << "MILPNode::incumbentHeuristic():" << endl); 
    … …  
    18281984} 
    18291985 
     1986// This is not currently called.  It appears to be incomplete (doesn't check for 
     1987// feasibility, doesn't consider variable type, etc).  It appears this version doesn't 
     1988// use information from the LP relaxation.  This may be permanently superceded by the 
     1989// randomized rounding heuristic. 
     1990 
    18301991int MILPNode::urandomIncumbentHeuristic(DoubleVector& vec, double& value) 
    18311992{ 

  • pico/trunk/src/milp/pico/milpNode.h

    r4052 r4094  
    245245 
    246246  virtual void  incumbentHeuristic(); 
     247  void BBHincumbentHeuristic(); // Nediak/Eckstein heuristic 
     248 
     249  // A randomized rounding heuristic.  Round based on the LP 
     250  // relaxation.  For a binary variable with fractional value f, round 
     251  // to 0 with probability f and to 1 with probability (1-f).  For a 
     252  // general integer variable with non-integer value v.f (f is the 
     253  // fractional part), round to v with probability f and to v+1 with 
     254  // probability (1-f).  If there are continuous variables, set them 
     255  // with the LP if possible after all integer variables are set. 
     256  // Apply to every node up to depth maxRRDepth.  At each invocation, do 
     257  // numRRTrialsPerCall trials.  Default is trying once at the root 
     258  // for every LP solve.  TODO: consider whether we only want to do once per 
     259  // node, or at start/end, etc. 
     260    // This will give an immediate incumbent for IPs where every setting 
     261  // of the integer variables is feasible. 
     262 
     263  void RRheuristic(); 
     264 
     265  // Used by the randomized rounding heuristic, and possibly useful 
     266  // for user-defined incumbent heuristics.  Takes a partial solution 
     267  // where all integer variables have been set to viable integer 
     268  // values and sets the continuous variables in the solution. 
     269  // Returns true if the method succeeds in setting the continuous 
     270  // variables.  Sets solnKnownFeasible to true if the resulting 
     271  // solution vector is known to be feasible.  The default behavior is 
     272  // to use an LP to set the continuous variables.  In this case, 
     273  // succeeding in setting the variables and knowing the solution is 
     274  // feasible is the same test (LP solve).  More generally, in an 
     275  // application with more structure, a user might know of a way to 
     276  // set the continous variables from the integer variables without 
     277  // using an LP.  If the user has a problem-specific feasibility 
     278  // test, they can either set solnKnownFeasible (if it succeeds) or 
     279  // return false if it fails. 
     280 
     281  virtual bool setContinuousVars(DoubleVector &partialSolution, bool &solnKnownFeasible); 
     282 
    247283  double        improveIncumbent(); 
    248284  virtual void  updateIncumbent();