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

#include <CouenneFeasPump.hpp>

Inheritance diagram for Couenne::CouenneFeasPump:

[legend]

Collaboration diagram for Couenne::CouenneFeasPump:

[legend]

Public Types
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. More...

	CouenneFeasPump (const CouenneFeasPump &other)
	Copy constructor. More...

virtual	~CouenneFeasPump ()
	Destructor. More...

virtual CbcHeuristic *	clone () const
	Clone. More...

CouenneFeasPump &	operator= (const CouenneFeasPump &rhs)
	Assignment operator. More...

virtual void	resetModel (CbcModel *model)
	Does nothing, but necessary as CbcHeuristic declares it pure virtual. More...

virtual int	solution (double &objectiveValue, double *newSolution)
	Run heuristic, return 1 if a better solution than the one passed is found and 0 otherwise. More...

void	setNumberSolvePerLevel (int value)
	set number of nlp's solved for each given level of the tree More...

virtual CouNumber	solveMILP (const 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 More...

virtual CouNumber	solveNLP (const CouNumber nSol, CouNumber &iSol)
	obtain solution to NLP More...

expression *	updateNLPObj (const double *)
	set new expression as the NLP objective function using argument as point to minimize distance from. More...

bool	fixIntVariables (const double *sol)
	admits a (possibly fractional) solution and fixes the integer components in the nonlinear problem for later re-solve. More...

double	findSolution (const double nSol, double &sol, int niter, int *nsuciter)
	find feasible solution (called by solveMILP ()) More...

void	init_MILP ()
	initialize all solvers at the first call, where the initial MILP is built More...

void	initIpoptApp ()
	Common code for initializing non-smartptr ipopt application. More...

CouenneProblem *	Problem () const
	return pointer to problem More...

enum fpCompDistIntType	compDistInt () const
	return type of MILP solved More...

double	multDistNLP () const
	Return Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): More...

double	multHessNLP () const
	weight of Hessian in NLP More...

double	multObjFNLP () const
	weight of objective in NLP More...

double	multDistMILP () const
	weight of distance in MILP More...

double	multHessMILP () const
	weight of Hessian in MILP More...

double	multObjFMILP () const
	weight of objective in MILP More...

CouenneTNLP *	nlp () const
	return NLP More...

int &	nCalls ()
	return number of calls (can be changed) More...

int	milpPhase (double nSol, double iSol)
	MILP phase of the FP. More...

int	nlpPhase (double iSol, double nSol)
	NLP phase of the FP. More...

Static Public Member Functions
static void	registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions >)
	initialize options to be read later More...

Private Attributes
CouenneProblem *	problem_
	Couenne representation of the problem. More...

CouenneCutGenerator *	couenneCG_
	CouenneCutGenerator for linearization cuts. More...

CouenneTNLP *	nlp_
	Continuous relaxation of the problem, with an interface for Ipopt only. More...

Ipopt::IpoptApplication *	app_
	Ipopt Application pointer for solving NLPs. More...

OsiSolverInterface *	milp_
	MILP relaxation of the MINLP (used to find integer, non-NLP-feasible solutions) More...

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

CouenneFPpool *	pool_
	Pool of solutions. More...

std::set< CouenneFPsolution, compareSol >	tabuPool_
	Solutions to avoid. More...

int *	match_
	matching between reformulation's variables and L-1 norm variables More...

int	numberSolvePerLevel_
	Number of NLPs solved for each given level of the tree. More...

double	multDistNLP_
	Weights in computing distance, in both MILP and NLP (must sum up to 1 for MILP and for NLP): More...

double	multHessNLP_
	weight of Hessian in NLP More...

double	multObjFNLP_
	weight of objective in NLP More...

double	multDistMILP_
	weight of distance in MILP More...

double	multHessMILP_
	weight of Hessian in MILP More...

double	multObjFMILP_
	weight of objective in MILP More...

enum fpCompDistIntType	compDistInt_
	Compute distance from integer variables only, not all variables. More...

enum fpCutPlane	milpCuttingPlane_
	Separate convexification cuts during or after MILP. More...

int	nSepRounds_
	Number of separation rounds for MILP convexification cuts. More...

int	maxIter_
	Maximum iterations per call. More...

bool	useSCIP_
	Use SCIP instead of Cbc for solving MILPs. More...

int	milpMethod_
	Which SCIP MILP method to use. More...

enum fpTabuMgtPolicy	tabuMgt_
	Tabu management policy: none, use from pool, random perturbation of current solution. More...

