Linear Feasibility Pump for MINLPs. More...

#include <LinFeasPump.h>

Inheritance diagram for Minotaur::LinFeasPump:

[legend]

Collaboration diagram for Minotaur::LinFeasPump:

[legend]

Public Member Functions
	LinFeasPump (EnvPtr env, ProblemPtr p, EnginePtr e1, EnginePtr e2)
	Default constructor.

	~LinFeasPump ()
	Default destructor.

void	solve (NodePtr node, RelaxationPtr rel, SolutionPoolPtr s_pool)
	Call to the heuristic.

void	writeStats (std::ostream &out) const
	Write statistics to the logger.

Public Member Functions inherited from Minotaur::FeasibilityPump
	FeasibilityPump (EnvPtr env, ProblemPtr p, EnginePtr e)
	default constructor

	FeasibilityPump (EnvPtr env, ProblemPtr p, EnginePtr nlpe, EnginePtr e)
	constructor for derived class

virtual	~FeasibilityPump ()
	default destructor

Public Member Functions inherited from Minotaur::Heuristic
	Heuristic ()
	Default constructor.

virtual	~Heuristic ()
	Destroy.

virtual void	solveNode (ConstSolutionPtr, NodePtr, RelaxationPtr, SolutionPoolPtr)
	Use this heuristic.

Protected Member Functions
void	constructObj_ (ProblemPtr prob, ConstSolutionPtr sol)
	Function to construct/update the objective function.

void	implementFP_ (const double *x, SolutionPoolPtr s_pool)
	Fucntion to implement the linear feasibility pump.

double	getSolGap_ (double f_nlp, double f_feas)
	Calculate the gap between the NLP relaxation solution and integer feasible solution.

bool	prepareLP_ (SolutionPool *sp)
	A function to prepare the linear relaxation.

void	separatingCut_ (double f_nlp, SolutionPoolPtr s_pool)
	This function makes a cut by including the objective as constraint.

bool	shouldFP_ ()
	Function to decide whether to use Linear Feasibility Pump.

Protected Member Functions inherited from Minotaur::FeasibilityPump
void	convertSol_ (SolutionPoolPtr s_pool, ConstSolutionPtr sol)
	Function to convert a solution of the cloned problem to that of an original problem.

bool	cycle_ (double find_value)
	A search function for detection of cycling.

double	hash_ ()
	A function to hash the solutions.

bool	isFrac_ (const double *x)
	Function to check the integrality of a variable.

void	perturb_ (double hash_val, UInt n_to_flip)
	A function to perturb the rounded solution in case of cycling.

void	restoreBounds_ (double LB_copy, double UB_copy, UInt vars)
	A function to restore the upper and lower bounds of the problem.

void	saveBounds_ (double LB_copy, double UB_copy, UInt vars)
	A function to save the upper and lower bounds of the problem.

VarVector	selectToFlip_ (UInt n_to_flip)
	A funtion to randomly select "n" binary/integer variable to be flipped.

Protected Attributes
double *	gradientObj_
	gradient of the objective function

LinHandlerPtr	lh_
	Linear Handler pointer.

EnginePtr	lpE_
	LP Engine to be used to solving linear relaxation.

ConstraintPtr	objConstraint_
	objective improvement constraint pointer

VariablePtr	objVar_

LinearFunctionPtr	olfClone_
	clone of linear objective function

QGHandlerPtr	qh_
	QG Handler.

RelaxationPtr	r_
	Relaxation Pointer.

LinFeasStats *	statsLFP_
	Statistics.

Protected Attributes inherited from Minotaur::FeasibilityPump
VarVector	bins_
	Binary/integer variables present in the problem.

EnginePtr	e_
	Pointer to the engine to be used to solve the problem.

EnvPtr	env_
	Pointer to the environment.

DoubleVector	hashVal_
	Vector for hash value of solutions.

double	intTol_
	Tolerance for a number to be considered as an integer.

LoggerPtr	logger_
	Pointer to the logger.

UInt	nToFlip_
	Number of variables to be flipped if cycling is detected.

ProblemPtr	p_
	Pointer to the problem being solved.

DoubleVector	random_
	A random vector for inner product with the solution.

DoubleVector	roundedSol_
	Vector of rounded solution.

FeasPumpStats *	stats_
	Statistics for the Feasibility Pump heuristic.

Timer *	timer_
	Timer of the heuristic.

Static Protected Attributes
static const std::string	me_ = "Linear Feas Pump: "
	Message name for the heuristic.

Static Protected Attributes inherited from Minotaur::FeasibilityPump
static const std::string	me_ = "Feasibility Pump: "
	Message name for the heuristic.

Detailed Description

Linear Feasibility Pump for MINLPs.

A Linear Feasibility Pump heuristic used to find solutions for Mixed Integer NLPs by solving a linear relaxation of NLP using a LP engine. An NLP is solved after every "n" iterations and solution from NLP solve is used to construct a LP relaxation. This class is derived from the class FeasibilityPump.

Constructor & Destructor Documentation

◆ LinFeasPump()

LinFeasPump::LinFeasPump	(	EnvPtr	env,
		ProblemPtr	p,
		EnginePtr	e1,
		EnginePtr	e2
	)

Default constructor.

Parameters

[in]	env	Environment pointer
[in]	p	Problem pointer
[in]	e1	The NLP engine pointer
	[in[	e2 The LP engine pointer

The constructor initializes the base class using env, p and e1 and uses e2 to initialize the LP engine. Logger of the base is also defined in this function.

Member Function Documentation

◆ constructObj_()

void LinFeasPump::constructObj_	(	ProblemPtr	prob,
		ConstSolutionPtr	sol
	)

protectedvirtual

Function to construct/update the objective function.

Parameters

[in]	prob	Pointer to the cloned problem
[in]	sol	Pointer to the solution of relaxation that was previously solved.

This function selects the variable which are fractional and construct the objective function out of such variables. The new objective function replaces the objective of the problem passed

Reimplemented from Minotaur::FeasibilityPump.

◆ getSolGap_()

double LinFeasPump::getSolGap_	(	double	f_nlp,
		double	f_feas
	)

protected

Calculate the gap between the NLP relaxation solution and integer feasible solution.

Parameters

[in]	f_nlp	nlp solution value.
[in]	x	const pointer to integer feasible solution.

Returns: gap. gap is given by $\frac{f(x)-f(x_nlp)}{|f(x)|+1e-6}$

◆ implementFP_()

void LinFeasPump::implementFP_	(	const double *	x,
		SolutionPoolPtr	s_pool
	)

protectedvirtual

Fucntion to implement the linear feasibility pump.

Parameters

[in]	s_pool	Pointer to solution pool
[in]	x	Is not required. Can be NULL.

Reimplemented from Minotaur::FeasibilityPump.

◆ prepareLP_()

bool LinFeasPump::prepareLP_ ( SolutionPool * sp )

protected

A function to prepare the linear relaxation.

Returns: True if problem is infeasible else false

This function first initializes the Linear Handler and QG Handler which are then used to construct a linear relaxation from the original problem

◆ separatingCut_()

void LinFeasPump::separatingCut_	(	double	f_nlp,
		SolutionPoolPtr	s_pool
	)

protected

This function makes a cut by including the objective as constraint.

Parameters

[in]	f_nlp	NLP solution value solution
[in]	x	const pointer to the primal feasible solution

If a feasible solution is found we add an additional constraint to the problem to force the heuristic to find a better feasible fucntion. The constraint added is a linear relaxation of the objective at the feasible point, i.e. $\nabla f(x^{LP}) + (x-x^{LP}) < 0$