#include <LinearHandler.h>

Inheritance diagram for Minotaur::LinearHandler:

Collaboration diagram for Minotaur::LinearHandler:

[legend]

Public Member Functions
	LinearHandler ()
	Default constructor.

	LinearHandler (EnvPtr env, ProblemPtr problem)
	Constructor.

	~LinearHandler ()
	Destroy.

void	relaxInitFull (RelaxationPtr rel, SolutionPool sp, bool is_inf)
	Create root relaxation if doing full node relaxations. More...

void	relaxInitInc (RelaxationPtr rel, SolutionPool sp, bool is_inf)
	Create root relaxation if doing incremental node relaxations. More...

void	relaxNodeFull (NodePtr node, RelaxationPtr rel, bool *is_inf)
	Create a relaxation for a node, building from scratch. More...

void	relaxNodeInc (NodePtr node, RelaxationPtr rel, bool *is_inf)
	Create an incremental relaxation for a node. More...

bool	isFeasible (ConstSolutionPtr, RelaxationPtr, bool &, double &)

bool	isNeeded ()
	Return true if this handler is needed for the problem. More...

void	separate (ConstSolutionPtr sol, NodePtr node, RelaxationPtr rel, CutManager cutman, SolutionPoolPtr s_pool, ModVector &p_mods, ModVector &r_mods, bool sol_found, SeparationStatus *status)

virtual void	getBranchingCandidates (RelaxationPtr, const DoubleVector &, ModVector &, BrVarCandSet &, BrCandVector &, bool &)
	Does nothing. More...

virtual ModificationPtr	getBrMod (BrCandPtr, DoubleVector &, RelaxationPtr, BranchDirection)
	Does nothing. More...

virtual Branches	getBranches (BrCandPtr, DoubleVector &, RelaxationPtr, SolutionPoolPtr)
	Does nothing. More...

virtual SolveStatus	presolve (PreModQ pre_mods, bool changed, Solution **sol)
	Initial presolve. More...

virtual bool	presolveNode (RelaxationPtr p, NodePtr node, SolutionPoolPtr s_pool, ModVector &p_mods, ModVector &r_mods)
	Presolve the problem and its relaxation at a node. More...

virtual std::string	getName () const
	Return the name of the handler. More...

const LinPresolveOpts *	getOpts () const
	Return a constant pointer to the presolve options.

void	setPreOptMaxIters (int val)
	Maximum number of iterations.

void	setPreOptPurgeVars (bool val)
	If True, purge fixed variables.

void	setPreOptPurgeCons (bool val)
	If True, purge redundant constraints.

void	setPreOptDualFix (bool val)

void	setPreOptCoeffImp (bool val)

void	simplePresolve (ProblemPtr p, SolutionPoolPtr spool, ModVector &t_mods, SolveStatus &status)

void	writePreStats (std::ostream &out) const
	Write the presolve statistics.

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

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

virtual	~Handler ()
	Destroy.

virtual void	addConstraint (ConstraintPtr newcon)
	Add constraint to be handled by this handler. More...

virtual ConstraintVector::const_iterator	consBegin () const

virtual ConstraintVector::const_iterator	consEnd () const

virtual int	fixNodeErr (RelaxationPtr, ConstSolutionPtr, SolutionPoolPtr, bool &)

virtual Branches	getBranches (BrCandPtr cand, DoubleVector &x, RelaxationPtr rel, SolutionPoolPtr s_pool)=0
	Return branches for branching. More...

virtual void	getBranchingCandidates (RelaxationPtr rel, const DoubleVector &x, ModVector &mods, BrVarCandSet &cands, BrCandVector &gencands, bool &is_inf)=0
	find branching candidates. More...

virtual ModificationPtr	getBrMod (BrCandPtr cand, DoubleVector &x, RelaxationPtr rel, BranchDirection dir)=0
	Get the modifcation that creates a given (up or down) branch. More...

virtual std::string	getName () const =0
	Return the name of the handler. More...

bool	getStrongerMods (RelaxationPtr rel, NodePtr node, SolutionPoolPtr s_pool, ModVector &p_mods, ModVector &r_mods)
	do node presolve to get mods for stronger branching All params are presolveNode params.

virtual bool	isFeasible (ConstSolutionPtr sol, RelaxationPtr rel, bool &should_prune, double &inf_meas)=0
	Check if a solution is feasible. More...

virtual bool	isNeeded ()
	Return true if this handler is needed for the problem. More...

virtual SolveStatus	presolve (PreModQ pre_mods, bool changed, Solution **sol)=0
	Initial presolve. More...

virtual bool	presolveNode (RelaxationPtr rel, NodePtr node, SolutionPoolPtr s_pool, ModVector &p_mods, ModVector &r_mods)=0
	Presolve the problem and its relaxation at a node. More...

virtual bool	postSolveRootNode (RelaxationPtr, SolutionPoolPtr, ConstSolutionPtr, ModVector &, ModVector &)
	At the root node post solve the problem and its relaxation. LP based bound tightening (OBBT) is employed here after filtering variables for which no OBBT is required. More...

virtual void	relaxInitFull (RelaxationPtr rel, SolutionPool sp, bool is_inf)=0
	Create root relaxation if doing full node relaxations. More...

virtual void	relaxInitInc (RelaxationPtr rel, SolutionPool sp, bool is_inf)=0
	Create root relaxation if doing incremental node relaxations. More...

virtual void	relaxNodeFull (NodePtr node, RelaxationPtr rel, bool *is_inf)=0
	Create a relaxation for a node, building from scratch. More...

virtual void	relaxNodeInc (NodePtr node, RelaxationPtr rel, bool *is_inf)=0
	Create an incremental relaxation for a node. More...

virtual void	removeCuts (RelaxationPtr, ConstSolutionPtr)

virtual void	separate (ConstSolutionPtr sol, NodePtr node, RelaxationPtr rel, CutManager cutman, SolutionPoolPtr s_pool, ModVector &p_mods, ModVector &r_mods, bool sol_found, SeparationStatus *status)=0
	add cuts to separate a given point. More...

virtual void	setModFlags (bool mod_prob, bool mod_rel)
	Tell the handler whether the problem will be modified or the relaxation will be modified or both. These modifications will be saved in the tree as well. More...

virtual void	simplePresolve (ProblemPtr, SolutionPoolPtr, ModVector &, SolveStatus &status)

void	undoStrongerMods (ProblemPtr p, RelaxationPtr rel, ModVector &p_mods, ModVector &r_mods)
	Undo Modifications made during stronger branching. More...

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

Protected Member Functions
void	chkIntToBin_ (VariablePtr v)

void	chkSing_ (bool *changed)
	Find variables that appear in exactly one constraint in linear form and do not appear in objective. Such a variable can be removed after changing the bounds on the constraint. More...

void	coeffImp_ (bool *changed)

void	computeImpBounds_ (ConstraintPtr c, VariablePtr z, double zval, double lb, double ub)

void	copyBndsFromRel_ (RelaxationPtr rel, ModVector &p_mods)

void	delFixedVars_ (bool *changed)

void	dualFix_ (bool *changed)

void	domRows_ (bool *changed)

void	dupRows_ (bool *changed)

SolveStatus	checkBounds_ (ProblemPtr p)
	check if lb <= ub for all variables and constraints.

void	changeBFlag_ (VariablePtr v)
	change constraints flag for presolve

void	findLinVars_ ()

void	findAllBinCons_ ()

void	fixToCont_ ()

void	getLfBnds_ (LinearFunctionPtr lf, double lo, double up)

void	getSingLfBnds_ (LinearFunctionPtr lf, double lo, double up)

SolveStatus	linBndTighten_ (ProblemPtr p, bool apply_to_prob, ConstraintPtr c_ptr, bool changed, ModQ mods, UInt *nintmods)

void	purgeVars_ (PreModQ *pre_mods)

void	relax_ (ProblemPtr p, RelaxationPtr rel, bool *is_inf)
	Common routine for building relaxation by copying all the linear constraints and variable-bounds from a given problem. More...

void	substVars_ (bool changed, PreModQ pre_mods)

void	tightenInts_ (ProblemPtr p, bool apply_to_prob, bool changed, ModQ mods)
	Round the bounds. More...

bool	treatDupRows_ (ConstraintPtr c1, ConstraintPtr c2, double mult, bool *changed)

void	updateLfBoundsFromLb_ (ProblemPtr p, bool apply_to_prob, LinearFunctionPtr lf, double lb, double uu, bool is_sing, bool changed, ModQ mods, UInt *nintmods)

void	updateLfBoundsFromUb_ (ProblemPtr p, bool apply_to_prob, LinearFunctionPtr lf, double ub, double ll, bool is_sing, bool changed, ModQ mods, UInt *nintmods)

SolveStatus	varBndsFromCons_ (ProblemPtr p, bool apply_to_prob, bool changed, ModQ mods, UInt *nintmods)

SolveStatus	varBndsFromObj_ (ProblemPtr p, double ub, bool apply_to_prob, bool changed, ModQ mods)

Protected Attributes
EnvPtr	env_
	Environment.

ProblemPtr	problem_
	The problem for which the handler was created.

LoggerPtr	logger_
	Log.

const double	intTol_
	Tolerance for checking integrality. More...

bool	chkDupRows_
	If true, dupRows_ is run in presolve.

const double	eTol_
	Tolerance.

const double	infty_
	Infinity. Bounds beyond this number are treated as infinity.

LinPresolveStats *	pStats_
	Statistics of presolve.

LinPresolveOpts *	pOpts_
	Options for presolve.

VarQueue	linVars_

Protected Attributes inherited from Minotaur::Handler
ConstraintVector	cons_

bool	modProb_
	If true, modify the original (or transformed) problem.

bool	modRel_
	If true, modify the relaxation of original (or transformed) problem.

Static Protected Attributes
static const std::string	me_ = "LinearHandler: "
	For log.

Detailed Description

An LinearHandler handles variables of a problem. It only checks bounds and integrality of the variables.

Member Function Documentation

◆ chkSing_()

void LinearHandler::chkSing_ ( bool * changed )

protected

Find variables that appear in exactly one constraint in linear form and do not appear in objective. Such a variable can be removed after changing the bounds on the constraint.

Parameters

[out] changed Set to true if some such variables are found and fixed.

◆ getBranches()

virtual Branches Minotaur::LinearHandler::getBranches	(	BrCandPtr	,
		DoubleVector &	,
		RelaxationPtr	,
		SolutionPoolPtr
	)

inlinevirtual

Does nothing.

Implements Minotaur::Handler.

◆ getBranchingCandidates()

virtual void Minotaur::LinearHandler::getBranchingCandidates	(	RelaxationPtr	,
		const DoubleVector &	,
		ModVector &	,
		BrVarCandSet &	,
		BrCandVector &	,
		bool &
	)

inlinevirtual

Does nothing.

Implements Minotaur::Handler.

◆ getBrMod()

virtual ModificationPtr Minotaur::LinearHandler::getBrMod	(	BrCandPtr	,
		DoubleVector &	,
		RelaxationPtr	,
		BranchDirection
	)

inlinevirtual

Does nothing.

Implements Minotaur::Handler.

◆ getName()

std::string LinearHandler::getName ( ) const

virtual

Return the name of the handler.

Implements Minotaur::Handler.

◆ isFeasible()

bool Minotaur::LinearHandler::isFeasible	(	ConstSolutionPtr	,
		RelaxationPtr	,
		bool &	,
		double &
	)

inlinevirtual

We assume that linear constraints and bound constraints are always satisfied. Always return true.

Implements Minotaur::Handler.

◆ isNeeded()

bool Minotaur::LinearHandler::isNeeded ( )

inlinevirtual

Return true if this handler is needed for the problem.

It is useful to know if a handler is required or not. For example, a handler may be deleted if it is not needed.

Reimplemented from Minotaur::Handler.

◆ presolve()

SolveStatus LinearHandler::presolve	(	PreModQ *	pre_mods,
		bool *	changed,
		Solution **	sol
	)

virtual

Initial presolve.

Do the initial presolve. For now we will assume that presolve modifies the given problem. We do not create a new problem. All modifications that require post-processing for getting the solution back are prepended to 'pre_mods' by the handler.

Parameters

[in]	pre_mods	A pointer to a queue of PreMod objects. Modifications made by the presolver must be prepended (not appended) to pre_mods. The order is important for post-solve.
[out]	changed	True if the presolve modified the problem.

Returns: status of presolve.

Parameters

[out] sol Optimal solution found by the handler, if any. The status must be SolvedOptimal if and only if sol is created.

Implements Minotaur::Handler.

◆ presolveNode()

bool LinearHandler::presolveNode	(	RelaxationPtr	rel,
		NodePtr	node,
		SolutionPoolPtr	s_pool,
		ModVector &	p_mods,
		ModVector &	r_mods
	)

virtual

Presolve the problem and its relaxation at a node.

Presolve the problem and its relaxation at a given node. Bound propagation and other simple modifications can be made in this function. It is called after the node relaxation is setup but before it is solved. Both the problem and its relaxation are presolved. Changes to the problem are stored in the tree. Changes to the relaxation are optional and may or may not be stored in the tree.

Parameters

[in]	rel	Relaxation at the current node.
[in]	node	Current node.
[in]	s_pool	Pool of solutions.
[in]	p_mods	Unused. Modifications to the problem that must be stored in this node so that they are applied to all descendant nodes as well. All modifications must be appended not prepended.
[out]	r_mods	Modifications to the relaxation that must be stored in this node so that they are applied to all descendant nodes as well. All modifications must be appended not prepended. This may be unnecessary in certain algorithms.

Returns: true if Node can be pruned because infeasibility is detected.

Implements Minotaur::Handler.

◆ relax_()

void LinearHandler::relax_	(	ProblemPtr	p,
		RelaxationPtr	rel,
		bool *	is_inf
	)

protected

Common routine for building relaxation by copying all the linear constraints and variable-bounds from a given problem.

Parameters

[in]	p	The problem whose relaxation we want to create.
[in]	rel	The relaxation in which we want to add new variables and constraints.
[out]	is_inf	True if problem p is found to be infeasible, false otherwise.

◆ relaxInitFull()

void LinearHandler::relaxInitFull	(	RelaxationPtr	rel,
		SolutionPool *	sp,
		bool *	is_inf
	)

virtual

Create root relaxation if doing full node relaxations.

This method is used to add all the variables and constraints handled by this handler, with the understanding that nodes will also be fully rebuilt. The relaxation is already created, it should not be freed or re-allocated.

Parameters

[in,out]	rel	The relaxation that is being constructed.
[in]	Solution	pool for storing any new solutions found.
[out]	is_inf	is true if the handler finds that the problem is infeasible.

Implements Minotaur::Handler.

◆ relaxInitInc()

void LinearHandler::relaxInitInc	(	RelaxationPtr	rel,
		SolutionPool *	sp,
		bool *	is_inf
	)

virtual

Create root relaxation if doing incremental node relaxations.

This method is used to add all the variables and constraints handled by this handler, with the understanding that nodes will incrementally relaxed. The relaxation is already created, it should not be freed or re-allocated.

Parameters

[in,out]	rel	The relaxation that is being constructed.
[in]	Solution	pool for storing any new solutions found.
[out]	is_inf	is true if the handler finds that the problem is infeasible.

Implements Minotaur::Handler.

◆ relaxNodeFull()

void LinearHandler::relaxNodeFull	(	NodePtr	node,
		RelaxationPtr	rel,
		bool *	is_inf
	)

virtual

Create a relaxation for a node, building from scratch.

Create a relaxation of the constraints. Either this method, or relaxNodeInc should be called at each node. Here, we only make minor modifications to the same relaxation.

Parameters

[in]	node	is the node for which relaxation is to be created.
[in]	rel	is the relaxation that is being constructed. Do not allocate or re-allocate space for it. Just add new variables or constraints to it.
[out]	is_inf	is true if the node can be pruned.

Implements Minotaur::Handler.

◆ relaxNodeInc()

void LinearHandler::relaxNodeInc	(	NodePtr	node,
		RelaxationPtr	rel,
		bool *	is_inf
	)

virtual

Create an incremental relaxation for a node.

Create a relaxation of the constraints. Either this method, or nodeRelaxFull relax should be called at root node. Usually we only make minor modifications to the same relaxation.

Parameters

[in]	node	is the node for which relaxation is to be created.
[in]	rel	is the relaxation that is being constructed. Do not allocate or re-allocate space for it. Just add new variables or constraints to it.
[out]	is_inf	is true if the node can be pruned.

Implements Minotaur::Handler.

◆ separate()

void LinearHandler::separate	(	ConstSolutionPtr	sol,
		NodePtr	node,
		RelaxationPtr	rel,
		CutManager *	cutman,
		SolutionPoolPtr	s_pool,
		ModVector &	p_mods,
		ModVector &	r_mods,
		bool *	sol_found,
		SeparationStatus *	status
	)

virtual

Generate valid cuts using linear constraints.

Implements Minotaur::Handler.

◆ simplePresolve()

void LinearHandler::simplePresolve	(	ProblemPtr	,
		SolutionPoolPtr	,
		ModVector &	,
		SolveStatus &	status
	)

virtual

Do simple presolve. This may involve quick bound inference and other simple tricks. Can be cheaper than node presolve and root presolve.

Parameters

[in]	p	Problem for which presolving to be done.
[in]	spool	Solution pool.
[out]	t_mods	Modification derived from presolve.
[out]	status	Presolve status.

Reimplemented from Minotaur::Handler.

◆ tightenInts_()

void LinearHandler::tightenInts_	(	ProblemPtr	p,
		bool	apply_to_prob,
		bool *	changed,
		ModQ *	mods
	)

protected

Round the bounds.

TODO:

◆ writeStats()

void LinearHandler::writeStats ( std::ostream & ) const

virtual

Write statistics to ostream out.

Reimplemented from Minotaur::Handler.

Member Data Documentation

◆ intTol_

const double Minotaur::LinearHandler::intTol_

protected

Tolerance for checking integrality.

If |round(x) - x| < intTol_, then it is considered to be integer valued.

◆ linVars_

VarQueue Minotaur::LinearHandler::linVars_

protected

Linear variables: variables that do not appear in nonlinear functions, both in objective and constraints.

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

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

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Function Documentation

◆ chkSing_()

◆ getBranches()

◆ getBranchingCandidates()

◆ getBrMod()

◆ getName()

◆ isFeasible()

◆ isNeeded()

◆ presolve()

◆ presolveNode()

◆ relax_()

◆ relaxInitFull()

◆ relaxInitInc()

◆ relaxNodeFull()

◆ relaxNodeInc()

◆ separate()

◆ simplePresolve()

◆ tightenInts_()

◆ writeStats()

Member Data Documentation

◆ intTol_

◆ linVars_