// Copyright (c) 2016-2020 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>
//
pub mod cpx;
pub mod minimal;
use crate::{DVector, Minorant, Real};
pub use super::SubgradientExtension;
use either::Either;
use std::error::Error;
/**
* Trait for master problems without box constraints.
*
* Implementors of this trait are supposed to solve quadratic
* optimization problems of the form
*
* \\[ \min \left\\{ \hat{f}(d) + \frac{u}{2} \\| d \\|\^2 \colon
* d \in \mathbb{R}\^n \right\\}. \\]
*
* where $\hat{f}$ is a piecewise linear model, i.e.
*
* \\[ \hat{f}(d) = \max \\{ \ell_i(d) = c_i + \langle g_i, d \rangle \colon
* i=1,\dotsc,k \\}
* = \max \left\\{ \sum_{i=1}\^k \alpha_i \ell_i(d) \colon
* \alpha \in \Delta \right\\}, \\]
*
* where $\Delta := \left\\{ \alpha \in \mathbb{R}\^k \colon \sum_{i=1}\^k
* \alpha_i = 1 \right\\}$. Note, the unconstrained solver is expected
* to compute *dual* optimal solutions, i.e. the solver must compute
* optimal coefficients $\bar{\alpha}$ for the dual problem
*
* \\[ \max_{\alpha \in \Delta} \min_{d \in \mathbb{R}\^n}
* \sum_{i=1}\^k \alpha_i \ell_i(d) + \frac{u}{2} \\| d \\|\^2. \\]
*/
pub trait UnconstrainedMasterProblem: Send + 'static {
/// Unique index for a minorant.
type MinorantIndex: Copy + Eq;
/// Error type for this master problem.
type Err: Error + Send + Sync;
/// Return a new instance of the unconstrained master problem.
fn new() -> Result<Self, Self::Err>
where
Self: Sized;
/// Return the number of subproblems.
fn num_subproblems(&self) -> usize;
/// Set the number of subproblems (different function models.)
fn set_num_subproblems(&mut self, n: usize) -> Result<(), Self::Err>;
/// Return the current weight.
fn weight(&self) -> Real;
/// Set the weight of the quadratic term, must be > 0.
fn set_weight(&mut self, weight: Real) -> Result<(), Self::Err>;
/// Return the number of minorants of subproblem `fidx`.
fn num_minorants(&self, fidx: usize) -> usize;
/// Compress the bundle.
///
/// When some minorants are compressed, the callback is called with the
/// coefficients and indices of the compressed minorants and the index of
/// the new minorant. The callback may be called several times.
fn compress<F>(&mut self, f: F) -> Result<(), Self::Err>
where
F: FnMut(Self::MinorantIndex, &mut dyn Iterator<Item = (Self::MinorantIndex, Real)>);
/// Ensures that the aggregated submodels have the correct minorants.
///
/// If the model consists of aggregated submodels, each subproblem contained
/// in a submodel must have the same number of minorants. If this is not the case,
/// existing minorants (e.g. the aggregated minorant) is used for those submodels
/// that have too few.
fn fill_models<F>(&mut self, f: F) -> Result<(), Self::Err>
where
F: FnMut(Self::MinorantIndex, &mut dyn Iterator<Item = (Self::MinorantIndex, Real)>);
/// Add a new minorant to the model.
fn add_minorant(&mut self, fidx: usize, minorant: Minorant) -> Result<Self::MinorantIndex, Self::Err>;
/// Add or move some variables.
///
/// The variables in `changed` have been changed, so the subgradient
/// information must be updated. Furthermore, `nnew` new variables
/// are added.
fn add_vars<S>(
&mut self,
nnew: usize,
changed: &[usize],
extend_subgradient: S,
) -> Result<(), Either<Self::Err, S::Err>>
where
S: SubgradientExtension<Self::MinorantIndex>;
/// Solve the master problem.
fn solve(&mut self, eta: &DVector, fbound: Real, augbound: Real, relprec: Real) -> Result<(), Self::Err>;
/// Return the current dual optimal solution.
fn dualopt(&self) -> &DVector;
/// Return the current dual optimal solution value.
fn dualopt_cutval(&self) -> Real;
/// Return the multiplier associated with a minorant.
fn multiplier(&self, min: Self::MinorantIndex) -> Real;
/// Return the multipliers associated with a subproblem.
fn opt_multipliers<'a>(&'a self, fidx: usize) -> Box<dyn Iterator<Item = (Self::MinorantIndex, Real)> + 'a>;
/// Return the value of the current model at the given point.
fn eval_model(&self, y: &DVector) -> Real;
/// Return the value of the current model of a certain subproblem at the
/// given point.
fn eval_model_subproblem(&self, fidx: usize, y: &DVector) -> Real;
/// Aggregate the given minorants according to the current solution.
///
/// The (indices of the) minorants to be aggregated get invalid
/// after this operation. The function returns the index of the
/// aggregated minorant along with the coefficients of the convex
/// combination. The index of the new aggregated minorant might or
/// might not be one of indices of the original minorants.
///
/// # Error
/// The indices of the minorants `mins` must belong to subproblem `fidx`.
fn aggregate(&mut self, fidx: usize, mins: &[usize]) -> Result<(Self::MinorantIndex, DVector), Self::Err>;
/// Move the center of the master problem along $\alpha \cdot d$.
fn move_center(&mut self, alpha: Real, d: &DVector);
}
/// A builder for creating unconstrained master problem solvers.
pub trait Builder {
/// The master problem to be build.
type MasterProblem: UnconstrainedMasterProblem;
/// Create a new master problem.
fn build(&mut self) -> Result<Self::MasterProblem, <Self::MasterProblem as UnconstrainedMasterProblem>::Err>;
}