Feasibility Pump for MINLPs. More...

#include <FeasibilityPump.h>

Inheritance diagram for Minotaur::FeasibilityPump:

Collaboration diagram for Minotaur::FeasibilityPump:

[legend]

Public Member Functions
	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

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

void	writeStats (std::ostream &out) const
	write statistic to the logger More...

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

virtual	~Heuristic ()
	Destroy.

virtual void	solve (NodePtr node, RelaxationPtr rel, SolutionPoolPtr s_pool)=0
	Use this heuristic. More...

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

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

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

void	convertSol_ (SolutionPoolPtr s_pool, ConstSolutionPtr sol)
	Function to convert a solution of the cloned problem to that of an original problem. More...

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

double	hash_ ()
	A function to hash the solutions. More...

virtual void	implementFP_ (const double *x, SolutionPoolPtr s_pool)
	Function to implement the Feasibility Pump method. More...

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

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

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

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

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

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

Protected Attributes
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_ = "Feasibility Pump: "
	Message name for the heuristic.

Detailed Description

Feasibility Pump for MINLPs.

A Feasibility Pump heuristic used to find solutions for Mixed Integer NLPs by solving a relaxed NLP using an NLP engine. After an initial solve a sequence of points are found which are closest to the nearest integer solution obtained by rounding the previous point.

Member Function Documentation

◆ constructObj_()

void FeasibilityPump::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 in Minotaur::LinFeasPump.

◆ convertSol_()

void FeasibilityPump::convertSol_	(	SolutionPoolPtr	s_pool,
		ConstSolutionPtr	sol
	)

protected

Function to convert a solution of the cloned problem to that of an original problem.

Parameters

[in]	s_pool	Pointer to solution pool of original problem
[in]	sol	Solution pointer to the modified (cloned) problem

The binary variables are fixed by changing their bounds in the original problem and then the original problem is resolved to obtain a feasible solution. Bounds are relaxed at the end.

◆ cycle_()

bool FeasibilityPump::cycle_ ( double find_value )

protected

A search function for detection of cycling.

Parameters

[in] find_value Value to be located in a vector containing hash values of already visited rounded solutions

Returns: true If the point already exist implying cycling and false otherwise

◆ hash_()

double FeasibilityPump::hash_ ( )

protected

A function to hash the solutions.

Returns: The hash value of the solution

A hashing function which calculates the inner product of vector x with a FIXED random vector in (0,1]^n. This function uses the roundedSol_ vector and random_ vector to calculate the hash value

◆ implementFP_()

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

protectedvirtual

Function to implement the Feasibility Pump method.

Parameters

[in]	Constant	pointer to primal solution
[in]	Pointer	to solution pool

Reimplemented in Minotaur::LinFeasPump.

◆ isFrac_()

bool FeasibilityPump::isFrac_ ( const double * x )

protected

Function to check the integrality of a variable.

Parameters

[in] Constant pointer to the primal solution

return true if there is any fractional variable else false

◆ perturb_()

void FeasibilityPump::perturb_	(	double	hash_val,
		UInt	n_to_flip
	)

protected

A function to perturb the rounded solution in case of cycling.

Parameters

[in]	hash_val	Hash value of the current rounded solution
[in]	n_to_flip	Number of variables to be flipped

This function uses selectToFlip_ to get candidates for flipping till a new rounded solution is obtained which is not visited earlier. Cycling_ is used to detect earlier existence. The parameter n_to_flip is passed by the calling method is usually an indicator of integer infeasibilities of the solution.

◆ restoreBounds_()

void FeasibilityPump::restoreBounds_	(	double *	LB_copy,
		double *	UB_copy,
		UInt	vars
	)

protected

A function to restore the upper and lower bounds of the problem.

Parameters

[in]	LB_copy.	Pointer to an array of lower bound.
[in]	UB_copy.	Pointer to an array of upper bound.
[in]	numvars.	Number of variables in the problem.

◆ saveBounds_()

void FeasibilityPump::saveBounds_	(	double *	LB_copy,
		double *	UB_copy,
		UInt	vars
	)

protected

A function to save the upper and lower bounds of the problem.

Parameters

[in]	LB_copy.	Pointer to an array of lower bound. Space has to be allocated.
[in]	UB_copy.	Pointer to an array of upper bound. Space has to be allocated.
[in]	numvars.	Number of variables in the problem.

◆ selectToFlip_()

VarVector FeasibilityPump::selectToFlip_ ( UInt n_to_flip )

protected

A funtion to randomly select "n" binary/integer variable to be flipped.

Parameters

[in] n_to_flip Number of variables to be flipped

Returns: The vector of pointer to the variables selected as candidate

This function uses random sampling for selection of variables as a candidate for be flipped from 0 to 1 or 1 to 0.

◆ shouldFP_()

bool FeasibilityPump::shouldFP_ ( )

protectedvirtual

Function to decide whether to use Feasibility Pump.

return true or false.

We decide not to use Feasibility Pump is problem has integer variables and/or if the problem is nonlinear (constraints or objective)

Reimplemented in Minotaur::LinFeasPump.

◆ solve()

void FeasibilityPump::solve	(	NodePtr	node,
		RelaxationPtr	rel,
		SolutionPoolPtr	s_pool
	)

virtual

call to the heuristic

Implements Minotaur::Heuristic.

Reimplemented in Minotaur::LinFeasPump.

◆ writeStats()

void FeasibilityPump::writeStats ( std::ostream & out ) const

virtual

write statistic to the logger

Implements Minotaur::Heuristic.

Reimplemented in Minotaur::LinFeasPump.

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

/home/amahajan/tmp/minotaur-test/src/base/FeasibilityPump.h
/home/amahajan/tmp/minotaur-test/src/base/FeasibilityPump.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Function Documentation

◆ constructObj_()

◆ convertSol_()

◆ cycle_()

◆ hash_()

◆ implementFP_()

◆ isFrac_()

◆ perturb_()

◆ restoreBounds_()

◆ saveBounds_()

◆ selectToFlip_()

◆ shouldFP_()

◆ solve()

◆ writeStats()