int	nCalls_
	How often should it be called. More...

double	fadeMult_
	decrease factor for MILP/NLP multipliers of distance/Hessian/objective More...

Detailed Description

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

Definition at line 57 of file CouenneFeasPump.hpp.

Member Enumeration Documentation

enum Couenne::CouenneFeasPump::fpCompDistIntType

Enumerator
FP_DIST_INT
FP_DIST_ALL
FP_DIST_POST

Definition at line 61 of file CouenneFeasPump.hpp.

enum Couenne::CouenneFeasPump::fpCutPlane

Enumerator
FP_CUT_NONE
FP_CUT_INTEGRATED
FP_CUT_EXTERNAL
FP_CUT_POST

Definition at line 62 of file CouenneFeasPump.hpp.

enum Couenne::CouenneFeasPump::fpTabuMgtPolicy

Enumerator
FP_TABU_NONE
FP_TABU_POOL
FP_TABU_PERTURB
FP_TABU_CUT

Definition at line 63 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 58 of file CouenneFeasPumpConstructors.cpp.

CouenneFeasPump::CouenneFeasPump ( const CouenneFeasPump & other )

Copy constructor.

Definition at line 161 of file CouenneFeasPumpConstructors.cpp.

CouenneFeasPump::~CouenneFeasPump ( )

virtual

Destructor.

Definition at line 221 of file CouenneFeasPumpConstructors.cpp.

Member Function Documentation

CbcHeuristic * CouenneFeasPump::clone ( ) const

virtual

Clone.

Definition at line 166 of file CouenneFeasPumpConstructors.cpp.

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

Assignment operator.

Definition at line 171 of file CouenneFeasPumpConstructors.cpp.

virtual void Couenne::CouenneFeasPump::resetModel ( CbcModel * model )

inlinevirtual

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

Definition at line 83 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.

void Couenne::CouenneFeasPump::setNumberSolvePerLevel ( int value )

inline

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

Definition at line 95 of file CouenneFeasPump.hpp.

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

virtual

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

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 53 of file CouenneFPSolveMILP.cpp.

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

virtual

obtain solution to NLP

obtain continuous (if fractional) solution

Definition at line 27 of file CouenneFPSolveNLP.cpp.

expression * CouenneFeasPump::updateNLPObj ( const double * iSol )

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

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

Return new objective function

Return new objective function.

Definition at line 235 of file CouenneFeasPumpConstructors.cpp.

bool CouenneFeasPump::fixIntVariables ( const double * sol )

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

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

Returns false if restriction infeasible, true otherwise

Definition at line 428 of file CouenneFeasPumpConstructors.cpp.

void CouenneFeasPump::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions )

static

initialize options to be read later

initialize options

Definition at line 471 of file CouenneFeasPumpConstructors.cpp.

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

find feasible solution (called by solveMILP ())

find a feasible or optimal solution of MILP

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

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

solve MILP

Definition at line 27 of file CouenneFPFindSolution.cpp.

void CouenneFeasPump::init_MILP ( )

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

initialize MILP solvers if needed

Definition at line 108 of file CouenneFPFindSolution.cpp.

void CouenneFeasPump::initIpoptApp ( )

Common code for initializing non-smartptr ipopt application.

Definition at line 31 of file CouenneFeasPumpConstructors.cpp.

CouenneProblem* Couenne::CouenneFeasPump::Problem ( ) const

inline

return pointer to problem

Definition at line 135 of file CouenneFeasPump.hpp.

enum fpCompDistIntType Couenne::CouenneFeasPump::compDistInt ( ) const

inline

return type of MILP solved

Definition at line 139 of file CouenneFeasPump.hpp.

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 145 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multHessNLP ( ) const

inline

weight of Hessian in NLP

Definition at line 146 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multObjFNLP ( ) const

inline

weight of objective in NLP

Definition at line 147 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multDistMILP ( ) const

inline

weight of distance in MILP

Definition at line 149 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multHessMILP ( ) const

inline

weight of Hessian in MILP

Definition at line 150 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multObjFMILP ( ) const

inline

weight of objective in MILP

Definition at line 151 of file CouenneFeasPump.hpp.

CouenneTNLP* Couenne::CouenneFeasPump::nlp ( ) const

inline

return NLP

Definition at line 154 of file CouenneFeasPump.hpp.

int& Couenne::CouenneFeasPump::nCalls ( )

inline

return number of calls (can be changed)

Definition at line 158 of file CouenneFeasPump.hpp.

int CouenneFeasPump::milpPhase	(	double *	nSol,
		double *	iSol
	)

MILP phase of the FP.

Definition at line 38 of file CouenneFPphaseMILP.cpp.

int Couenne::CouenneFeasPump::nlpPhase	(	double *	iSol,
		double *	nSol
	)

NLP phase of the FP.

Member Data Documentation

CouenneProblem* Couenne::CouenneFeasPump::problem_

private

Couenne representation of the problem.

Definition at line 179 of file CouenneFeasPump.hpp.

CouenneCutGenerator* Couenne::CouenneFeasPump::couenneCG_

private

CouenneCutGenerator for linearization cuts.

Definition at line 182 of file CouenneFeasPump.hpp.

CouenneTNLP* Couenne::CouenneFeasPump::nlp_

private

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

Definition at line 193 of file CouenneFeasPump.hpp.

Ipopt::IpoptApplication* Couenne::CouenneFeasPump::app_

private

Ipopt Application pointer for solving NLPs.

Definition at line 196 of file CouenneFeasPump.hpp.

OsiSolverInterface* Couenne::CouenneFeasPump::milp_

private

MILP relaxation of the MINLP (used to find integer, non-NLP-feasible solutions)

Definition at line 200 of file CouenneFeasPump.hpp.

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 205 of file CouenneFeasPump.hpp.

CouenneFPpool* Couenne::CouenneFeasPump::pool_

private

Pool of solutions.

Definition at line 208 of file CouenneFeasPump.hpp.

std::set<CouenneFPsolution, compareSol> Couenne::CouenneFeasPump::tabuPool_

private

Solutions to avoid.

Definition at line 211 of file CouenneFeasPump.hpp.

int* Couenne::CouenneFeasPump::match_

private

matching between reformulation's variables and L-1 norm variables

Definition at line 214 of file CouenneFeasPump.hpp.

int Couenne::CouenneFeasPump::numberSolvePerLevel_

private

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

Definition at line 221 of file CouenneFeasPump.hpp.

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 226 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multHessNLP_

private

weight of Hessian in NLP

Definition at line 227 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multObjFNLP_

private

weight of objective in NLP

Definition at line 228 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multDistMILP_

private

weight of distance in MILP

Definition at line 230 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multHessMILP_

private

weight of Hessian in MILP

Definition at line 231 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::multObjFMILP_

private

weight of objective in MILP

Definition at line 232 of file CouenneFeasPump.hpp.

enum fpCompDistIntType Couenne::CouenneFeasPump::compDistInt_

private

Compute distance from integer variables only, not all variables.

Definition at line 235 of file CouenneFeasPump.hpp.

enum fpCutPlane Couenne::CouenneFeasPump::milpCuttingPlane_

private

Separate convexification cuts during or after MILP.

Definition at line 238 of file CouenneFeasPump.hpp.

int Couenne::CouenneFeasPump::nSepRounds_

private

Number of separation rounds for MILP convexification cuts.

Definition at line 241 of file CouenneFeasPump.hpp.

int Couenne::CouenneFeasPump::maxIter_

private

Maximum iterations per call.

Definition at line 244 of file CouenneFeasPump.hpp.

bool Couenne::CouenneFeasPump::useSCIP_

private

Use SCIP instead of Cbc for solving MILPs.

Definition at line 247 of file CouenneFeasPump.hpp.

int Couenne::CouenneFeasPump::milpMethod_

private

Which SCIP MILP method to use.

Definition at line 250 of file CouenneFeasPump.hpp.

enum fpTabuMgtPolicy Couenne::CouenneFeasPump::tabuMgt_

private

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

Definition at line 253 of file CouenneFeasPump.hpp.

int Couenne::CouenneFeasPump::nCalls_

private

How often should it be called.

Definition at line 256 of file CouenneFeasPump.hpp.

double Couenne::CouenneFeasPump::fadeMult_

private

decrease factor for MILP/NLP multipliers of distance/Hessian/objective

Definition at line 259 of file CouenneFeasPump.hpp.

The documentation for this class was generated from the following files:

/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFeasPump.hpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFeasPump.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFeasPumpConstructors.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFPFindSolution.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFPphaseMILP.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFPphaseNLP.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFPSolveMILP.cpp
/tmp/OS-2.10.2/Couenne/src/heuristics/CouenneFPSolveNLP.cpp

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation