Diving heuristif for MINLPs. More...

#include <MINLPDiving.h>

Inheritance diagram for Minotaur::MINLPDiving:

Collaboration diagram for Minotaur::MINLPDiving:

[legend]

Public Member Functions
	MINLPDiving (EnvPtr env, ProblemPtr p, EnginePtr e)
	default constructor

	~MINLPDiving ()
	default destructor

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

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

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

virtual	~Heuristic ()
	Destroy.

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

Protected Types
typedef UInt(MINLPDiving::*	FuncPtr) (UInt numfrac, const double *x, Direction d, Order o)

Protected Member Functions
void	backtrack_ (UInt n_flipped)
	Backtracking method.

UInt	FracBounds_ (UInt numfrac, const double *x, Direction d, Order o)
	Fractional selection method for fractional variable.

void	getScore_ (const double *x, Scoretype s)
	Get the score of solution.

void	implementDive_ (int i, const double *x, SolutionPoolPtr s_pool)
	Function to implement diving.

UInt	isFrac_ (const double *x)
	The number of fractional variables in current solution.

UInt	LexBounds_ (UInt numfrac, const double *x, Direction d, Order o)
	Lexicographic selection method for fractional variable.

UInt	ReducedCost_ (UInt numfrac, const double *x, Direction d, Order o)
	Reduced cost diving selection method for fractional variable.

void	restoreBounds_ (double LB_copy, double UB_copy, UInt vars)
	Restore the bounds for the problem.

double	rounding_ (double value, Direction d)
	Rounding a value in a given direction.

void	saveBounds_ (double LB_copy, double UB_copy, UInt vars)
	Save bounds of the problem.

FuncPtr	selectHeur_ (int i, Direction &d, Order &o)
	Select the method, ordering and direction.

bool	shouldDive_ ()
	Function to decide on diving or not.

void	sort_ (UInt left, UInt right)
	Sort the score.

void	updateAvgDual_ (ConstSolutionPtr sol)
	Update the average of dual multiplier.

UInt	VectorLength_ (UInt numfrac, const double *x, Direction d, Order o)
	Vector Length selection method for fractional variable.

bool	vectorFlag_ (UInt min_vlength)
	Function to decide on vector length diving.

Protected Attributes
DoubleVector	avgDual_

EnginePtr	e_
	Engine being used to solve the problem.

EnvPtr	env_
	Environment.

double *	gradientObj_
	Gradient of objective function for vector length diving.

double	intTol_

ModVector	lastNodeMods_

LinearHandler *	lh_
	Linear Handler for presolving.

LoggerPtr	logger_
	Logger.

UInt	maxNLP_
	Maximum number of NLPs allowed for diving heuristic.

UInt	maxSol_
	Maximum number of feasible solution required from heuristic.

std::stack< VarBoundModPtr >	mods_

UInt	nSelector_
	Number of method for selection of variables.

ProblemPtr	p_
	Problem to be solved.

DoubleVector	score_
	Violated variable fraction part list.

DivingheurStats *	stats_
	Statistics for the heuristic.

Timer *	timer_
	Timer for this heuristic.

UIntVector	violated_
	violated variable index list

Static Protected Attributes
static const std::string	me_ = "MINLP Diving Heuristic: "

Detailed Description

Diving heuristif for MINLPs.

A Diving Heuristic used to find solutions for Mixed Integer NLPs by solving the Relaxed NLP using an NLP engine. The engine is called once initially to generate a solution which is rounded and used for diving.

Member Function Documentation

◆ backtrack_()

void MINLPDiving::backtrack_ ( UInt n_flipped )

protected

Backtracking method.

Parameters

[in] n_flipped Number of bound changes made in previous dive

All the changes are made by unwinding the modification stack n_flipped number of times

◆ FracBounds_()

UInt MINLPDiving::FracBounds_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o
	)

protected

Fractional selection method for fractional variable.

Parameters

[in]	numfrac	Number of fractional variables in current solution
[in]	x	Constant pointer to primal solution
[in]	d	Direction of rounding
[in]	o	Order for selection of fractional variables

◆ getScore_()

void MINLPDiving::getScore_	(	const double *	x,
		Scoretype	s
	)

protected

Get the score of solution.

Parameters

[in]	x	Const pointer to the primal solution
[in]	s	Scoretype

The score of the solution is determined based on one of the predefined scoretypes.

◆ implementDive_()

void MINLPDiving::implementDive_	(	int	i,
		const double *	x,
		SolutionPoolPtr	s_pool
	)

protected

Function to implement diving.

Parameters

[in]	i	Index of the method number
[in]	x	Const pointer to the root node primal solution
[in]	s_pool	Pointer to the solution pool

Method for selection of fractional variable as candidate for rouding are chosen for diving. Changes made to the problem are stored in the stack of modification.

◆ isFrac_()

UInt MINLPDiving::isFrac_ ( const double * x )

protected

The number of fractional variables in current solution.

Parameters

[in] x Const pointer to primal solution

Returns: Number of fractional variables

◆ LexBounds_()

UInt MINLPDiving::LexBounds_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o
	)

protected

Lexicographic selection method for fractional variable.

Parameters

[in]	numfrac	Number of fractional variables in current solution
[in]	x	Constant pointer to primal solution
[in]	d	Direction of rounding
[in]	o	Order for selection of fractional variables

◆ ReducedCost_()

UInt MINLPDiving::ReducedCost_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o
	)

protected

Reduced cost diving selection method for fractional variable.

Parameters

[in]	numfrac	Number of fractional variables in current solution
[in]	x	Constant pointer to primal solution
[in]	d	Direction of rounding
[in]	o	Order for selection of fractional variables

◆ restoreBounds_()

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

protected

Restore the bounds for the problem.

Parameters

[in]	LB_copy	Pointer to saved bounds
[in]	UB_copt	Pointer to saved bounds
[in]	vars	Number of variables in the problem

◆ rounding_()

double MINLPDiving::rounding_	(	double	value,
		Direction	d
	)

protected

Rounding a value in a given direction.

Parameters

[in]	value	Fractional value to be rounded
[in]	d	Direction to be used for rounding

Returns: rounded value of the fractional variable

◆ saveBounds_()

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

protected

Save bounds of the problem.

Parameters

[in]	LB_copy	Pointer to bounds, space has to be allocated
[in]	UB_copt	Pointer to bounds, space has to be allocated
[in]	vars	Number of variables in the problem

◆ selectHeur_()

MINLPDiving::FuncPtr MINLPDiving::selectHeur_	(	int	i,
		Direction &	d,
		Order &	o
	)

protected

Select the method, ordering and direction.

Parameters

[in]	i	Index of the method number
	d	Reference to direction of rouding
	o	Reference to order for selecting variable

Returns: FuncPtr Address of the selected Diving method

◆ shouldDive_()

bool MINLPDiving::shouldDive_ ( )

protected

Function to decide on diving or not.

return true or false

We decide not to dive is the problem size is large and hessian is dense

◆ solve()

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

virtual

call to heuristic

Implements Minotaur::Heuristic.

◆ sort_()

void MINLPDiving::sort_	(	UInt	left,
		UInt	right
	)

protected

Sort the score.

Parameters

[in]	left	Beginning of the container
[in]	right	End of the container

If the number of non-zero in hessian or number of bin+int <20 don't dive

◆ updateAvgDual_()

void MINLPDiving::updateAvgDual_ ( ConstSolutionPtr sol )

protected

Update the average of dual multiplier.

Parameters

[in] sol Constant Pointer to the solution

◆ VectorLength_()

UInt MINLPDiving::VectorLength_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o
	)

protected

Vector Length selection method for fractional variable.

Parameters

[in]	numfrac	Number of fractional variables in current solution
[in]	x	Constant pointer to primal solution
[in]	d	Direction of rounding
[in]	o	Order for selection of fractional variables

◆ writeStats()

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

virtual

writing the statistics to the logger

Implements Minotaur::Heuristic.

Member Data Documentation

◆ avgDual_

DoubleVector Minotaur::MINLPDiving::avgDual_

protected

Average of dual variables from the previous iterations which is to be used to reduced cost diving

◆ intTol_

double Minotaur::MINLPDiving::intTol_

protected

If a value is this far from an integer, it is considered integer.

◆ lastNodeMods_

ModVector Minotaur::MINLPDiving::lastNodeMods_

protected

Mods implied by bound changes in the previous node's presolve. We only store mods of one node only.

◆ mods_

std::stack<VarBoundModPtr> Minotaur::MINLPDiving::mods_

protected

A stack of modification pointer. All modification are stored in stack and for backtracking the stack is unwinded to restore feasibility

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

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

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Function Documentation

◆ backtrack_()

◆ FracBounds_()

◆ getScore_()

◆ implementDive_()

◆ isFrac_()

◆ LexBounds_()

◆ ReducedCost_()

◆ restoreBounds_()

◆ rounding_()

◆ saveBounds_()

◆ selectHeur_()

◆ shouldDive_()

◆ solve()

◆ sort_()

◆ updateAvgDual_()

◆ VectorLength_()

◆ writeStats()

Member Data Documentation

◆ avgDual_

◆ intTol_

◆ lastNodeMods_

◆ mods_