// 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::problem::SubgradientExtender;
use crate::{DVector, Minorant, Real};
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<M: Minorant>: Send + 'static {
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(&mut self) -> Result<(), Self::Err>;
/// 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: M) -> Result<Self::MinorantIndex, Self::Err>;
/// Add `nnew` new variables.
fn add_vars<SErr>(
&mut self,
nnew: usize,
extend_subgradient: &mut SubgradientExtender<M, SErr>,
) -> Result<(), Either<Self::Err, SErr>>;
/// 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 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;
/// Return the aggregated primal.
fn aggregated_primal(&self, fidx: usize) -> Result<M::Primal, 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<Mn: Minorant> {
/// The master problem to be build.
type MasterProblem: UnconstrainedMasterProblem<Mn>;
/// Create a new master problem.
fn build(&mut self) -> Result<Self::MasterProblem, <Self::MasterProblem as UnconstrainedMasterProblem<Mn>>::Err>;
}