Cut Generator for implied bounds derived from pairs of linear (in)equalities. More...

#include <CouenneTwoImplied.hpp>

Inheritance diagram for Couenne::CouenneTwoImplied:

Collaboration diagram for Couenne::CouenneTwoImplied:

Public Member Functions
	CouenneTwoImplied (CouenneProblem *, JnlstPtr, const Ipopt::SmartPtr< Ipopt::OptionsList >)
	constructor

	CouenneTwoImplied (const CouenneTwoImplied &)
	copy constructor

	~CouenneTwoImplied ()
	destructor

CouenneTwoImplied *	clone () const
	clone method (necessary for the abstract CglCutGenerator class)

void	generateCuts (const OsiSolverInterface &, OsiCuts &, const CglTreeInfo=CglTreeInfo()) const
	the main CglCutGenerator

Public Member Functions inherited from CglCutGenerator
virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())=0

	CglCutGenerator ()

	CglCutGenerator (const CglCutGenerator &)

virtual CglCutGenerator *	clone () const=0

CglCutGenerator &	operator= (const CglCutGenerator &rhs)

virtual	~CglCutGenerator ()

virtual std::string	generateCpp (FILE *)

virtual void	refreshSolver (OsiSolverInterface *)

int	getAggressiveness () const

void	setAggressiveness (int value)

void	setGlobalCuts (bool trueOrFalse)

bool	canDoGlobalCuts () const

virtual bool	mayGenerateRowCutsInTree () const

virtual bool	needsOptimalBasis () const

virtual int	maximumLengthOfCutInTree () const

virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())=0

	CglCutGenerator ()

	CglCutGenerator (const CglCutGenerator &)

virtual CglCutGenerator *	clone () const=0

CglCutGenerator &	operator= (const CglCutGenerator &rhs)

virtual	~CglCutGenerator ()

virtual std::string	generateCpp (FILE *)

virtual void	refreshSolver (OsiSolverInterface *)

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

Protected Attributes
CouenneProblem *	problem_
	pointer to problem data structure (used for post-BT)

JnlstPtr	jnlst_
	Journalist.

int	nMaxTrials_
	maximum number of trials in every call

double	totalTime_
	Total CPU time spent separating cuts.

double	totalInitTime_
	CPU time spent columning the row formulation.

bool	firstCall_
	first call indicator

int	depthLevelling_
	Depth of the BB tree where to start decreasing chance of running this.

int	depthStopSeparate_
	Depth of the BB tree where stop separation.

Additional Inherited Members
Public Attributes inherited from CglCutGenerator
int	aggressive_

bool	canDoGlobalCuts_

Detailed Description

Cut Generator for implied bounds derived from pairs of linear (in)equalities.

Implied bounds usually work on a SINGLE inequality of the form

$\ell_j \le \sum_{i \in N_+} a_{ji} x_i + \sum_{i \in N_-} a_{ji} x_i \le u_j$

where $a_{ji} > 0$ for $i \in N_+$ and $a_{ji} < 0$ for $i \in N_-$ , and allow one to infer better bounds $ [x^L_i, x^U_i] $ on all variables with nonzero coefficients:

(1) $x^L_i \ge (\ell_j - \sum_{i \in N_+} a_{ji} x^U_i - \sum_{i \in N_-} a_{ji} x^L_i ) / a_{ji} \qquad \forall i \in N_+$

(2) $x^U_i \le (u_j - \sum_{i \in N_+} a_{ji} x^L_i - \sum_{i \in N_-} a_{ji} x^U_i ) / a_{ji} \qquad \forall i \in N_+$

(3) $x^L_i \ge (u_j - \sum_{i \in N_+} a_{ji} x^L_i - \sum_{i \in N_-} a_{ji} x^U_i ) / a_{ji} \qquad \forall i \in N_-$

(4) $x^U_i \le (\ell_j - \sum_{i \in N_+} a_{ji} x^U_i - \sum_{i \in N_-} a_{ji} x^L_i ) / a_{ji} \qquad \forall i \in N_+$

