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
NNCBoxSupportFunction *	ConicBundle::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::Matrix &	ConicBundle::NNCBoxSupportFunction::get_lower_bounds ()
	returns the column vector of lower bounds

const CH_Matrix_Classes::Matrix &	ConicBundle::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:

FunctionTask::ObjectiveFunction

$f_{\gamma,F}(y)=\gamma f(F(y))=\gamma\max\{(c+Ay)^\top x\colon x\in[l,u]\},$

If in setting up the groundset within MatrixCBSolver the variables are introduced with a linear cost vector $b\mathbf{R}^m$ and appropriate sign constraints, this corresponds to Lagrangian relaxation of the linear constraints in the linear program

$\mbox{maximize } c^\top x \mbox{ subject to } A^\top x \begin{array}{c}\le\\=\\\ge\end{array} b, x\in[\gamma l,\gamma u]$
FunctionTask::ConstantPenaltyFunction

$f^+_{\gamma,F}(y)=\gamma\max\{0,f(F(y))\},$

or, as above in the Lagrangean relaxation setting

$\mbox{maximize } c^\top x \mbox{ subject to } A^\top x \begin{array}{c}\le\\=\\\ge\end{array} b, x\in[\delta l,\delta u]\mbox{ with }0\le \delta\le \gamma$
FunctionTask::AdaptivePenaltyFunction

$f^+_{\infty,F}(y)=\gamma\max\{0,f(F(y))\}\mbox{ with }\gamma\to \infty.$

or, as above in the Lagrangean relaxation setting

$\mbox{maximize } c^\top x \mbox{ subject to } A^\top x \begin{array}{c}\le\\=\\\ge\end{array} b, x\in[\delta l,\delta u]\mbox{ with }0\le \delta\le \gamma \mbox{ and }\gamma\to \infty$

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

NNCBoxSupportFunction::print_problem_data() that outputs the full function description so that it can be read again by read_problem_data
NNCBoxSupportFunction::read_problem_data() reads the problem data as output by print_problem_data()
NNCBoxSupportFunction::set_out() and NNCBoxSupportFunction::set_cbout() work as described in ConicBundle::CBout

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.

Classes

Functions

Variables

Initialization

Implementations of MatrixFunctionOracle routines

routines for querying data of the problem

routines for supporting input and output

Detailed Description

Function Documentation

◆ apply_modification()

◆ extend()