Couenne::CouenneFeasPump Class Reference

An implementation of the Feasibility pump that uses linearization and Ipopt to find the two sequences of points. More...

#include <CouenneFeasPump.hpp>

Collaboration diagram for Couenne::CouenneFeasPump:

Collaboration graph
[legend]
List of all members.

Public Types

 FP_DIST_INT
 FP_DIST_ALL
 FP_DIST_POST
 FP_CUT_NONE
 FP_CUT_INTEGRATED
 FP_CUT_EXTERNAL
 FP_CUT_POST
 FP_TABU_NONE
 FP_TABU_POOL
 FP_TABU_PERTURB
 FP_TABU_CUT
enum  fpCompDistIntType { FP_DIST_INT, FP_DIST_ALL, FP_DIST_POST }
enum  fpCutPlane { FP_CUT_NONE, FP_CUT_INTEGRATED, FP_CUT_EXTERNAL, FP_CUT_POST }
enum  fpTabuMgtPolicy { FP_TABU_NONE, FP_TABU_POOL, FP_TABU_PERTURB, FP_TABU_CUT }

Public Member Functions

 CouenneFeasPump (CouenneProblem *couenne=NULL, CouenneCutGenerator *cg=NULL, Ipopt::SmartPtr< Ipopt::OptionsList > options=NULL)
 Constructor with (optional) MINLP pointer.
 CouenneFeasPump (const CouenneFeasPump &other)
 Copy constructor.
virtual ~CouenneFeasPump ()
 Destructor.
virtual CbcHeuristic * clone () const
 Clone.
CouenneFeasPumpoperator= (const CouenneFeasPump &rhs)
 Assignment operator.
virtual void resetModel (CbcModel *model)
 Does nothing, but necessary as CbcHeuristic declares it pure virtual.
virtual int solution (double &objectiveValue, double *newSolution)
 Run heuristic, return 1 if a better solution than the one passed is found and 0 otherwise.
void setNumberSolvePerLevel (int value)
 set number of nlp's solved for each given level of the tree
CouNumber solveMILP (CouNumber *nSol, CouNumber *&iSol, int niter, int *nsuciter)
 find integer (possibly NLP-infeasible) point isol closest (according to the l-1 norm of the hessian) to the current NLP-feasible (but fractional) solution nsol
CouNumber solveNLP (CouNumber *nSol, CouNumber *&iSol)
 obtain solution to NLP
expressionupdateNLPObj (const double *)
 set new expression as the NLP objective function using argument as point to minimize distance from.
void fixIntVariables (double *sol)
 admits a (possibly fractional) solution and fixes the integer components in the nonlinear problem for later re-solve
double findSolution (double *&sol, int niter, int *nsuciter)
 find feasible solution (called by solveMILP ())
void init_MILP ()
 initialize all solvers at the first call, where the initial MILP is built
void initIpoptApp ()
 Common code for initializing non-smartptr ipopt application.
CouenneProblemProblem () const
 return pointer to problem
enum fpCompDistIntType compDistInt () const
 return type of MILP solved
double multDistNLP () const
 Return Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): weight of distance in NLP.
double multHessNLP () const
 weight of Hessian in NLP
double multObjFNLP () const
 weight of objective in NLP
double multDistMILP () const
 weight of distance in MILP
double multHessMILP () const
 weight of Hessian in MILP
double multObjFMILP () const
 weight of objective in MILP
CouenneTNLPnlp () const
 return NLP

Static Public Member Functions

static void registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions >)
 initialize options to be read later

Private Attributes

CouenneProblemproblem_
 Couenne representation of the problem.
CouenneCutGeneratorcouenneCG_
 CouenneCutGenerator for linearization cuts.
CouenneTNLPnlp_
 Continuous relaxation of the problem, with an interface for Ipopt only.
Ipopt::IpoptApplication * app_
 Ipopt Application pointer for solving NLPs.
OsiSolverInterface * milp_
 MILP relaxation of the MINLP (used to find integer non-NLP-feasible solution).
OsiSolverInterface * postlp_
 LP relaxation of the MINLP used when fixing integer variables (used for compDistInt_ in FP_DIST_POST and possibly FP_DIST_INT).
CouenneFPpoolpool_
 Pool of solutions.
std::set< CouenneFPsolution,
compareSol
tabuPool_
 Solutions to avoid.
int numberSolvePerLevel_
 Number of NLPs solved for each given level of the tree.
double multDistNLP_
 Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): weight of distance in NLP.
double multHessNLP_
 weight of Hessian in NLP
double multObjFNLP_
 weight of objective in NLP
double multDistMILP_
 weight of distance in MILP
double multHessMILP_
 weight of Hessian in MILP
double multObjFMILP_
 weight of objective in MILP
enum fpCompDistIntType compDistInt_
 compute distance from integer variables only, not all variables;
enum fpCutPlane milpCuttingPlane_
 Separate convexification cuts during or after MILP.
int nSepRounds_
 Number of separation rounds for MILP convexification cuts.
int maxIter_
 maximum iterations per call
bool useSCIP_
 use SCIP instead of Cbc for solving MILPs
int milpMethod_
 Which SCIP MILP method to use.
enum fpTabuMgtPolicy tabuMgt_
 Tabu management policy: none, use from pool, random perturbation of current solution.

Detailed Description

An implementation of the Feasibility pump that uses linearization and Ipopt to find the two sequences of points.

Definition at line 48 of file CouenneFeasPump.hpp.


Member Enumeration Documentation

enum Couenne::CouenneFeasPump::fpCompDistIntType

Enumerator:
FP_DIST_INT 
FP_DIST_ALL 
FP_DIST_POST 

Definition at line 52 of file CouenneFeasPump.hpp.

enum Couenne::CouenneFeasPump::fpCutPlane

Enumerator:
FP_CUT_NONE 
FP_CUT_INTEGRATED 
FP_CUT_EXTERNAL 
FP_CUT_POST 

Definition at line 53 of file CouenneFeasPump.hpp.

enum Couenne::CouenneFeasPump::fpTabuMgtPolicy

Enumerator:
FP_TABU_NONE 
FP_TABU_POOL 
FP_TABU_PERTURB 
FP_TABU_CUT 

Definition at line 54 of file CouenneFeasPump.hpp.


Constructor & Destructor Documentation

CouenneFeasPump::CouenneFeasPump ( CouenneProblem couenne = NULL,
CouenneCutGenerator cg = NULL,
Ipopt::SmartPtr< Ipopt::OptionsList >  options = NULL 
)

Constructor with (optional) MINLP pointer.

Definition at line 55 of file CouenneFeasPumpConstructors.cpp.

References compDistInt_, FP_CUT_EXTERNAL, FP_CUT_INTEGRATED, FP_CUT_NONE, FP_CUT_POST, FP_DIST_ALL, FP_DIST_INT, FP_DIST_POST, FP_TABU_CUT, FP_TABU_NONE, FP_TABU_PERTURB, FP_TABU_POOL, initIpoptApp(), Couenne::J_COUENNE(), maxIter_, milpCuttingPlane_, milpMethod_, multDistMILP_, multDistNLP_, multHessMILP_, multHessNLP_, multObjFMILP_, multObjFNLP_, nSepRounds_, numberSolvePerLevel_, pool_, problem_, s, Couenne::SUM_NINF, tabuMgt_, and useSCIP_.

Referenced by clone().

CouenneFeasPump::CouenneFeasPump ( const CouenneFeasPump other  ) 

Copy constructor.

Definition at line 152 of file CouenneFeasPumpConstructors.cpp.

References operator=().

CouenneFeasPump::~CouenneFeasPump (  )  [virtual]

Destructor.

Definition at line 251 of file CouenneFeasPumpConstructors.cpp.

References app_, milp_, pool_, and postlp_.


Member Function Documentation

CbcHeuristic * CouenneFeasPump::clone (  )  const [virtual]

Clone.

Definition at line 198 of file CouenneFeasPumpConstructors.cpp.

References CouenneFeasPump().

Referenced by operator=().

CouenneFeasPump & CouenneFeasPump::operator= ( const CouenneFeasPump rhs  ) 

Assignment operator.

Definition at line 203 of file CouenneFeasPumpConstructors.cpp.

References app_, clone(), compDistInt_, couenneCG_, initIpoptApp(), maxIter_, milp_, milpCuttingPlane_, milpMethod_, multDistMILP_, multDistNLP_, multHessMILP_, multHessNLP_, multObjFMILP_, multObjFNLP_, nlp_, nSepRounds_, numberSolvePerLevel_, pool_, postlp_, problem_, tabuMgt_, tabuPool_, and useSCIP_.

Referenced by CouenneFeasPump().

virtual void Couenne::CouenneFeasPump::resetModel ( CbcModel *  model  )  [inline, virtual]

Does nothing, but necessary as CbcHeuristic declares it pure virtual.

Definition at line 74 of file CouenneFeasPump.hpp.

int CouenneFeasPump::solution ( double &  objectiveValue,
double *  newSolution 
) [virtual]

Run heuristic, return 1 if a better solution than the one passed is found and 0 otherwise.

objectiveValue Best known solution in input and value of solution found in output

newSolution Solution found by heuristic.

Definition at line 39 of file CouenneFeasPump.cpp.

References app_, Couenne::t_chg_bounds::CHANGED, Couenne::CouenneProblem::checkNLP2(), couenneCG_, e, fixIntVariables(), FP_CUT_EXTERNAL, FP_CUT_POST, FP_TABU_CUT, FP_TABU_NONE, FP_TABU_PERTURB, FP_TABU_POOL, Couenne::CouenneProblem::getFeasTol(), Couenne::CouenneRecordBestSol::getModSol(), Couenne::CouenneRecordBestSol::getModSolVal(), Couenne::CouenneProblem::getRecordBestSol(), Couenne::CouenneRecordBestSol::getSol(), Couenne::CouenneRecordBestSol::getVal(), Couenne::isInteger(), Couenne::J_NLPHEURISTIC(), maxIter_, milp_, milpCuttingPlane_, multHessMILP_, multHessNLP_, nlp_, nSepRounds_, numberSolvePerLevel_, Couenne::CouenneProblem::nVars(), pool_, postlp_, print(), printCmpSol(), printDist(), problem_, RND_DECR_EXPONENT, Couenne::t_chg_bounds::setUpper(), solveMILP(), solveNLP(), tabuMgt_, tabuPool_, Couenne::CouenneRecordBestSol::update(), and x.

void Couenne::CouenneFeasPump::setNumberSolvePerLevel ( int  value  )  [inline]

set number of nlp's solved for each given level of the tree

Definition at line 86 of file CouenneFeasPump.hpp.

References numberSolvePerLevel_.

CouNumber CouenneFeasPump::solveMILP ( CouNumber nSol,
CouNumber *&  iSol,
int  niter,
int *  nsuciter 
)

find integer (possibly NLP-infeasible) point isol closest (according to the l-1 norm of the hessian) to the current NLP-feasible (but fractional) solution nsol

Definition at line 52 of file CouenneFPSolveMILP.cpp.

References addDistanceConstraints(), compDistInt_, createCloneMILP(), e, findSolution(), FP_DIST_ALL, FP_DIST_INT, FP_DIST_POST, init_MILP(), Couenne::isInteger(), Couenne::J_NLPHEURISTIC(), milp_, NUMERICS_THRES, postlp_, and problem_.

Referenced by solution().

CouNumber CouenneFeasPump::solveNLP ( CouNumber nSol,
CouNumber *&  iSol 
)

obtain solution to NLP

Definition at line 27 of file CouenneFPSolveNLP.cpp.

References app_, Couenne::J_NLPHEURISTIC(), nlp_, print(), problem_, and updateNLPObj().

Referenced by solution().

expression * CouenneFeasPump::updateNLPObj ( const double *   ) 

set new expression as the NLP objective function using argument as point to minimize distance from.

Return new objective function

Definition at line 265 of file CouenneFeasPumpConstructors.cpp.

References compDistInt_, COUENNE_EPS, FP_DIST_INT, Couenne::isInteger(), multDistNLP_, multHessNLP_, multObjFNLP_, nlp_, and problem_.

Referenced by solveNLP().

void CouenneFeasPump::fixIntVariables ( double *  sol  ) 

admits a (possibly fractional) solution and fixes the integer components in the nonlinear problem for later re-solve

Definition at line 419 of file CouenneFeasPumpConstructors.cpp.

References Couenne::t_chg_bounds::CHANGED, COUENNE_EPS, INT_NLP_BRACKET, Couenne::isInteger(), problem_, Couenne::t_chg_bounds::setLower(), and Couenne::t_chg_bounds::setUpper().

Referenced by solution().

void CouenneFeasPump::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions  )  [static]

initialize options to be read later

Definition at line 459 of file CouenneFeasPumpConstructors.cpp.

Referenced by Couenne::CouenneSetup::registerAllOptions().

double CouenneFeasPump::findSolution ( double *&  sol,
int  niter,
int *  nsuciter 
)

find feasible solution (called by solveMILP ())

as found on the notes, these methods can be used, from the most expensive and accurate (exact) method to a cheap, inexact one:

1. Solve a MILP relaxation with Manhattan distance as objective 2. Partially solve the MILP with emphasis on good solutions 3. Apply RENS to 1 4. Use Objective FP 2.0 for MILPs 5. round-and-propagate 6. choose from pool, see 4 7. random perturbation

solve MILP

Definition at line 28 of file CouenneFPFindSolution.cpp.

References couenneCG_, FP_CUT_INTEGRATED, Couenne::J_NLPHEURISTIC(), milp_, milpCuttingPlane_, milpMethod_, pool_, problem_, tabuPool_, and useSCIP_.

Referenced by solveMILP().

void CouenneFeasPump::init_MILP (  ) 

initialize all solvers at the first call, where the initial MILP is built

Definition at line 482 of file CouenneFPFindSolution.cpp.

Referenced by solveMILP().

void CouenneFeasPump::initIpoptApp (  ) 

Common code for initializing non-smartptr ipopt application.

Definition at line 31 of file CouenneFeasPumpConstructors.cpp.

References app_, Couenne::J_NLPHEURISTIC(), and problem_.

Referenced by CouenneFeasPump(), and operator=().

CouenneProblem* Couenne::CouenneFeasPump::Problem (  )  const [inline]

return pointer to problem

Definition at line 125 of file CouenneFeasPump.hpp.

References problem_.

enum fpCompDistIntType Couenne::CouenneFeasPump::compDistInt (  )  const [inline]

return type of MILP solved

Definition at line 129 of file CouenneFeasPump.hpp.

References compDistInt_.

double Couenne::CouenneFeasPump::multDistNLP (  )  const [inline]

Return Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): weight of distance in NLP.

Definition at line 135 of file CouenneFeasPump.hpp.

References multDistNLP_.

double Couenne::CouenneFeasPump::multHessNLP (  )  const [inline]

weight of Hessian in NLP

Definition at line 136 of file CouenneFeasPump.hpp.

References multHessNLP_.

double Couenne::CouenneFeasPump::multObjFNLP (  )  const [inline]

weight of objective in NLP

Definition at line 137 of file CouenneFeasPump.hpp.

References multObjFNLP_.

double Couenne::CouenneFeasPump::multDistMILP (  )  const [inline]

weight of distance in MILP

Definition at line 139 of file CouenneFeasPump.hpp.

References multDistMILP_.

double Couenne::CouenneFeasPump::multHessMILP (  )  const [inline]

weight of Hessian in MILP

Definition at line 140 of file CouenneFeasPump.hpp.

References multHessMILP_.

double Couenne::CouenneFeasPump::multObjFMILP (  )  const [inline]

weight of objective in MILP

Definition at line 141 of file CouenneFeasPump.hpp.

References multObjFMILP_.

CouenneTNLP* Couenne::CouenneFeasPump::nlp (  )  const [inline]

return NLP

Definition at line 144 of file CouenneFeasPump.hpp.

References nlp_.


Member Data Documentation

CouenneProblem* Couenne::CouenneFeasPump::problem_ [private]

Couenne representation of the problem.

Definition at line 155 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), findSolution(), fixIntVariables(), initIpoptApp(), operator=(), Problem(), solution(), solveMILP(), solveNLP(), and updateNLPObj().

CouenneCutGenerator* Couenne::CouenneFeasPump::couenneCG_ [private]

CouenneCutGenerator for linearization cuts.

Definition at line 158 of file CouenneFeasPump.hpp.

Referenced by findSolution(), operator=(), and solution().

CouenneTNLP* Couenne::CouenneFeasPump::nlp_ [private]

Continuous relaxation of the problem, with an interface for Ipopt only.

Definition at line 169 of file CouenneFeasPump.hpp.

Referenced by nlp(), operator=(), solution(), solveNLP(), and updateNLPObj().

Ipopt::IpoptApplication* Couenne::CouenneFeasPump::app_ [private]

Ipopt Application pointer for solving NLPs.

Definition at line 172 of file CouenneFeasPump.hpp.

Referenced by initIpoptApp(), operator=(), solution(), solveNLP(), and ~CouenneFeasPump().

OsiSolverInterface* Couenne::CouenneFeasPump::milp_ [private]

MILP relaxation of the MINLP (used to find integer non-NLP-feasible solution).

Definition at line 176 of file CouenneFeasPump.hpp.

Referenced by findSolution(), operator=(), solution(), solveMILP(), and ~CouenneFeasPump().

OsiSolverInterface* Couenne::CouenneFeasPump::postlp_ [private]

LP relaxation of the MINLP used when fixing integer variables (used for compDistInt_ in FP_DIST_POST and possibly FP_DIST_INT).

Definition at line 181 of file CouenneFeasPump.hpp.

Referenced by operator=(), solution(), solveMILP(), and ~CouenneFeasPump().

CouenneFPpool* Couenne::CouenneFeasPump::pool_ [private]

Pool of solutions.

Definition at line 184 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), findSolution(), operator=(), solution(), and ~CouenneFeasPump().

std::set<CouenneFPsolution, compareSol> Couenne::CouenneFeasPump::tabuPool_ [private]

Solutions to avoid.

Definition at line 187 of file CouenneFeasPump.hpp.

Referenced by findSolution(), operator=(), and solution().

int Couenne::CouenneFeasPump::numberSolvePerLevel_ [private]

Number of NLPs solved for each given level of the tree.

Definition at line 194 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), operator=(), setNumberSolvePerLevel(), and solution().

double Couenne::CouenneFeasPump::multDistNLP_ [private]

Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): weight of distance in NLP.

Definition at line 199 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multDistNLP(), operator=(), and updateNLPObj().

double Couenne::CouenneFeasPump::multHessNLP_ [private]

weight of Hessian in NLP

Definition at line 200 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multHessNLP(), operator=(), solution(), and updateNLPObj().

double Couenne::CouenneFeasPump::multObjFNLP_ [private]

weight of objective in NLP

Definition at line 201 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multObjFNLP(), operator=(), and updateNLPObj().

double Couenne::CouenneFeasPump::multDistMILP_ [private]

weight of distance in MILP

Definition at line 203 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multDistMILP(), and operator=().

double Couenne::CouenneFeasPump::multHessMILP_ [private]

weight of Hessian in MILP

Definition at line 204 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multHessMILP(), operator=(), and solution().

double Couenne::CouenneFeasPump::multObjFMILP_ [private]

weight of objective in MILP

Definition at line 205 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), multObjFMILP(), and operator=().

enum fpCompDistIntType Couenne::CouenneFeasPump::compDistInt_ [private]

compute distance from integer variables only, not all variables;

Definition at line 208 of file CouenneFeasPump.hpp.

Referenced by compDistInt(), CouenneFeasPump(), operator=(), solveMILP(), and updateNLPObj().

enum fpCutPlane Couenne::CouenneFeasPump::milpCuttingPlane_ [private]

Separate convexification cuts during or after MILP.

Definition at line 211 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), findSolution(), operator=(), and solution().

int Couenne::CouenneFeasPump::nSepRounds_ [private]

Number of separation rounds for MILP convexification cuts.

Definition at line 214 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), operator=(), and solution().

int Couenne::CouenneFeasPump::maxIter_ [private]

maximum iterations per call

Definition at line 217 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), operator=(), and solution().

bool Couenne::CouenneFeasPump::useSCIP_ [private]

use SCIP instead of Cbc for solving MILPs

Definition at line 220 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), findSolution(), and operator=().

int Couenne::CouenneFeasPump::milpMethod_ [private]

Which SCIP MILP method to use.

Definition at line 223 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), findSolution(), and operator=().

enum fpTabuMgtPolicy Couenne::CouenneFeasPump::tabuMgt_ [private]

Tabu management policy: none, use from pool, random perturbation of current solution.

Definition at line 226 of file CouenneFeasPump.hpp.

Referenced by CouenneFeasPump(), operator=(), and solution().


The documentation for this class was generated from the following files:
Generated on Wed Nov 30 03:13:27 2011 by  doxygen 1.4.7