Consider now two inequalities:

$\ell_h \le \sum_{i \in N^1_+} a_{hi} x_i + \sum_{i \in N^1_-} a_{hi} x_i \le u_h$

$\ell_k \le \sum_{i \in N^2_+} a_{ki} x_i + \sum_{i \in N^2_-} a_{ki} x_i \le u_k$

and their CONVEX combination using $\alpha$ and $1 - \alpha$ , where $\alpha \in [0,1]$ :

$\ell' \le \sum_{i \in N} b_i x_i \le u'$

with $N = N^1_+\cup N^1_-\cup N^2_+\cup N^2_-$ , $\ell' = \alpha \ell_h + (1-\alpha) \ell_k$ , and $u' = \alpha u_h + (1-\alpha) u_k$ . As an example where this might be useful, consider

$x + y \ge 2$

$x - y \ge 1$

with $x \in [0,4]$ and $y \in [0,1]$ . (This is similar to an example given in Tawarmalani and Sahinidis to explain FBBT != OBBT, I believe.) The sum of the two above inequalities gives $x \ge 1.5$ , while using only the implied bounds on the single inequalities gives $x \ge 1$ .

The key consideration here is that the $ b_i $ coefficients, $\ell'$ , and $ u' $ are functions of $\alpha$ , which determines which, among (1)-(4), to apply. In general,

if $ b_i > 0 $ then

$x^L_i \ge (l' - \sum_{j \in N_+'} b_j x^U_j - \sum_{j \in N_-'} b_j x^L_j) / b_i$ ,

$x^U_i \le (u' - \sum_{j \in N_+'} b_j x^L_j - \sum_{j \in N_-'} b_j x^U_j) / b_i$ ;

if $ b_i < 0 $ then

$x^L_i \ge (l' - \sum_{j \in N_+'} b_j x^U_j - \sum_{j \in N_-'} b_j x^L_j) / b_i$ ,

$x^U_i \le (u' - \sum_{j \in N_+'} b_j x^L_j - \sum_{j \in N_-'} b_j x^U_j) / b_i$ .

Each lower/upper bound is therefore a piecewise rational function of $\alpha$ , given that $ b_i $ and the content of $
N_+' $ and $ N_-' $ depend on $\alpha$ . These functions are continuous (easy to prove) but not differentiable at some points of $ [0,1] $ .

The purpose of this procedure is to find the maximum of the lower bounding function and the minimum of the upper bounding function.

Divide the interval $ [0,1] $ into at most $ m+1 $ intervals (where $ m $ is the number of coefficients not identically zero, or the number of $ b_i $ that are nonzero for at least one value of $\alpha$ ). The limits $ c_i
$ of the subintervals are the zeros of each coefficient, i.e. the values of $\alpha$ such that $\alpha a_{ki} + (1-\alpha) a_{hi} = 0$ , or $c_i = \frac{-a_{hi}}{a_{ki} - a_{hi}}$ .

Sorting these values gives us something to do on every interval $[c_j, c_{j+1}]$ when computing a new value of $ x^L_i
$ and $ x^U_i $ , which I'll denote $ L_i $ and $
U_i $ in the following.

0) if $ c_j = c_i $ then

compute $VL = \lim_{c_j \to \alpha} L_i (\alpha)$
if $= +\infty$ , infeasible else compute derivative DL (should be $+\infty$ )

1) else

compute $VL = \lim_{\alpha \to c_j} L_i (\alpha)$ (can be retrieved from previous interval as $L_i (\alpha)$ is continuous)
compute $DL = \lim_{\alpha \to c_j} dL_i (\alpha)$

update $ x^L $ with VL if necessary.

2) if $c_{j+1} = c_i$ then

compute $VR = \lim_{\alpha \to c_{j+1}} L_i (\alpha)$
if = $+\infty$ , infeasible else compute derivative DR (should be $-\infty$ )

3) else

compute $VR = \lim_{\alpha \to c_{j+1}} L_i (\alpha)$
compute $DR = \lim_{\alpha \to c_{j+1}} dL_i (\alpha)$

update $ x^L $ with VR if necessary.

if $ DL > 0 $ and $ DR < 0 $ , there might be a maximum in between, otherwise continue to next interval

compute internal maximum VI, update $ x^L $ with VI if necessary.

Apply a similar procedure for the upper bound

This should be applied for any $ h,k,i $ , therefore we might have a lot to do. First, select possible pairs $ (h,k) $ among those for which there exists at least one variable that satisfies neither of the following conditions:

a) same sign coefficient, constraints $ (h,k) $ both $\ge$ or both $\le$

b) opposite sign coefficient, constraints $ (h,k) $ $(\le,\ge)$ or $(\ge,\le)$

as in those cases, no $ c_i $ would be in $ [0,1] $

Definition at line 174 of file CouenneTwoImplied.hpp.

Constructor & Destructor Documentation

◆ CouenneTwoImplied() [1/2]

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

constructor

◆ CouenneTwoImplied() [2/2]

Couenne::CouenneTwoImplied::CouenneTwoImplied ( const CouenneTwoImplied & )

copy constructor

◆ ~CouenneTwoImplied()

Couenne::CouenneTwoImplied::~CouenneTwoImplied ( )

destructor

Member Function Documentation

◆ clone()

CouenneTwoImplied * Couenne::CouenneTwoImplied::clone ( ) const

inlinevirtual

clone method (necessary for the abstract CglCutGenerator class)

Implements CglCutGenerator.

Definition at line 190 of file CouenneTwoImplied.hpp.

◆ generateCuts()

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

the main CglCutGenerator

◆ registerOptions()

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

static

Add list of options to be read from file.

Member Data Documentation

◆ problem_

CouenneProblem* Couenne::CouenneTwoImplied::problem_

protected

pointer to problem data structure (used for post-BT)

Definition at line 208 of file CouenneTwoImplied.hpp.

◆ jnlst_

JnlstPtr Couenne::CouenneTwoImplied::jnlst_

protected

Journalist.

Definition at line 211 of file CouenneTwoImplied.hpp.

◆ nMaxTrials_

int Couenne::CouenneTwoImplied::nMaxTrials_

protected

maximum number of trials in every call

Definition at line 214 of file CouenneTwoImplied.hpp.

◆ totalTime_

double Couenne::CouenneTwoImplied::totalTime_

mutableprotected

Total CPU time spent separating cuts.

Definition at line 217 of file CouenneTwoImplied.hpp.

◆ totalInitTime_

double Couenne::CouenneTwoImplied::totalInitTime_

mutableprotected

CPU time spent columning the row formulation.

Definition at line 220 of file CouenneTwoImplied.hpp.

◆ firstCall_

bool Couenne::CouenneTwoImplied::firstCall_

mutableprotected

first call indicator

Definition at line 223 of file CouenneTwoImplied.hpp.

◆ depthLevelling_

int Couenne::CouenneTwoImplied::depthLevelling_

protected

Depth of the BB tree where to start decreasing chance of running this.

Definition at line 226 of file CouenneTwoImplied.hpp.

◆ depthStopSeparate_

int Couenne::CouenneTwoImplied::depthStopSeparate_

protected

Depth of the BB tree where stop separation.

Definition at line 229 of file CouenneTwoImplied.hpp.

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

/builddir/build/BUILD/Couenne-0.5.8/src/bound_tightening/twoImpliedBT/CouenneTwoImplied.hpp

Public Member Functions

Static Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CouenneTwoImplied() [1/2]

◆ CouenneTwoImplied() [2/2]

◆ ~CouenneTwoImplied()

Member Function Documentation

◆ clone()

◆ generateCuts()

◆ registerOptions()

Member Data Documentation

◆ problem_

◆ jnlst_

◆ nMaxTrials_

◆ totalTime_

◆ totalInitTime_

◆ firstCall_

◆ depthLevelling_

◆ depthStopSeparate_