Cut Generator for FBBT fixpoint. More...

#include <CouenneFixPoint.hpp>

Inheritance diagram for Couenne::CouenneFixPoint:

Collaboration diagram for Couenne::CouenneFixPoint:

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

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

	~CouenneFixPoint ()
	destructor More...

CouenneFixPoint *	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 Member Functions
void	createRow (int, int, int, OsiSolverInterface , const int , const double *, const double, const int, bool, int, int) const
	Create a single cut. More...

Protected Attributes
bool	extendedModel_
	should we use an extended model or a more compact one? More...

CouenneProblem *	problem_
	pointer to the CouenneProblem representation More...

bool	firstCall_
	Is this the first call? More...

double	CPUtime_
	CPU time. More...

int	nTightened_
	Number of bounds tightened. More...

int	levelStop_
	Level at which to stop. More...

CouenneBTPerfIndicator	perfIndicator_
	Performance indicator. More...

Detailed Description

Cut Generator for FBBT fixpoint.

Definition at line 30 of file CouenneFixPoint.hpp.

Constructor & Destructor Documentation

CouenneFixPoint::CouenneFixPoint	(	CouenneProblem *	p,
		const Ipopt::SmartPtr< Ipopt::OptionsList >	options
	)

constructor

Definition at line 17 of file FixPointConstructors.cpp.

CouenneFixPoint::CouenneFixPoint ( const CouenneFixPoint & rhs )

copy constructor

Definition at line 34 of file FixPointConstructors.cpp.

CouenneFixPoint::~CouenneFixPoint ( )

destructor

Definition at line 45 of file FixPointConstructors.cpp.

Member Function Documentation

CouenneFixPoint* Couenne::CouenneFixPoint::clone ( ) const

inline

clone method (necessary for the abstract CglCutGenerator class)

Definition at line 45 of file CouenneFixPoint.hpp.

void CouenneFixPoint::generateCuts	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		const CglTreeInfo	treeInfo = `CglTreeInfo ()`
	)		const

the main CglCutGenerator

Cut Generator for FBBT fixpoint.

Only run this if the latest FBBT terminated on the iteration limit, as this suggests that the FPLP might be of some help. Termination before iteration limit reached implies that a relaxation (on which the FPLP is based) won't generate better bounds.

However, we do run the first time as otherwise it would be nixed for the whole branch-and-bound.

An LP relaxation of a MINLP problem is available in the first parameter passed. Let us suppose that this LP relaxation is of the form

LP = {x in R^n: Ax <= b}

for suitable nxm matrix A, rhs vector b, and variable vector x. Our purpose is that of creating a much larger LP that will help us find the interval [l,u] corresponding to the fixpoint of an FBBT algorithm. To this purpose, consider a single constraint of the above system:

sum {i=1..n} a_ji x_i <= b_j

According to two schools of thought (Leo's and mine), this single constraint can give rise to a number of FBBT constraints. The two schools of thoughts differ in the meaning of b: in mine, it is constant. In Leo's, it is a variable.

We need to perform the following steps:

define variables xL and xU define variables gL and gU for constraints (downward variables)

add objective function sum_j (u_j - l_j)

for each constraint a^j x <= b_j in Ax <= b: for each variable x_i contained: depending on sign of a_ji, add constraint on x_i^L or x_i^U (*) add constraints on g_j as well

solve LP

if new bounds are better than si's old bounds add OsiColCuts

Get the original problem's coefficient matrix and rhs vector, A and b

Now we have an fbbt-fixpoint LP problem. Solve it to get (possibly) better bounds

Definition at line 28 of file FixPointGenCuts.cpp.

void CouenneFixPoint::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions )

static

Add list of options to be read from file.

Definition at line 49 of file FixPointConstructors.cpp.

void CouenneFixPoint::createRow	(	int	sign,
		int	indexVar,
		int	nVars,
		OsiSolverInterface *	p,
		const int *	indices,
		const double *	coe,
		const double	rhs,
		const int	nEl,
		bool	extMod,
		int	indCon,
		int	nCon
	)		const

protected

Create a single cut.

Define

I+ the subset of {1..n} such that a_ji > 0 and i != indexVar; I- the subset of {1..n} such that a_ji < 0 and i != indexVar.

Consider

sum {i=1..n} a_ji x_i = b_j, (=)

equivalent to the two constraints

sum {i=1..n} a_ji x_i >= b_j. (>) – sign will be -1 (rlb) sum {i=1..n} a_ji x_i <= b_j (<) – sign will be +1 (rub)

Hence we should consider both (<) and (>) when we have an equality constraint. The resulting set of upward FBBT is as follows:

sum {i in I+} a_ji xU_i + sum {i in I-} a_ji xL_i >= bU_j (only if (<) enforced, i.e., sign == 1) sum {i in I+} a_ji xL_i + sum {i in I-} a_ji xU_i <= bL_j (only if (>) enforced, i.e., sign == -1)

together with the constraints defining the initial bounding interval of the auxiliary variable (already included):

bU_j <= bU0_j (<) bL_j >= bL0_j (>)

The set of downward FBBT constraints is instead:

xL_i >= (bL_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k) / a_ji (if a_ji > 0 and (>)) xU_i <= (bU_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k) / a_ji (if a_ji > 0 and (<))

xU_i <= (bL_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k) / a_ji (if a_ji < 0 and (>)) xL_i >= (bU_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k) / a_ji (if a_ji < 0 and (<))

probably better rewritten, to avoid (further) numerical issues, as

a_ji xL_i >= bL_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k (if a_ji > 0 and (>)) a_ji xU_i <= bU_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k (if a_ji > 0 and (<))

a_ji xU_i <= - bL_j + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k (if a_ji < 0 and (>))
a_ji xL_i >= - bU_j + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k (if a_ji < 0 and (<))

or even better, to keep the old coefficients (but not the indices!), like this:

a_ji xL_i + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k - bL_j >= 0 (if a_ji > 0 and (>)) a_ji xU_i + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k - bU_j <= 0 (if a_ji > 0 and (<))

a_ji xU_i + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k - bL_j >= 0 (if a_ji < 0 and (>)) a_ji xL_i + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k - bU_j <= 0 (if a_ji < 0 and (<))

and finally we need initial lower/upper bounds:

xL_i >= xL0_i xU_i <= xU0_i

and some consistency constraints

bL_i <= bU_i

(these and the two bound constraints above are already added in the main function above).

According to my school of thought, instead, there is no upward/downward directions to simulate. Hence, considering again

sum {i=1..n} a_ji x_i >= b_j (>) – sign will be -1 (rlb) sum {i=1..n} a_ji x_i <= b_j (<) – sign will be +1 (rub)

we'll have similar constraints, where bL and bU are replaced by the original rhs.

xL_i >= (b_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k) / a_ji (if a_ji > 0 and (>)) xU_i <= (b_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k) / a_ji (if a_ji > 0 and (<))

xU_i <= (b_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k) / a_ji (if a_ji < 0 and (>)) xL_i >= (b_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k) / a_ji (if a_ji < 0 and (<))

once again rewritten as

a_ji xL_i >= b_j - sum {k in I+} a_jk xU_k - sum {k in I-} a_jk xL_k (if a_ji > 0 and (>)) a_ji xU_i <= b_j - sum {k in I+} a_jk xL_k - sum {k in I-} a_jk xU_k (if a_ji > 0 and (<))

a_ji xU_i <= - b_j + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k (if a_ji < 0 and (>))
a_ji xL_i >= - b_j + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k (if a_ji < 0 and (<))

or even better:

a_ji xL_i + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k >= b_j (if a_ji > 0 and (>)) a_ji xU_i + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k <= b_j (if a_ji > 0 and (<))

a_ji xU_i + sum {k in I+} a_jk xU_k + sum {k in I-} a_jk xL_k >= b_j (if a_ji < 0 and (>)) a_ji xL_i + sum {k in I+} a_jk xL_k + sum {k in I-} a_jk xU_k <= b_j (if a_ji < 0 and (<))

No other cuts are needed.

Definition at line 436 of file FixPointGenCuts.cpp.

Member Data Documentation

bool Couenne::CouenneFixPoint::extendedModel_

protected

should we use an extended model or a more compact one?

Definition at line 63 of file CouenneFixPoint.hpp.

CouenneProblem* Couenne::CouenneFixPoint::problem_

protected

pointer to the CouenneProblem representation

Definition at line 66 of file CouenneFixPoint.hpp.

bool Couenne::CouenneFixPoint::firstCall_

mutableprotected

Is this the first call?

Definition at line 69 of file CouenneFixPoint.hpp.

double Couenne::CouenneFixPoint::CPUtime_

mutableprotected

CPU time.

Definition at line 72 of file CouenneFixPoint.hpp.

int Couenne::CouenneFixPoint::nTightened_

mutableprotected

Number of bounds tightened.

Definition at line 75 of file CouenneFixPoint.hpp.

int Couenne::CouenneFixPoint::levelStop_

protected

Level at which to stop.

Definition at line 78 of file CouenneFixPoint.hpp.

CouenneBTPerfIndicator Couenne::CouenneFixPoint::perfIndicator_

protected

Performance indicator.

Definition at line 92 of file CouenneFixPoint.hpp.

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

/tmp/OS-2.10.2/Couenne/src/bound_tightening/CouenneFixPoint.hpp
/tmp/OS-2.10.2/Couenne/src/bound_tightening/FixPointConstructors.cpp
/tmp/OS-2.10.2/Couenne/src/bound_tightening/FixPointGenCuts.cpp

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation