Parallel Diving heuristic for MINLPs. More...

#include <ParMINLPDiving.h>

Inheritance diagram for Minotaur::ParMINLPDiving:

Collaboration diagram for Minotaur::ParMINLPDiving:

[legend]

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

	~ParMINLPDiving ()
	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

void	writeParStats (std::ostream &out, DivingheurStats *stats, double wallTime) const
	writing the statistics to the logger

virtual std::string	getDirectionString (UInt i)
	Return a string that describes the rounding direction in simple words.

virtual std::string	getScoreString (UInt i)
	Return a string that describes the scoring rule in simple words.

virtual std::string	getOrderString (UInt i)
	Return a string that describes the rounding order in simple words.

void	setAltEngine (EnginePtr nlpe)
	Set the alternate (typically NLP) engine pointer.

void	setOrigProb (ProblemPtr minlp)
	Set the original problem pointer.

void	solveNLP (ConstSolutionPtr sol, bool *solFound, ProblemPtr minlp, EnginePtr nlpe)
	Solve NLP at LP integer feasible solution.

void	fixInts (const double x, std::stack< Modification > &nlpMods, ProblemPtr minlp)
	Fix integer variables as in x.

void	unfixInts (std::stack< Modification * > &nlpMods, ProblemPtr minlp)

double	getWallTime ()
	Get wall clock time.

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(ParMINLPDiving::*	FuncPtr) (UInt numfrac, const double x, Direction d, Order o, ProblemPtr p, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, ModVector &lastNodeMods, DoubleVector &score, DoubleVector &avgDual, double *gradientObj)

Protected Member Functions
void	backtrack_ (UInt n_moded, ModVector &lastNodeMods, ProblemPtr p, std::stack< VarBoundModPtr > &mods)
	Backtracking method.

UInt	FracBounds_ (UInt numfrac, const double x, Direction d, Order o, ProblemPtr p, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, ModVector &lastNodesMods, DoubleVector &score, DoubleVector &avgDual, double *gradientObj)
	Fractional selection method for fractional variable.

void	getScore_ (const double x, Scoretype s, DoubleVector &score, ProblemPtr p, DoubleVector &avgDual, double gradientObj)
	Get the score of solution.

void	implementDive_ (int i, const double x, SolutionPoolPtr s_pool, ModVector &lastNodesMods, EnginePtr e, ProblemPtr p, DoubleVector &avgDual, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, DoubleVector &score, double gradientObj, DivingheurStats stats)
	Function to implement diving.

UInt	isFrac_ (const double *x, UIntVector &violated, ProblemPtr p)
	The number of fractional variables in current solution.

UInt	LexBounds_ (UInt numfrac, const double x, Direction d, Order o, ProblemPtr p, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, ModVector &lastNodesMods, DoubleVector &score, DoubleVector &avgDual, double *gradientObj)
	Lexicographic selection method for fractional variable.

UInt	ReducedCost_ (UInt numfrac, const double x, Direction d, Order o, ProblemPtr p, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, ModVector &lastNodesMods, DoubleVector &score, DoubleVector &avgDual, double *gradientObj)
	Reduced cost diving selection method for fractional variable.

void	restoreBounds_ (double LB_copy, double UB_copy, UInt vars, ProblemPtr p)
	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, DoubleVector &score, UIntVector &violated)
	Sort the score.

void	updateAvgDual_ (ConstSolutionPtr sol, DoubleVector &avgDual, DivingheurStats *stats)
	Update the average of dual multiplier.

UInt	VectorLength_ (UInt numfrac, const double x, Direction d, Order o, ProblemPtr p, UIntVector &violated, std::stack< VarBoundModPtr > &mods, LinearHandler lh, ModVector &lastNodesMods, DoubleVector &score, DoubleVector &avgDual, double *gradientObj)
	Vector Length selection method for fractional variable.

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

Protected Attributes
EnginePtr	e_
	Engine being used to solve the problems during dive.

EnginePtr	nlpe_
	NLP Engine (required only if e_ is LP Engine)

EnvPtr	env_
	Environment.

double	intTol_
	Gradient of objective function for vector length diving.

LoggerPtr	logger_
	Linear Handler for presolving.

UInt	maxProbs_
	Maximum number of problem-solves allowed for each thread.

UInt	maxSol_
	Maximum number of feasible solution required from heuristic.

UInt	nSelector_
	Number of method for selection of variables.

UInt	numThreads_
	Number of threads to be used for the heuristic.

ProblemPtr	minlp_
	Original problem (required only if p_ is LP relaxation)

ProblemPtr	p_
	Problem to be solved.

DivingheurStats *	stats_
	Violated variable fraction part list.

Timer *	timer_
	Timer for this heuristic.

double	wallTimeStart_
	violated variable index list

UInt	numLevels_
	Number of subsets to fix the fractional variables in each round.

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

Detailed Description

Parallel Diving heuristic for MINLPs.

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

Member Function Documentation

◆ backtrack_()

void ParMINLPDiving::backtrack_	(	UInt	n_moded,
		ModVector &	lastNodeMods,
		ProblemPtr	p,
		std::stack< VarBoundModPtr > &	mods
	)

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 ParMINLPDiving::FracBounds_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o,
		ProblemPtr	p,
		UIntVector &	violated,
		std::stack< VarBoundModPtr > &	mods,
		LinearHandler *	lh,
		ModVector &	lastNodesMods,
		DoubleVector &	score,
		DoubleVector &	avgDual,
		double *	gradientObj
	)

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 ParMINLPDiving::getScore_	(	const double *	x,
		Scoretype	s,
		DoubleVector &	score,
		ProblemPtr	p,
		DoubleVector &	avgDual,
		double *	gradientObj
	)

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 ParMINLPDiving::implementDive_	(	int	i,
		const double *	x,
		SolutionPoolPtr	s_pool,
		ModVector &	lastNodesMods,
		EnginePtr	e,
		ProblemPtr	p,
		DoubleVector &	avgDual,
		UIntVector &	violated,
		std::stack< VarBoundModPtr > &	mods,
		LinearHandler *	lh,
		DoubleVector &	score,
		double *	gradientObj,
		DivingheurStats *	stats
	)

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 ParMINLPDiving::isFrac_	(	const double *	x,
		UIntVector &	violated,
		ProblemPtr	p
	)

protected

The number of fractional variables in current solution.

Parameters

[in] x Const pointer to primal solution

Returns: Number of fractional variables

◆ LexBounds_()

UInt ParMINLPDiving::LexBounds_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o,
		ProblemPtr	p,
		UIntVector &	violated,
		std::stack< VarBoundModPtr > &	mods,
		LinearHandler *	lh,
		ModVector &	lastNodesMods,
		DoubleVector &	score,
		DoubleVector &	avgDual,
		double *	gradientObj
	)

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 ParMINLPDiving::ReducedCost_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o,
		ProblemPtr	p,
		UIntVector &	violated,
		std::stack< VarBoundModPtr > &	mods,
		LinearHandler *	lh,
		ModVector &	lastNodesMods,
		DoubleVector &	score,
		DoubleVector &	avgDual,
		double *	gradientObj
	)

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 ParMINLPDiving::restoreBounds_	(	double *	LB_copy,
		double *	UB_copy,
		UInt	vars,
		ProblemPtr	p
	)

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 ParMINLPDiving::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 ParMINLPDiving::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_()

ParMINLPDiving::FuncPtr ParMINLPDiving::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 ParMINLPDiving::shouldDive_ ( )

protected

Function to decide on diving or not.

return true or false

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

◆ solve()

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

virtual

call to heuristic

Implements Minotaur::Heuristic.

◆ sort_()

void ParMINLPDiving::sort_	(	UInt	left,
		UInt	right,
		DoubleVector &	score,
		UIntVector &	violated
	)

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 ParMINLPDiving::updateAvgDual_	(	ConstSolutionPtr	sol,
		DoubleVector &	avgDual,
		DivingheurStats *	stats
	)

protected

Update the average of dual multiplier.

Parameters

[in] sol Constant Pointer to the solution

◆ VectorLength_()

UInt ParMINLPDiving::VectorLength_	(	UInt	numfrac,
		const double *	x,
		Direction	d,
		Order	o,
		ProblemPtr	p,
		UIntVector &	violated,
		std::stack< VarBoundModPtr > &	mods,
		LinearHandler *	lh,
		ModVector &	lastNodesMods,
		DoubleVector &	score,
		DoubleVector &	avgDual,
		double *	gradientObj
	)

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 ParMINLPDiving::writeStats ( std::ostream & out ) const

virtual

writing the statistics to the logger

Implements Minotaur::Heuristic.

Member Data Documentation

◆ e_

EnginePtr Minotaur::ParMINLPDiving::e_

protected

Engine being used to solve the problems during dive.

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

◆ intTol_

double Minotaur::ParMINLPDiving::intTol_

protected

Gradient of objective function for vector length diving.

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

◆ logger_

LoggerPtr Minotaur::ParMINLPDiving::logger_

protected

Linear Handler for presolving.

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

◆ nSelector_

UInt Minotaur::ParMINLPDiving::nSelector_

protected

Number of method for selection of variables.

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

◆ stats_

DivingheurStats* Minotaur::ParMINLPDiving::stats_

protected

Violated variable fraction part list.

Statistics for the heuristic

◆ wallTimeStart_

double Minotaur::ParMINLPDiving::wallTimeStart_

protected

violated variable index list

Wall time start

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

/home/amahajan/tmp/minotaur-test/src/base/ParMINLPDiving.h
/home/amahajan/tmp/minotaur-test/src/base/ParMINLPDiving.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

◆ e_

◆ intTol_

◆ logger_

◆ nSelector_

◆ stats_

◆ wallTimeStart_