ConicBundle
Classes | Functions | Variables
implemention of MatrixFunctionOracle (NNCBoxSupportFunction)

NNCBoxSupportFunction is an example implementation of ConicBundle::MatrixFunctionOracle for the minimization of the support function over a box (it is, however, recommended to use a BoxOracle instead, which should be more efficient). It may be used for Lagrangian relaxation of linear programs over boxes or, using FunctionTask::AdaptivePenaltyFunction, over unbounded domains with finite optima. More...

Classes

class  ConicBundle::NNCBoxSupportMinorantExtender
 Implementation of MinorantExtender for NNCBoxSupportFunction. More...
 
class  ConicBundle::NNCBoxSupportFunction
 general purpose implementation of MatrixFunctionOracle as explained in implemention of MatrixFunctionOracle (NNCBoxSupportFunction) (see, however, the likely better choice of a BoxOracle) More...
 
class  ConicBundle::NNCBoxSupportModification
 Collects modifications for NNCBoxSupport for appending, deleting or reassigning variables and respective upper and lower bounds. More...
 

Functions

 ConicBundle::NNCBoxSupportMinorantExtender::NNCBoxSupportMinorantExtender (NNCBoxSupportFunction *fun)
 the NNCBoxSupportFunction pointed to has to be valid for the livetime of this object
 
int ConicBundle::NNCBoxSupportMinorantExtender::extend (Minorant &minorant, int n_coords, const int *indices)
 called by ConicBundle to update internal Minorant objects, has to return 0 on success More...
 
int ConicBundle::NNCBoxSupportFunction::apply_modification (const NNCBoxSupportModification &mod)
 applies the NNCBoxSupportModfication mod to the current function
 

Variables

NNCBoxSupportFunctionConicBundle::NNCBoxSupportMinorantExtender::fun
 the oracle this MinorantExtender was generated by, needed for retrieving problem data
 
CH_Matrix_Classes::Matrix ConicBundle::NNCBoxSupportFunction::lb
 column vector of lower bounds
 
CH_Matrix_Classes::Matrix ConicBundle::NNCBoxSupportFunction::ub
 column vector of upper bounds
 

Initialization

 ConicBundle::NNCBoxSupportFunction::NNCBoxSupportFunction (const CH_Matrix_Classes::Matrix &lb, const CH_Matrix_Classes::Matrix &ub, const CBout *cb=0, int incr=-1)
 intialize with lower bounds vector lb and upper bounds vector ub (and output options), both must be column vectors of the same length and lb<=ub componentwise, length 0 results in objective value 0
 
 ConicBundle::NNCBoxSupportFunction::~NNCBoxSupportFunction ()
 

Implementations of MatrixFunctionOracle routines

int ConicBundle::NNCBoxSupportFunction::evaluate (const CH_Matrix_Classes::Matrix &current_point, CH_Matrix_Classes::Real relprec, CH_Matrix_Classes::Real &objective_value, std::vector< Minorant *> &minorants, PrimalExtender *&primal_extender)
 see MatrixFunctionOracle::evaluate()
 
virtual int ConicBundle::NNCBoxSupportFunction::apply_modification (const OracleModification &oracle_modification, const CH_Matrix_Classes::Matrix *new_center, const CH_Matrix_Classes::Matrix *old_center, bool &discard_objective_in_center, bool &discard_model, bool &discard_aggregates, MinorantExtender *&minorant_extender)
 see MatrixFunctionOracle::apply_modification() for the general use, here oracle_modification has a special role if it can be cast to an AMFModification More...
 
virtual bool ConicBundle::NNCBoxSupportFunction::check_correctness () const
 see MatrixFunctionOracle::check_correctness() (true only needed for debugging)
 

routines for querying data of the problem

const CH_Matrix_Classes::MatrixConicBundle::NNCBoxSupportFunction::get_lower_bounds ()
 returns the column vector of lower bounds
 
const CH_Matrix_Classes::MatrixConicBundle::NNCBoxSupportFunction::get_upper_bounds ()
 retunrs the column vector of upper bounds
 

routines for supporting input and output

void ConicBundle::NNCBoxSupportFunction::set_out (std::ostream *o=0, int pril=1)
 see ConicBundle::CBout
 
void ConicBundle::NNCBoxSupportFunction::set_cbout (const CBout *cb, int incr=-1)
 see ConicBundle::CBout
 
std::ostream & ConicBundle::NNCBoxSupportFunction::print_problem_data (std::ostream &out) const
 write the problem description to out so that it can be read again by read_problem_data()
 
std::istream & ConicBundle::NNCBoxSupportFunction::read_problem_data (std::istream &in)
 clear() and read the problem from in in the format written by print_problem_data()
 
std::ostream & ConicBundle::NNCBoxSupportFunction::print_problem_data_to_mfile (std::ostream &out, CH_Matrix_Classes::Integer blocknr) const
 undocumented highly volatile variant for external testing
 

Detailed Description

NNCBoxSupportFunction is an example implementation of ConicBundle::MatrixFunctionOracle for the minimization of the support function over a box (it is, however, recommended to use a BoxOracle instead, which should be more efficient). It may be used for Lagrangian relaxation of linear programs over boxes or, using FunctionTask::AdaptivePenaltyFunction, over unbounded domains with finite optima.

NOTE: For support functions over boxes the BoxOracle with its specialized BoxModel should be much better suited and more efficient. This is just an additional possible option and serves as a good example implementation of a MatricFunctionOracle.

The class NNCBoxSupportFunction implements a general purpose version of MatrixFunctionOracle for minimizing the support function

\[f:\mathbf{R}^n\to\mathbf{R},\quad f(\tilde c)=\max\{\tilde c^\top x\colon x\in[l,u]\},\]

where $l,u\in\mathbf{R}^n$ are given lower and upper bounds ( $l\le u$ componentwise). When adding this function to the solver by MatrixCBsolver::add_function(), one may specify a weight $\gamma>0$, a ConicBundle::FunctionTask, and an AffineFunctionTransformation $F\colon \mathbf{R}^m\to\mathbf{R}^n, F(y)=c+Ay$ for given $c\in\mathbf{R}^n$ and $A\in\mathbf{R}^{n\times m}$. Depending on the ConicBundle::FunctionTask, the solver actually minimizes the following:

The standard use of a NNCBoxSupportFunction is to fully initialize it on construction with the data l and u and then to add this function to the MatrixCBSolver. If dynamic changes to this NNCBoxSupportFunction are required afterwards (only adding and deleting box coordinates is allowed), use the class ConicBundle::NNCBoxSupportModification within the corresponding problem modification routines of the MatrixCBSolver interface.

The minorant generated for the input cost vector $\tilde c$ is a maximizing vertex of the box, so it is itself the basic primal data and no extram primal data is needed.

For facilitating input and output, NNCBoxSupportFunction offers

Function Documentation

◆ apply_modification()

virtual int ConicBundle::NNCBoxSupportFunction::apply_modification ( const OracleModification oracle_modification,
const CH_Matrix_Classes::Matrix new_center,
const CH_Matrix_Classes::Matrix old_center,
bool &  discard_objective_in_center,
bool &  discard_model,
bool &  discard_aggregates,
MinorantExtender *&  minorant_extender 
)
virtual

see MatrixFunctionOracle::apply_modification() for the general use, here oracle_modification has a special role if it can be cast to an AMFModification

if oracle_modification cannot be cast to an NNCBoxSupportModification it is assumed that all append modifications amount to have already been carried out on *this seperately before this routine is called. In particular, it is only checked whether the new dimension matches the one given by oracle_modification, the old dimension is ignored. If this does not hold, the routine stops with an error. Otherwise it checks the other stuff as if a suitable NNCBoxSupportModification has just been executed.

Reimplemented from ConicBundle::ModifiableOracleObject.

◆ extend()

int ConicBundle::NNCBoxSupportMinorantExtender::extend ( Minorant minorant,
int  n_coords,
const int *  indices 
)
virtual

called by ConicBundle to update internal Minorant objects, has to return 0 on success

Parameters
[in,out]minorant(Minorant&) it holds a (possibly aggregated) minorant that was generated from minorants returned by oracle calls, e.g. as in FunctionOracle::evaluate() If PrimalData was provided in these minorants, this will be aggregated along and will also be available in this minorant.
[in]n_coords(int) the number of coordinate positions that have to be filled in
[out]indices(const int*) the indices of these coordinate positions (sorted in strictly increasing order)
Returns
  • 0 on success,
  • 1 if extension is impossible

Implements ConicBundle::MinorantExtender.