LinearRelax Class Reference

A linear relaxation. More...

#include <linrelax.h>

Collaboration diagram for LinearRelax:

Classes
class	LinConstraint
	Class to represent a linear (block) constraint. More...
Public Member Functions
int	core_size () const
	The size of the core of the linear relaxation.
	LinearRelax (Pointer< Param > param_)
	Constructor.
	LinearRelax (const LinearRelax &linrelax, int k, Pointer< MinlpNode > node=NULL, Pointer< SepQcFunc > alt_obj=NULL)
	Constructs a copy of one block of a LinearRelax which includes already all cuts for a specific node.
void	init (Pointer< MinlpProblem > convex_prob, const vector< int > &i_discr, Pointer< dvector > feas_point=NULL, bool is_feas=true)
	Initialize a linear relaxation from a convex problem.
void	add_level_cut (double level)
	Adds a level cut.
void	update_level_cut (double newlevel)
	Updates the level cut.
void	add_cut (const Pointer< SimpleCut > &cut, int k, const Pointer< MinlpNode > &node=NULL)
	Adds a cut to the cutpool.
void	add_cut (const Pointer< SimpleCut > &cut, const Pointer< MinlpNode > &node=NULL)
	Adds a cut to the cutpool of coupling constraints.
void	add_cut (const Pointer< LinearizationCut > &cut, int k, const Pointer< MinlpNode > &node=NULL)
void	add_cut (Pointer< IntervalGradientCut > intgradcut, int k, Pointer< MinlpNode > node=NULL)
	Adds a IntervalGradientCut to the cutpool.
void	integrate (LinearRelax &linrelax, int k, Pointer< MinlpNode > node=NULL)
	Integrated the cuts from another linear relaxation into this one.
void	get_cuts (list< CutPool::CutInfo > &cutinfos, Pointer< MinlpNode > node=NULL)
	Collects the cuts for a node.
void	update_cuts (Pointer< MinlpNode > node, int k, IntervalGradientCutGenerator &generator, LinearizedConCutGenerator &linconcutgen)
double	get_upper_bound ()
	Computes an upper bound of the linear relaxation by maximizing the objective function.
bool	cutlimit_reached () const
int	nr_local_cuts (Pointer< MinlpNode > node) const
	The number of local cuts for a node.
int	nr_global_cuts () const
	The number of global cuts.
int	nr_all_cuts () const
	The number of all cuts, global and local.
void	remove_node (Pointer< MinlpNode > node)
	Removes a node from the cuts in the cutpool.
void	duplicate_nodeinfo (Pointer< MinlpNode > oldnode, Pointer< MinlpNode > newnode)
void	clear_solver ()
	Clears the solver such that it does not represent the linear relaxation of some node.
bool	feasible (Pointer< MinlpNode > node, double tol=1E-4)
	Checks the linear relaxation (R) or (R[U]) for feasibility.
bool	point_feasible (Pointer< MinlpNode > node, const dvector &x, double tol=1E-4) const
	Checks, if a specific point is feasible for the linear relaxation.
int	solve (dvector &sol_point, double &value, Pointer< MinlpNode > node, dvector *dual_point=NULL, double tol=1E-4)
	Solves the linear relaxation (R) or (R[U]).
double	box_reduce (Pointer< MinlpNode > node, int k, const vector< bool > &discr, bool unknown_only=false, set< pair< int, IntervalReduction::which_bound_type > > *changed_var=NULL, double min_impr=0.01)
	Reduces the box of a block of variables by minimizing/maximizing the variables using the linear relaxation.
double	box_reduce (Pointer< MinlpNode > node, const vector< bool > &discr, bool unknown_only=false, set< pair< int, IntervalReduction::which_bound_type > > *changed_var=NULL, double min_impr=0.01)
	Reduces the box of all variables by minimizing/maximizing the variables using the linear relaxation.
double	box_reduce (dvector &newlow, dvector &newup, const vector< bool > &discr, bool unknown_only=false, set< pair< int, IntervalReduction::which_bound_type > > *changed_var=NULL, double min_impr=0.01)
void	set_box (const dvector &lower_, const dvector &upper_)
int	generate_cuts (Pointer< MinlpNode > node)
Public Attributes
Pointer< SepQcFunc >	obj
	The objective function of the linear relaxation.
vector< list< LinConstraint > >	block_con
	The constraints of the core linear relaxation, which are defined for one block only.
list< LinConstraint >	couple_con
	The constraints of the core linear relaxation, which are defined for more than one block.
set< pair< int, int > >	boxreduce_reduced_integer
Private Member Functions
bool	box_reduce (pair< double, double > &newbox, const pair< double, double > &oldbox, int k, int i, bool discrete=false, bool unknown_only=false)
	Reduces the box of a variable by minimizing/maximizing the variable using the linear relaxation.
Private Attributes
Pointer< Param >	param
	Parameters.
int	max_cutsnr
	The maximum number of cuts, we will add.
int	inactivetime_limit_global
	Given to CutPool's.
int	inactivetime_limit_local
vector< Pointer< CutPool > >	cutpool
Pointer< CutPool >	cutpoolcoupling
	Cutpool of coupling constraints.
dvector	lower
	Bounds on variables.
dvector	upper
vector< int >	i_discr
	Indices of integer variables.
Pointer< LinearRelaxSolver >	solver
MinlpNode *	solver_node
	The address of the node, the LinearRelaxSolver uses currently.
list< LinConstraint >::iterator	levelcut_pos
	The LinConstraint in couple_con or block_con, which keeps the level cut.
Friends
class	LinearRelaxSolverGeneral
class	LinearRelaxSolverMIP
ostream &	operator<< (ostream &out, LinearRelax &linrelax)

Detailed Description

A linear relaxation.

Parameters:

	Level	Cuts options 0 or 1 default 1 level 1 Indicates, whether to add a level cut (1) or not (0).
	max	cuts nr options integer $ 0$ default 500000 level 2 The maximum number of cuts handled (over all nodes).
	Cuts	inactive time limit global options integer $ 0$ default 10 level 1 The number of iterations a global (i.e., valid for all nodes) cut should be inactive before it is deleted.
	Cuts	inactive time limit local options integer $ 0$ default 3 level 1 The number of iterations a local (i.e., valid for only one node and its successors) cut should be inactive before it is deleted.

Definition at line 43 of file linrelax.h.

Constructor & Destructor Documentation

LinearRelax::LinearRelax ( Pointer< Param > param_ )

Constructor.

LinearRelax::LinearRelax	(	const LinearRelax &	linrelax,
		int	k,
		Pointer< MinlpNode >	node = `NULL`,
		Pointer< SepQcFunc >	alt_obj = `NULL`
	)

Constructs a copy of one block of a LinearRelax which includes already all cuts for a specific node.

Copies the blockproblem from linrelax, adds the global cuts and the one for the given node (if not NULL) to this problem. So, this the core of the linear relax is (R_k[U]).

Parameters:

alt_obj

An alternative objective function.

Member Function Documentation

bool LinearRelax::box_reduce	(	pair< double, double > &	newbox,
		const pair< double, double > &	oldbox,
		int	k,
		int	i,
		bool	discrete = `false`,
		bool	unknown_only = `false`
	)			`[private]`

Reduces the box of a variable by minimizing/maximizing the variable using the linear relaxation.

Parameters:

	oldlow	Old lower bound of the variable.
	oldup	Old upper bound of the variable.
	k	Block number of the variable.
	i	Block index of the variable.
	discrete	Indicates, whether the variable is a discrete one.
	unknown_only	Indicates, whether we should only try to compute unknown bounds (instead of reducing known ones).

Returns:: The new box of the variable.

int LinearRelax::core_size ( ) const

The size of the core of the linear relaxation.

couple_con.size()+ block_con[k].size().

void LinearRelax::init	(	Pointer< MinlpProblem >	convex_prob,
		const vector< int > &	i_discr,
		Pointer< dvector >	feas_point = `NULL`,
		bool	is_feas = `true`
	)

Initialize a linear relaxation from a convex problem.

void LinearRelax::add_level_cut ( double level )

Adds a level cut.

void LinearRelax::update_level_cut ( double newlevel )

Updates the level cut.

void LinearRelax::add_cut	(	const Pointer< SimpleCut > &	cut,
		int	k,
		const Pointer< MinlpNode > &	node = `NULL`
	)

Adds a cut to the cutpool.

If the cut is global, or the node matches the one, the LinearRelaxSolver uses, the solver is notified.

void LinearRelax::add_cut	(	const Pointer< SimpleCut > &	cut,
		const Pointer< MinlpNode > &	node = `NULL`
	)			`[inline]`

Adds a cut to the cutpool of coupling constraints.

Definition at line 171 of file linrelax.h.

void LinearRelax::add_cut	(	const Pointer< LinearizationCut > &	cut,
		int	k,
		const Pointer< MinlpNode > &	node = `NULL`
	)

void LinearRelax::add_cut	(	Pointer< IntervalGradientCut >	intgradcut,
		int	k,
		Pointer< MinlpNode >	node = `NULL`
	)

Adds a IntervalGradientCut to the cutpool.

If the cut is global, or the node matches the one, the LinearRelaxSolver uses, the solver is notified.

void LinearRelax::integrate	(	LinearRelax &	linrelax,
		int	k,
		Pointer< MinlpNode >	node = `NULL`
	)

Integrated the cuts from another linear relaxation into this one.

Adds the global cuts from the first cutpool in linrelax, which are not tagged, to the k'th cutpool here.

void LinearRelax::get_cuts	(	list< CutPool::CutInfo > &	cutinfos,
		Pointer< MinlpNode >	node = `NULL`
	)

Collects the cuts for a node.

void LinearRelax::update_cuts	(	Pointer< MinlpNode >	node,
		int	k,
		IntervalGradientCutGenerator &	generator,
		LinearizedConCutGenerator &	linconcutgen
	)

double LinearRelax::get_upper_bound ( )

Computes an upper bound of the linear relaxation by maximizing the objective function.

bool LinearRelax::cutlimit_reached ( ) const [inline]

Definition at line 197 of file linrelax.h.

int LinearRelax::nr_local_cuts ( Pointer< MinlpNode > node ) const

The number of local cuts for a node.

int LinearRelax::nr_global_cuts ( ) const

The number of global cuts.

int LinearRelax::nr_all_cuts ( ) const

The number of all cuts, global and local.

void LinearRelax::remove_node ( Pointer< MinlpNode > node )

Removes a node from the cuts in the cutpool.

void LinearRelax::duplicate_nodeinfo	(	Pointer< MinlpNode >	oldnode,
		Pointer< MinlpNode >	newnode
	)

void LinearRelax::clear_solver ( )

Clears the solver such that it does not represent the linear relaxation of some node.

bool LinearRelax::feasible	(	Pointer< MinlpNode >	node,
		double	tol = `1E-4`
	)

Checks the linear relaxation (R) or (R[U]) for feasibility.

Returns:: True, if the linear relaxation is feasible, false else.

bool LinearRelax::point_feasible	(	Pointer< MinlpNode >	node,
		const dvector &	x,
		double	tol = `1E-4`
	)			const

Checks, if a specific point is feasible for the linear relaxation.

Returns:: True, if the point is feasible according to the given tolerance. False, else.

int LinearRelax::solve	(	dvector &	sol_point,
		double &	value,
		Pointer< MinlpNode >	node,
		dvector *	dual_point = `NULL`,
		double	tol = `1E-4`
	)

Solves the linear relaxation (R) or (R[U]).

Parameters:

	sol_point	To store the solution point.
	value	To store the objective value.
	node	To distinguish between (R) and (R[U]).
	dual_point	A pointer to a dvector to store the dual variables in, or NULL, if not interested.

Returns:: A return code similiar to SNOPT. 0 for solved, 1 for infeasible, 3 else.

double LinearRelax::box_reduce	(	Pointer< MinlpNode >	node,
		int	k,
		const vector< bool > &	discr,
		bool	unknown_only = `false`,
		set< pair< int, IntervalReduction::which_bound_type > > *	changed_var = `NULL`,
		double	min_impr = `0.01`
	)

Reduces the box of a block of variables by minimizing/maximizing the variables using the linear relaxation.

Parameters:

	node	The node to use, can be NULL.
	k	The block number.
	discr	Indicators for discrete variables. Needs to be the one for the whole problem.
	unknown_only	Indicates, whether we should try to determine unknown bounds only.
	changed_var	A set to store the indices of variables in, which bounds were reduced by at least the percentage given in min_impr. Can be used as input for IntervalReduction.
	min_impr	The relative minimum improvement a bound must achieve to be added to changed_var.

double LinearRelax::box_reduce	(	Pointer< MinlpNode >	node,
		const vector< bool > &	discr,
		bool	unknown_only = `false`,
		set< pair< int, IntervalReduction::which_bound_type > > *	changed_var = `NULL`,
		double	min_impr = `0.01`
	)

Reduces the box of all variables by minimizing/maximizing the variables using the linear relaxation.

Parameters:

	node	The node to use, can be NULL.
	discr	Indicators for discrete variables. Needs to be the one for the whole problem.
	unknown_only	Indicates, whether we should try to determine unknown bounds only.
	changed_var	A set to store the indices of variables in, which bounds were reduced by at least the percentage given in min_impr. Can be used as input for IntervalReduction.
	min_impr	The relative minimum improvement a bound must achieve to be added to changed_var.

double LinearRelax::box_reduce	(	dvector &	newlow,
		dvector &	newup,
		const vector< bool > &	discr,
		bool	unknown_only = `false`,
		set< pair< int, IntervalReduction::which_bound_type > > *	changed_var = `NULL`,
		double	min_impr = `0.01`
	)