#include <CxQuadHandler.h>

Inheritance diagram for Minotaur::CxQuadHandler:

Collaboration diagram for Minotaur::CxQuadHandler:

[legend]

Public Member Functions
	CxQuadHandler (EnvPtr env, ProblemPtr problem)
	Default constructor.

	~CxQuadHandler ()
	Destroy.

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

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

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

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

bool	isFeasible (ConstSolutionPtr sol, RelaxationPtr relaxation, bool &is_inf, double &inf_meas)

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

void	getBranchingCandidates (RelaxationPtr rel, const DoubleVector &x, ModVector &mods, BrVarCandSet &cands, BrCandVector &, bool &is_inf)
	Return it is constrained to be an integer.

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

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

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

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

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

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.

virtual ConstraintVector::const_iterator	consBegin () const

virtual ConstraintVector::const_iterator	consEnd () const

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

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	isNeeded ()
	Return true if this handler is needed for the problem.

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.

virtual void	removeCuts (RelaxationPtr, ConstSolutionPtr)

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.

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.

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

Protected Member Functions
void	relaxTwoSided_ (QuadraticFunctionPtr qf, ConstraintPtr cons, RelaxationPtr rel)

void	relaxOneSided_ (QuadraticFunctionPtr qf, ConstraintPtr cons, RelaxationPtr rel)

void	relaxObj_ (ObjectivePtr obj, RelaxationPtr rel)
	Relax the objective function, to make it convex.

void	addSecant_ (VariablePtr x, VariablePtr y, RelaxationPtr rel)

LinearFunctionPtr	getNewSecantLf_ (VariablePtr x, VariablePtr y, double &lb, double &ub, double &r)
	Get linear function and right hand side (r) for a secant constraint.

VariablePtr	addMcCormick_ (VariablePtr x0, VariablePtr x1, RelaxationPtr rel)
	Add all four McCormick inequalities for .

VariablePtr	addMcCormickLower_ (VariablePtr x0, VariablePtr x1, RelaxationPtr rel)
	Add two McCormick inequalities for $y \geq x_0x_1$ .

VariablePtr	addMcCormickUpper_ (VariablePtr x0, VariablePtr x1, RelaxationPtr rel)
	Add two McCormick inequalities for $y \leq x_0x_1$ .

LinearFunctionPtr	getMcLf_ (VariablePtr x0, double lb0, double ub0, VariablePtr x1, double lb1, double ub1, VariablePtr y, double &rhs, UInt i)
	Generate the appropriate McCormick inequality using the bounds.

void	binToLin_ ()

void	binToLinFun_ (FunctionPtr f, LinearFunctionPtr lf2)

void	relax_ (RelaxationPtr rel, bool *is_inf)

void	removeFixed_ ()

void	removeFixedFun_ (FunctionPtr f, LinearFunctionPtr lf2, double *c)

Protected Attributes
VarSecantMap	cvCons_

McCormickSet	mcCons_

VarSet	brVars_

double	eTol_
	Tolerance.

LoggerPtr	logger_
	Logger.

ProblemPtr	problem_
	Original problem.

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_ = "CxQuadHandler: "
	For printing.

Detailed Description

An CxQuadHandler handles the convex parts of quadratic functions of a problem. For now, we will just handle squares of singleton variables e.g. $\sum_ix_i^2 \leq u_0$ . $u_0$ could be an auxiliary varible or a constant. Later we will introduce sums of squares of general linear functions as well.

Member Function Documentation

◆ addSecant_()

void CxQuadHandler::addSecant_	(	VariablePtr	x,
		VariablePtr	y,
		RelaxationPtr	rel
	)

protected

Get secant approximation for the inequality: $y - x^2 \leq 0$ , and add it to the relaxation.

◆ getBranches()

Branches CxQuadHandler::getBranches	(	BrCandPtr	cand,
		DoubleVector &	x,
		RelaxationPtr	rel,
		SolutionPoolPtr	s_pool
	)

virtual

Return branches for branching.

Get branches by branching on the given candidate. In the general scheme for branching, we store only bound changes, though we are also capable of storing other mods.

Parameters

[in]	cand	Candidate on which the brancher wants to branch.
[in]	x	The solution of the relaxation at the current node.
[in]	rel	The relaxation at the current node.
[in]	s_pool	Best feasible solutions found so far.

Returns: a vector of branch-objects.

Implements Minotaur::Handler.

◆ getBranchingCandidates()

void CxQuadHandler::getBranchingCandidates	(	RelaxationPtr	rel,
		const DoubleVector &	x,
		ModVector &	mods,
		BrVarCandSet &	cands,
		BrCandVector &	,
		bool &	is_inf
	)

virtual

Return $u_0$ it is constrained to be an integer.

Implements Minotaur::Handler.

◆ getBrMod()

ModificationPtr CxQuadHandler::getBrMod	(	BrCandPtr	cand,
		DoubleVector &	x,
		RelaxationPtr	rel,
		BranchDirection	dir
	)

virtual

Get the modifcation that creates a given (up or down) branch.

If one branch is pruned by the brancher (e.g. strong brancher), then we can apply the modifications of other branch to the relaxation without branching. This routine returns such a modification. This function is also called for obtaining modifications for strong branching on a candidate.

Parameters

[in]	cand	The candidate for which we want the modification.
[in]	x	The solution of relaxation at current node.
[in]	rel	The relaxation at current node.
[in]	dir	The Direction for which we want the modification, Up or Down?.

Returns: Modification that can be applied to the relaxation before re-solving it.

Implements Minotaur::Handler.

◆ getName()

std::string CxQuadHandler::getName ( ) const

virtual

Return the name of the handler.

Implements Minotaur::Handler.

◆ isFeasible()

bool CxQuadHandler::isFeasible	(	ConstSolutionPtr	sol,
		RelaxationPtr	relaxation,
		bool &	is_inf,
		double &	inf_meas
	)

virtual

Suppose we added a variable $u_0 \geq \sum_i x_i^2$ . In this function, check if at a given point, $(u_0^*, x^*)$ , the above constraint holds or not. Return true if the constraint holds, false otherwise. Checks the conditions for all such constraints but stops at the first infeasible one.

Implements Minotaur::Handler.

◆ presolve()

SolveStatus CxQuadHandler::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 CxQuadHandler::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 CxQuadHandler::relax_	(	RelaxationPtr	rel,
		bool *	is_inf
	)

protected

For now, this handler will introduce a new variable for each sum of squares of variables. We will also add constraints, that have these functions, from the original problem if such constraints have not already been added. If these constraints are already in the problem, we will add the corresponding new variable in the linear function of the constraint. Bounds: $u_O \in [0,\sum_i\max(lb_i^2, ub_i^2)$ ].

◆ relaxInitFull()

void CxQuadHandler::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 CxQuadHandler::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 CxQuadHandler::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 CxQuadHandler::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.

◆ relaxOneSided_()

void CxQuadHandler::relaxOneSided_	(	QuadraticFunctionPtr	qf,
		ConstraintPtr	cons,
		RelaxationPtr	rel
	)

protected

Add quadratic/linear relaxations of the quadratic constraint 'cons' that only has an upperbound.

◆ relaxTwoSided_()

void CxQuadHandler::relaxTwoSided_	(	QuadraticFunctionPtr	qf,
		ConstraintPtr	cons,
		RelaxationPtr	rel
	)

protected

Add quadratic/linear relaxations of the quadratic range constraint 'cons'.

◆ separate()

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

virtual

Not implemented yet.

Implements Minotaur::Handler.

Member Data Documentation

◆ brVars_

VarSet Minotaur::CxQuadHandler::brVars_

protected

Variables that occur in bilinear terms and also concave square terms. These do not include auxiliary variables that are added in relaxation. These are all the candidates that we consider for branching.

◆ cvCons_

VarSecantMap Minotaur::CxQuadHandler::cvCons_

protected

For each constraint of the type $y \leq x^2$ , we add a new secant approximation. This map stores the 'y' variables and the associated linear secant-constraint.

◆ mcCons_

McCormickSet Minotaur::CxQuadHandler::mcCons_

protected

Keep a set of McCormick inequalities that were added and for which we will update the co-efficients etc.

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

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

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Function Documentation

◆ addSecant_()

◆ getBranches()

◆ getBranchingCandidates()

◆ getBrMod()

◆ getName()

◆ isFeasible()

◆ presolve()

◆ presolveNode()

◆ relax_()

◆ relaxInitFull()

◆ relaxInitInc()

◆ relaxNodeFull()

◆ relaxNodeInc()

◆ relaxOneSided_()

◆ relaxTwoSided_()

◆ separate()

Member Data Documentation

◆ brVars_

◆ cvCons_

◆ mcCons_