# Couenne::CouenneTwoImplied Class Reference

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

`#include <CouenneTwoImplied.hpp>`

List of all members.

## 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
## 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.

## 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

where for and for , and allow one to infer better bounds on all variables with nonzero coefficients:

(1)

(2)

(3)

(4)

Consider now two inequalities:

and their CONVEX combination using and , where :

with , , and . As an example where this might be useful, consider

with and . (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 , while using only the implied bounds on the single inequalities gives .

The key consideration here is that the coefficients, , and are functions of , which determines which, among (1)-(4), to apply. In general,

if then

,

;

if then

,

.

Each lower/upper bound is therefore a piecewise rational function of , given that and the content of and depend on . These functions are continuous (easy to prove) but not differentiable at some points of .

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 into at most intervals (where is the number of coefficients not identically zero, or the number of that are nonzero for at least one value of ). The limits of the subintervals are the zeros of each coefficient, i.e. the values of such that , or .

Sorting these values gives us something to do on every interval when computing a new value of and , which I'll denote and in the following.

0) if then

- compute
- if , infeasible else compute derivative DL (should be )

1) else

- compute (can be retrieved from previous interval as is continuous)

- compute

update with VL if necessary.

2) if then

- compute

- if = , infeasible else compute derivative DR (should be )

3) else

- compute
- compute

update with VR if necessary.

if and , there might be a maximum in between, otherwise continue to next interval

compute internal maximum VI, update with VI if necessary.

Apply a similar procedure for the upper bound

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

a) same sign coefficient, constraints both or both

b) opposite sign coefficient, constraints or

as in those cases, no would be in

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_`[mutable, protected]`

Total CPU time spent separating cuts.

Definition at line 217 of file CouenneTwoImplied.hpp.

double Couenne::CouenneTwoImplied::totalInitTime_`[mutable, protected]`

CPU time spent columning the row formulation.

Definition at line 220 of file CouenneTwoImplied.hpp.

bool Couenne::CouenneTwoImplied::firstCall_`[mutable, protected]`

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

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines