These are cuts of the form. More...

#include <CouenneSdpCuts.hpp>

Inheritance diagram for Couenne::CouenneSdpCuts:

Public Member Functions
	CouenneSdpCuts (CouenneProblem *, JnlstPtr, const Ipopt::SmartPtr< Ipopt::OptionsList >)
	Constructor. More...

	~CouenneSdpCuts ()
	Destructor. More...

CouenneSdpCuts &	operator= (const CouenneSdpCuts &)
	Assignment. More...

	CouenneSdpCuts (const CouenneSdpCuts &)
	Copy constructor. More...

virtual CglCutGenerator *	clone () const
	Cloning constructor. More...

const bool	doNotUse () const

virtual void	generateCuts (const OsiSolverInterface &, OsiCuts &, const CglTreeInfo=CglTreeInfo()) const
	The main CglCutGenerator. More...

void	updateSol ()

Static Public Member Functions
static void	registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
	Add list of options to be read from file. More...

Protected Attributes
CouenneProblem *	problem_
	pointer to problem info More...

bool	doNotUse_
	after construction, true if there are enough product terms to justify application. More...

std::vector< CouenneExprMatrix * >	minors_
	minors on which to apply cuts More...

int	numEigVec_
	number of eigenvectors to be used (default: n) More...

bool	onlyNegEV_
	only use negative eigenvalues (default: yes) More...

bool	useSparsity_
	Sparsify eigenvalues before writing inequality (default: no) More...

bool	fillMissingTerms_
	If minor not fully dense, create fictitious auxiliary variables that will be used in sdp cuts only (tighter than sdp cuts without) More...

Private Types
enum	zero_type { POS_DELTA, SELECTED, VALID_DELTA }

Private Member Functions
void	genCutSingle (CouenneExprMatrix *const &, const OsiSolverInterface &, OsiCuts &, const CglTreeInfo=CglTreeInfo()) const

void	compareSparsify (const OsiSolverInterface &si, int n, int m, const double sol, double z, double w, FILE out) const

void	sparsify2 (const int n, const double A, double sparse_v_mat, int card_v_mat, int min_nz, int *evdec_num) const

void	genSDPcut (const OsiSolverInterface &si, OsiCuts &cs, CouenneExprMatrix XX, double v1, double v2, int *) const

void	additionalSDPcuts (const OsiSolverInterface &si, OsiCuts &cs, CouenneExprMatrix minor, int np, const double A, const double vector, int *) const

void	zero_comp (const int ind_i, const double delta, const int np, const int selected, int loc_selected, int ploc_card_selected, int ploc_card_new_selected, double ploc_lhs, double locmargin, double locmat, double locv, const int evidx, bool wise, int evdec_num, double recomp_gap, double *threshold) const

void	zero_unified (enum zero_type type, const int np, const int order, const int selected, const int min_card_new_selected, const double min_delta, const int start_point, const int curr_i, int loc_selected, int ploc_card_selected, int ploc_card_new_selected, double ploc_lhs, double locmargin, double locmat, int pnchanged, double locv, const int evidx, bool wise, double recomp_gap, double threshold, int *evdec_num) const

void	add_v_cut (const int np, const int loc_selected, const int loc_card_selected, const double locv, const int init_card_selected, int has_init_vect, int selected, int pcard_selected, int pnew_selected, double *sparse_v_mat, int pcard_v_mat) const

void	update_sparsify_structures (const int np, double v, double margin, double A, double lhs, const int zeroed, int evidx, bool decompose, int evdec_num) const

void	sparsify (bool sparsify_new, const int evidx, const double eigen_val, const double v, const int n, const double sol, double *sparse_v_mat, int card_v_mat, int *evdec_num) const

Detailed Description

These are cuts of the form.

a' X a >= 0

where X is a matrix constrained to be PSD.

Typical application is in problems with products forming a matrix of auxiliary variables X0 = (x_ij)_{i,j in N}, and x_ij is the auxiliary variable for x_i * x_j. After reformulation, matrices like X0 arise naturally and can be used to separate cuts that help strengthen the lower bound. See Sherali and Fraticelli for the base idea, and Qualizza, Belotti and Margot for an efficient rework and its implementation. Andrea Qualizza's code has been made open source and is used here (thanks Andrea!).

Definition at line 43 of file CouenneSdpCuts.hpp.

Member Enumeration Documentation

enum Couenne::CouenneSdpCuts::zero_type

private

Enumerator
POS_DELTA
SELECTED
VALID_DELTA

Definition at line 121 of file CouenneSdpCuts.hpp.

Constructor & Destructor Documentation

Couenne::CouenneSdpCuts::CouenneSdpCuts	(	CouenneProblem *	,
		JnlstPtr	,
		const Ipopt::SmartPtr< Ipopt::OptionsList >
	)

Constructor.

Couenne::CouenneSdpCuts::~CouenneSdpCuts ( )

Destructor.

Couenne::CouenneSdpCuts::CouenneSdpCuts ( const CouenneSdpCuts & )

Copy constructor.

Member Function Documentation

CouenneSdpCuts& Couenne::CouenneSdpCuts::operator= ( const CouenneSdpCuts & )

Assignment.

virtual CglCutGenerator* Couenne::CouenneSdpCuts::clone ( ) const

virtual

Cloning constructor.

const bool Couenne::CouenneSdpCuts::doNotUse ( ) const

inline

Definition at line 76 of file CouenneSdpCuts.hpp.

References doNotUse_.

virtual void Couenne::CouenneSdpCuts::generateCuts	(	const OsiSolverInterface &	,
		OsiCuts &	,
		const CglTreeInfo	= `CglTreeInfo()`
	)		const

virtual

The main CglCutGenerator.

static void Couenne::CouenneSdpCuts::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions )

static

Add list of options to be read from file.

void Couenne::CouenneSdpCuts::updateSol ( )

void Couenne::CouenneSdpCuts::genCutSingle	(	CouenneExprMatrix *const &	,
		const OsiSolverInterface &	,
		OsiCuts &	,
		const CglTreeInfo	= `CglTreeInfo()`
	)		const

private

void Couenne::CouenneSdpCuts::compareSparsify	(	const OsiSolverInterface &	si,
		int	n,
		int	m,
		const double *	sol,
		double *	z,
		double *	w,
		FILE *	out
	)		const

private

void Couenne::CouenneSdpCuts::sparsify2	(	const int	n,
		const double *	A,
		double **	sparse_v_mat,
		int *	card_v_mat,
		int	min_nz,
		int *	evdec_num
	)		const

private

void Couenne::CouenneSdpCuts::genSDPcut	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		CouenneExprMatrix *	XX,
		double *	v1,
		double *	v2,
		int **
	)		const

private

void Couenne::CouenneSdpCuts::additionalSDPcuts	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		CouenneExprMatrix *	minor,
		int	np,
		const double *	A,
		const double *	vector,
		int **
	)		const

private

void Couenne::CouenneSdpCuts::zero_comp	(	const int	ind_i,
		const double	delta,
		const int	np,
		const int *	selected,
		int *	loc_selected,
		int *	ploc_card_selected,
		int *	ploc_card_new_selected,
		double *	ploc_lhs,
		double *	locmargin,
		double *	locmat,
		double *	locv,
		const int	evidx,
		bool	wise,
		int *	evdec_num,
		double *	recomp_gap,
		double *	threshold
	)		const

private

void Couenne::CouenneSdpCuts::zero_unified	(	enum zero_type	type,
		const int	np,
		const int *	order,
		const int *	selected,
		const int	min_card_new_selected,
		const double	min_delta,
		const int	start_point,
		const int	curr_i,
		int *	loc_selected,
		int *	ploc_card_selected,
		int *	ploc_card_new_selected,
		double *	ploc_lhs,
		double *	locmargin,
		double *	locmat,
		int *	pnchanged,
		double *	locv,
		const int	evidx,
		bool	wise,
		double *	recomp_gap,
		double *	threshold,
		int *	evdec_num
	)		const

private

void Couenne::CouenneSdpCuts::add_v_cut	(	const int	np,
		const int *	loc_selected,
		const int	loc_card_selected,
		const double *	locv,
		const int	init_card_selected,
		int *	has_init_vect,
		int *	selected,
		int *	pcard_selected,
		int *	pnew_selected,
		double **	sparse_v_mat,
		int *	pcard_v_mat
	)		const

private

void Couenne::CouenneSdpCuts::update_sparsify_structures	(	const int	np,
		double *	v,
		double *	margin,
		double *	A,
		double *	lhs,
		const int *	zeroed,
		int	evidx,
		bool	decompose,
		int *	evdec_num
	)		const

private

void Couenne::CouenneSdpCuts::sparsify	(	bool	sparsify_new,
		const int	evidx,
		const double	eigen_val,
		const double *	v,
		const int	n,
		const double *	sol,
		double **	sparse_v_mat,
		int *	card_v_mat,
		int *	evdec_num
	)		const

private

Member Data Documentation

CouenneProblem* Couenne::CouenneSdpCuts::problem_

protected

pointer to problem info

Definition at line 47 of file CouenneSdpCuts.hpp.

bool Couenne::CouenneSdpCuts::doNotUse_

protected

after construction, true if there are enough product terms to justify application.

If not, do not add this cut generator

Definition at line 49 of file CouenneSdpCuts.hpp.

Referenced by doNotUse().

std::vector<CouenneExprMatrix *> Couenne::CouenneSdpCuts::minors_

protected

minors on which to apply cuts

Definition at line 53 of file CouenneSdpCuts.hpp.

int Couenne::CouenneSdpCuts::numEigVec_

protected

number of eigenvectors to be used (default: n)

Definition at line 55 of file CouenneSdpCuts.hpp.

bool Couenne::CouenneSdpCuts::onlyNegEV_

protected

only use negative eigenvalues (default: yes)

Definition at line 57 of file CouenneSdpCuts.hpp.

bool Couenne::CouenneSdpCuts::useSparsity_

protected

Sparsify eigenvalues before writing inequality (default: no)

Definition at line 59 of file CouenneSdpCuts.hpp.

bool Couenne::CouenneSdpCuts::fillMissingTerms_

protected

If minor not fully dense, create fictitious auxiliary variables that will be used in sdp cuts only (tighter than sdp cuts without)

Definition at line 61 of file CouenneSdpCuts.hpp.

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

CouenneSdpCuts.hpp

Public Member Functions

Static Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation