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

#include <CouenneTwoImplied.hpp>

Inheritance diagram for Couenne::CouenneTwoImplied:

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

	CouenneTwoImplied (const CouenneTwoImplied &)
	copy constructor More...

	~CouenneTwoImplied ()
	destructor More...

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

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

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 data structure (used for post-BT) More...

JnlstPtr	jnlst_
	Journalist. More...

int	nMaxTrials_
	maximum number of trials in every call More...

double	totalTime_
	Total CPU time spent separating cuts. More...

double	totalInitTime_
	CPU time spent columning the row formulation. More...

bool	firstCall_
	first call indicator More...

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

int	depthStopSeparate_
	Depth of the BB tree where stop separation. More...

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

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

constructor

Referenced by clone().

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

copy constructor

Couenne::CouenneTwoImplied::~CouenneTwoImplied ( )

destructor

Member Function Documentation

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

inline

clone method (necessary for the abstract CglCutGenerator class)

Definition at line 190 of file CouenneTwoImplied.hpp.

References CouenneTwoImplied().

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

the main CglCutGenerator

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

static

Add list of options to be read from file.

Member Data Documentation

CouenneProblem* Couenne::CouenneTwoImplied::problem_

protected

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

Definition at line 208 of file CouenneTwoImplied.hpp.

JnlstPtr Couenne::CouenneTwoImplied::jnlst_

protected

Journalist.

Definition at line 211 of file CouenneTwoImplied.hpp.

int Couenne::CouenneTwoImplied::nMaxTrials_

protected

maximum number of trials in every call

Definition at line 214 of file CouenneTwoImplied.hpp.

double Couenne::CouenneTwoImplied::totalTime_

mutableprotected

Total CPU time spent separating cuts.

Definition at line 217 of file CouenneTwoImplied.hpp.

double Couenne::CouenneTwoImplied::totalInitTime_

mutableprotected

CPU time spent columning the row formulation.

Definition at line 220 of file CouenneTwoImplied.hpp.

bool Couenne::CouenneTwoImplied::firstCall_

mutableprotected

first call indicator

Definition at line 223 of file CouenneTwoImplied.hpp.

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.

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:

CouenneTwoImplied.hpp

Public Member Functions

Static Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation