#include <CouenneTwoImplied.hpp>
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 | |
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. |
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
1) else
update with VL if necessary.
2) if then
3) else
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 173 of file CouenneTwoImplied.hpp.
CouenneTwoImplied::CouenneTwoImplied | ( | CouenneProblem * | , | |
JnlstPtr | , | |||
const Ipopt::SmartPtr< Ipopt::OptionsList > | ||||
) |
constructor
Definition at line 24 of file TwoImpliedConstructors.cpp.
References depthLevelling_, depthStopSeparate_, and nMaxTrials_.
Referenced by clone().
CouenneTwoImplied::CouenneTwoImplied | ( | const CouenneTwoImplied & | ) |
CouenneTwoImplied::~CouenneTwoImplied | ( | ) |
destructor
Definition at line 54 of file TwoImpliedConstructors.cpp.
References e, Couenne::J_COUENNE(), jnlst_, totalInitTime_, and totalTime_.
CouenneTwoImplied* Couenne::CouenneTwoImplied::clone | ( | ) | const [inline] |
clone method (necessary for the abstract CglCutGenerator class)
Definition at line 189 of file CouenneTwoImplied.hpp.
References CouenneTwoImplied().
void Couenne::CouenneTwoImplied::generateCuts | ( | const OsiSolverInterface & | , | |
OsiCuts & | , | |||
const | CglTreeInfo = CglTreeInfo() | |||
) | const |
the main CglCutGenerator
In principle, "si. getMatrixByCol ()" should be sufficient. However, there seems to be a bug (not sure where... Osi? Clp? Or, most probably, Couenne?) that doesn't return good values from A (and triggers Valgrind errors and segfaults on ex3_1_1 and others). While waiting for a fix, we'll use the row representation.
Update: we should probably stick to defining USE_ROW even when this is solved, as cuts from cs should also be added.
These will be used
these are the row-format originals
Prepare vector for integrality test. Since many checks are done within combine(), it is worth to prepare one here
Definition at line 59 of file TwoImpliedGenCuts.cpp.
References Couenne::t_chg_bounds::CHANGED, Couenne::combine(), COUENNE_EPS, COUENNE_INFINITY, depthLevelling_, depthStopSeparate_, e, firstCall_, Couenne::isInteger(), isWiped(), Couenne::J_COUENNE(), jnlst_, k, kk, m, n, nMaxTrials_, problem_, Couenne::t_chg_bounds::setLower(), Couenne::t_chg_bounds::setUpper(), totalInitTime_, totalTime_, Couenne::t_chg_bounds::UNCHANGED, Couenne::updateBranchInfo(), and WipeMakeInfeas().
void CouenneTwoImplied::registerOptions | ( | Ipopt::SmartPtr< Bonmin::RegisteredOptions > | roptions | ) | [static] |
Add list of options to be read from file.
Definition at line 62 of file TwoImpliedConstructors.cpp.
Referenced by Couenne::CouenneSetup::registerAllOptions().
CouenneProblem* Couenne::CouenneTwoImplied::problem_ [protected] |
pointer to problem data structure (used for post-BT)
Definition at line 203 of file CouenneTwoImplied.hpp.
Referenced by generateCuts().
JnlstPtr Couenne::CouenneTwoImplied::jnlst_ [protected] |
Journalist.
Definition at line 206 of file CouenneTwoImplied.hpp.
Referenced by generateCuts(), and ~CouenneTwoImplied().
int Couenne::CouenneTwoImplied::nMaxTrials_ [protected] |
maximum number of trials in every call
Definition at line 209 of file CouenneTwoImplied.hpp.
Referenced by CouenneTwoImplied(), and generateCuts().
double Couenne::CouenneTwoImplied::totalTime_ [mutable, protected] |
Total CPU time spent separating cuts.
Definition at line 212 of file CouenneTwoImplied.hpp.
Referenced by generateCuts(), and ~CouenneTwoImplied().
double Couenne::CouenneTwoImplied::totalInitTime_ [mutable, protected] |
CPU time spent columning the row formulation.
Definition at line 215 of file CouenneTwoImplied.hpp.
Referenced by generateCuts(), and ~CouenneTwoImplied().
bool Couenne::CouenneTwoImplied::firstCall_ [mutable, protected] |
first call indicator
Definition at line 218 of file CouenneTwoImplied.hpp.
Referenced by generateCuts().
int Couenne::CouenneTwoImplied::depthLevelling_ [protected] |
Depth of the BB tree where to start decreasing chance of running this.
Definition at line 221 of file CouenneTwoImplied.hpp.
Referenced by CouenneTwoImplied(), and generateCuts().
int Couenne::CouenneTwoImplied::depthStopSeparate_ [protected] |
Depth of the BB tree where stop separation.
Definition at line 224 of file CouenneTwoImplied.hpp.
Referenced by CouenneTwoImplied(), and generateCuts().