RsBundle  Check-in [2d05075c29]

 */

use bundle;
use env_logger;
use log::info;

use bundle::mcf;
use bundle::{DefaultSolver, FirstOrderProblem, SolverParams, StandardTerminator};

use std::env;

fn main() {
    env_logger::init();

    let mut args = env::args();

use std::error::Error;

use bundle::{self, dvec};
use env_logger;
use log::debug;

use bundle::{DVector, DefaultSolver, FirstOrderProblem, Minorant, Real, SimpleEvaluation, SolverParams};

struct QuadraticProblem {
    a: [[Real; 2]; 2],
    b: [Real; 2],
    c: Real,
}

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use crate::{DVector, Minorant, Real};

use std::error::Error;

use std::result;

// /// Error type for master problems.
// #[derive(Debug)]
// pub enum MasterProblemError {
//     /// Extension of the subgradient failed with some user error.
//     SubgradientExtension(Box<dyn Error + Send + Sync>),
//     /// No minorants available when solving the master problem
//     NoMinorants,
//     /// An error in the solver backend occurred.
//     Solver(Box<dyn Error + Send + Sync>),
//     /// A custom error (specific to the master problem solver) occurred.
//     Custom(Box<dyn Error + Send + Sync>),
// }


// impl fmt::Display for MasterProblemError {
//     fn fmt(&self, fmt: &mut fmt::Formatter) -> result::Result<(), fmt::Error> {
//         use self::MasterProblemError::*;
//         match self {
//             SubgradientExtension(err) => write!(fmt, "Subgradient extension failed: {}", err),
//             NoMinorants => write!(fmt, "No minorants when solving the master problem"),
//             Solver(err) => write!(fmt, "Solver error: {}", err),
//             Custom(err) => err.fmt(fmt),
//         }
//     }
// }




// impl Error for MasterProblemError {
//     fn source(&self) -> Option<&(dyn Error + 'static)> {
//         use self::MasterProblemError::*;
//         match self {
//             SubgradientExtension(err) => Some(err.as_ref()),
//             Solver(err) | Custom(err) => Some(err.as_ref()),
//             NoMinorants => None,



//         }
//     }
// }


/// Callback for subgradient extensions.
pub type SubgradientExtension<'a, I> =
    FnMut(usize, I, &[usize]) -> result::Result<DVector, Box<dyn Error + Send + Sync + 'static>> + 'a;

pub trait MasterProblem {
    /// Unique index for a minorant.
    type MinorantIndex: Copy + Eq;

    /// The error returned by the master problem.
    type Err;

    /// Create a new master problem.
    fn new() -> Result<Self, Self::Err>
    where
        Self: Sized;

    /// Set the number of subproblems.
    fn set_num_subproblems(&mut self, n: usize) -> Result<(), Self::Err>;

    /// Set the lower and upper bounds of the variables.
    fn set_vars(&mut self, nvars: usize, lb: Option<DVector>, ub: Option<DVector>) -> Result<(), Self::Err>;

    /// Return the current number of minorants of subproblem `fidx`.
    fn num_minorants(&self, fidx: usize) -> usize;

    /// Return the current weight of the quadratic term.
    fn weight(&self) -> Real;

    /// Set the weight of the quadratic term, must be > 0.
    fn set_weight(&mut self, weight: Real) -> Result<(), Self::Err>;

    /// Set the maximal number of inner iterations.
    fn set_max_updates(&mut self, max_updates: usize) -> Result<(), Self::Err>;

    /// Return the current number of inner iterations.
    fn cnt_updates(&self) -> usize;

    /// Add or move some variables with bounds.
    ///
    /// If an index is specified, existing variables are moved,
    /// otherwise new variables are generated.
    fn add_vars(
        &mut self,
        bounds: &[(Option<usize>, Real, Real)],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex>,
    ) -> Result<(), Self::Err>;

    /// Add a new minorant to the model.
    ///
    /// The function returns a unique (among all minorants of all
    /// subproblems) index of the minorant. This index must remain
    /// valid until the minorant is aggregated.
    fn add_minorant(&mut self, fidx: usize, minorant: Minorant) -> Result<Self::MinorantIndex, Self::Err>;

    /// Solve the master problem.
    fn solve(&mut self, cur_value: Real) -> Result<(), Self::Err>;

    /// 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>;

    /// Return the (primal) optimal solution $\\|d\^*\\|$.
    fn get_primopt(&self) -> DVector;

    /// Return the value of the linear model in the optimal solution.
    ///
    /// This is the term $\langle g\^*, d\^* \rangle$ where $g^\*$ is

// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use crate::master::UnconstrainedMasterProblem;
use crate::master::{MasterProblem, SubgradientExtension};
use crate::{DVector, Minorant, Real};



use itertools::multizip;
use log::debug;
use std::f64::{EPSILON, INFINITY, NEG_INFINITY};

/**
 * Turn unconstrained master problem into box-constrained one.
 *

            max_updates: 100,
            cnt_updates: 0,
            need_new_candidate: true,
            master,
        }
    }

    pub fn set_max_updates(&mut self, max_updates: usize) -> Result<(), M::Err> {
        assert!(max_updates > 0);
        self.max_updates = max_updates;
        Ok(())
    }

    /**
     * Update box multipliers $\eta$.

impl<M> MasterProblem for BoxedMasterProblem<M>
where
    M: UnconstrainedMasterProblem,
{
    type MinorantIndex = M::MinorantIndex;

    type Err = M::Err;

    fn new() -> Result<Self, Self::Err> {
        M::new().map(BoxedMasterProblem::with_master)
    }

    fn set_num_subproblems(&mut self, n: usize) -> Result<(), Self::Err> {
        self.master.set_num_subproblems(n)
    }

    fn set_vars(&mut self, n: usize, lb: Option<DVector>, ub: Option<DVector>) -> Result<(), Self::Err> {
        assert_eq!(lb.as_ref().map(|x| x.len()).unwrap_or(n), n);
        assert_eq!(ub.as_ref().map(|x| x.len()).unwrap_or(n), n);
        self.lb = lb.unwrap_or_else(|| dvec![NEG_INFINITY; n]);
        self.ub = ub.unwrap_or_else(|| dvec![INFINITY; n]);
        Ok(())
    }

    fn num_minorants(&self, fidx: usize) -> usize {
        self.master.num_minorants(fidx)
    }

    fn add_minorant(&mut self, fidx: usize, minorant: Minorant) -> Result<Self::MinorantIndex, Self::Err> {
        self.master.add_minorant(fidx, minorant)
    }

    fn weight(&self) -> Real {
        self.master.weight()
    }

    fn set_weight(&mut self, weight: Real) -> Result<(), Self::Err> {
        self.master.set_weight(weight)
    }

    fn add_vars(
        &mut self,
        bounds: &[(Option<usize>, Real, Real)],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex>,
    ) -> Result<(), Self::Err> {
        if !bounds.is_empty() {
            for (index, l, u) in bounds.iter().filter_map(|v| v.0.map(|i| (i, v.1, v.2))) {
                self.lb[index] = l;
                self.ub[index] = u;
            }
            self.lb.extend(bounds.iter().filter(|v| v.0.is_none()).map(|x| x.1));
            self.ub.extend(bounds.iter().filter(|v| v.0.is_none()).map(|x| x.2));
            self.eta.resize(self.lb.len(), 0.0);
            self.need_new_candidate = true;
            let nnew = bounds.iter().filter(|v| v.0.is_none()).count();
            let changed = bounds.iter().filter_map(|v| v.0).collect::<Vec<_>>();
            self.master.add_vars(nnew, &changed, extend_subgradient)
        } else {
            Ok(())
        }
    }

    #[allow(clippy::cognitive_complexity)]
    fn solve(&mut self, center_value: Real) -> Result<(), Self::Err> {
        debug!("Solve Master");
        debug!("  lb      ={}", self.lb);
        debug!("  ub      ={}", self.ub);

        if self.need_new_candidate {
            self.compute_candidate();
        }

        debug!("  dualopt={}", self.master.dualopt());
        debug!("  etaopt={}", self.eta);
        debug!("  primoptval={}", self.primoptval);

        Ok(())
    }

    fn aggregate(&mut self, fidx: usize, mins: &[usize]) -> Result<(Self::MinorantIndex, DVector), Self::Err> {
        self.master.aggregate(fidx, mins)
    }

    fn get_primopt(&self) -> DVector {
        self.primopt.clone()
    }

    fn move_center(&mut self, alpha: Real, d: &DVector) {
        self.need_new_candidate = true;
        self.master.move_center(alpha, d);
        self.lb.add_scaled(-alpha, d);
        self.ub.add_scaled(-alpha, d);
    }

    fn set_max_updates(&mut self, max_updates: usize) -> Result<(), Self::Err> {
        BoxedMasterProblem::set_max_updates(self, max_updates)
    }

    fn cnt_updates(&self) -> usize {
        self.cnt_updates
    }
}

// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! Master problem implementation using CPLEX.

#![allow(unused_unsafe)]

use crate::master::{SubgradientExtension, UnconstrainedMasterProblem};
use crate::{Aggregatable, DVector, Minorant, Real};



use c_str_macro::c_str;
use cplex_sys as cpx;
use cplex_sys::trycpx;
use log::debug;

use std;
use std::f64::{self, NEG_INFINITY};
use std::os::raw::{c_char, c_int};
use std::ptr;

#[derive(Debug)]
pub enum CplexMasterError {
    Cplex(cpx::CplexError),
    SubgradientExtension(Box<dyn std::error::Error + Send + Sync>),
    NoMinorants,
}

impl std::fmt::Display for CplexMasterError {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
        use CplexMasterError::*;
        match self {
            Cplex(err) => err.fmt(fmt),
            SubgradientExtension(err) => write!(fmt, "Subgradient extension failed: {}", err),
            NoMinorants => write!(fmt, "Master problem contains no minorants"),
        }
    }
}

impl std::error::Error for CplexMasterError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        use CplexMasterError::*;
        match self {
            Cplex(err) => Some(err),
            SubgradientExtension(err) => Some(err.as_ref()),
            NoMinorants => None,
        }
    }
}

impl From<cpx::CplexError> for CplexMasterError {
    fn from(err: cpx::CplexError) -> Self {
        CplexMasterError::Cplex(err)
    }
}

pub type Result<T> = std::result::Result<T, CplexMasterError>;

pub struct CplexMaster {
    lp: *mut cpx::Lp,

    /// True if the QP must be updated.
    force_update: bool,

    fn drop(&mut self) {
        unsafe { cpx::freeprob(cpx::env(), &mut self.lp) };
    }
}

impl UnconstrainedMasterProblem for CplexMaster {
    type MinorantIndex = usize;

    type Err = CplexMasterError;

    fn new() -> Result<CplexMaster> {
        Ok(CplexMaster {
            lp: ptr::null_mut(),
            force_update: true,
            freeinds: vec![],
            updateinds: vec![],

        let mut changedvars = vec![];
        changedvars.extend_from_slice(changed);
        changedvars.extend(noldvars..nnewvars);
        for (fidx, mins) in self.minorants.iter_mut().enumerate() {
            if !mins.is_empty() {
                for (i, m) in mins.iter_mut().enumerate() {
                    let new_subg =
                        extend_subgradient(fidx, i, &changedvars).map_err(CplexMasterError::SubgradientExtension)?;
                    for (&j, &g) in changed.iter().zip(new_subg.iter()) {
                        m.linear[j] = g;
                    }
                    m.linear.extend_from_slice(&new_subg[changed.len()..]);
                }
            }
        }

    fn solve(&mut self, eta: &DVector, _fbound: Real, _augbound: Real, _relprec: Real) -> Result<()> {
        if self.force_update || !self.updateinds.is_empty() {
            self.init_qp()?;
        }

        let nvars = unsafe { cpx::getnumcols(cpx::env(), self.lp) as usize };
        if nvars == 0 {
            return Err(CplexMasterError::NoMinorants);
        }
        // update linear costs
        {
            let mut c = Vec::with_capacity(nvars);
            let mut inds = Vec::with_capacity(nvars);
            for mins in &self.minorants {
                for m in mins {

// 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/>
//

use crate::master::{SubgradientExtension, UnconstrainedMasterProblem};
use crate::{Aggregatable, DVector, Minorant, Real};



use log::debug;

use std::error::Error;
use std::f64::NEG_INFINITY;
use std::fmt;
use std::result;

/// Minimal master problem error.
#[derive(Debug)]
pub enum MinimalMasterError {
    NumSubproblems { nsubs: usize },
    NoMinorants,
    MaxMinorants,
    SubgradientExtension(Box<dyn Error + Send + Sync>),
}

impl fmt::Display for MinimalMasterError {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> result::Result<(), fmt::Error> {
        use self::MinimalMasterError::*;
        match self {
            NumSubproblems { nsubs } => write!(fmt, "Too many subproblems (got: {} must be <= 2)", nsubs),
            MaxMinorants => write!(fmt, "The minimal master problem allows at most two minorants"),
            NoMinorants => write!(fmt, "The master problem does not contain a minorant"),
            SubgradientExtension(err) => write!(fmt, "Subgradient extension failed: {}", err),
        }
    }
}

impl Error for MinimalMasterError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        use MinimalMasterError::*;
        match self {
            SubgradientExtension(err) => Some(err.as_ref()),
            _ => None,
        }



    }
}

/**
 * A minimal master problem with only two minorants.
 *
 * This is the simplest possible master problem for bundle methods. It

    /// Optimal aggregated minorant.
    opt_minorant: Minorant,
}

impl UnconstrainedMasterProblem for MinimalMaster {
    type MinorantIndex = usize;

    type Err = MinimalMasterError;

    fn new() -> Result<MinimalMaster, Self::Err> {
        Ok(MinimalMaster {
            weight: 1.0,
            minorants: vec![],
            opt_mult: dvec![],
            opt_minorant: Minorant::default(),
        })
    }

    fn num_subproblems(&self) -> usize {
        1
    }

    fn set_num_subproblems(&mut self, n: usize) -> Result<(), Self::Err> {
        if n != 1 {
            Err(MinimalMasterError::NumSubproblems { nsubs: n })
        } else {
            Ok(())
        }
    }

    fn weight(&self) -> Real {
        self.weight
    }

    fn set_weight(&mut self, weight: Real) -> Result<(), Self::Err> {
        assert!(weight > 0.0);
        self.weight = weight;
        Ok(())
    }

    fn num_minorants(&self, fidx: usize) -> usize {
        assert_eq!(fidx, 0);
        self.minorants.len()
    }

    fn add_minorant(&mut self, fidx: usize, minorant: Minorant) -> Result<usize, Self::Err> {
        assert_eq!(fidx, 0);
        if self.minorants.len() >= 2 {
            return Err(MinimalMasterError::MaxMinorants);
        }
        self.minorants.push(minorant);
        self.opt_mult.push(0.0);
        Ok(self.minorants.len() - 1)
    }

    fn add_vars(
        &mut self,
        nnew: usize,
        changed: &[usize],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex>,
    ) -> Result<(), Self::Err> {
        if !self.minorants.is_empty() {
            let noldvars = self.minorants[0].linear.len();
            let mut changedvars = vec![];
            changedvars.extend_from_slice(changed);
            changedvars.extend(noldvars..noldvars + nnew);
            for (i, m) in self.minorants.iter_mut().enumerate() {
                let new_subg =
                    extend_subgradient(0, i, &changedvars).map_err(MinimalMasterError::SubgradientExtension)?;
                for (&j, &g) in changed.iter().zip(new_subg.iter()) {
                    m.linear[j] = g;
                }
                m.linear.extend_from_slice(&new_subg[changed.len()..]);
            }
        }

        Ok(())
    }

    #[allow(unused_variables)]
    fn solve(&mut self, eta: &DVector, fbound: Real, augbound: Real, relprec: Real) -> Result<(), Self::Err> {
        for (i, m) in self.minorants.iter().enumerate() {
            debug!("  {}:min[{},{}] = {}", i, 0, 0, m);
        }

        if self.minorants.len() == 2 {
            let xx = self.minorants[0].linear.dot(&self.minorants[0].linear);
            let yy = self.minorants[1].linear.dot(&self.minorants[1].linear);

            self.opt_mult[1] = alpha2;
            self.opt_minorant = Aggregatable::combine(self.opt_mult.iter().cloned().zip(&self.minorants));
        } else if self.minorants.len() == 1 {
            self.opt_minorant = self.minorants[0].clone();
            self.opt_mult.resize(1, 1.0);
            self.opt_mult[0] = 1.0;
        } else {
            return Err(MinimalMasterError::NoMinorants);
        }

        debug!("Unrestricted");
        debug!("  opt_minorant={}", self.opt_minorant);
        if self.opt_mult.len() == 2 {
            debug!("  opt_mult={}", self.opt_mult);
        }

        let mut result = NEG_INFINITY;
        for m in &self.minorants {
            result = result.max(m.eval(y));
        }
        result
    }

    fn aggregate(&mut self, fidx: usize, mins: &[usize]) -> Result<(usize, DVector), Self::Err> {
        assert_eq!(fidx, 0);
        if mins.len() == 2 {
            debug!("Aggregate");
            debug!("  {} * {}", self.opt_mult[0], self.minorants[0]);
            debug!("  {} * {}", self.opt_mult[1], self.minorants[1]);
            self.minorants[0] = Aggregatable::combine(self.opt_mult.iter().cloned().zip(&self.minorants));
            self.minorants.truncate(1);

//! * changing the weight parameter $w$,
//! * modifying $\hat{f}$ by adding or removing linear functions $\ell_i$,
//! * moving the center of the linear functions $\ell_i$ (and the
//!   bounds), i.e. replacing $\hat{f}$ by $d \mapsto \hat{f}(d -
//!   \hat{d})$ for some given $\hat{d} \in \mathbb{R}\^n$.

mod base;
pub use self::base::{MasterProblem, SubgradientExtension};

mod boxed;
pub use self::boxed::BoxedMasterProblem;

mod unconstrained;
pub use self::unconstrained::UnconstrainedMasterProblem;

//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use crate::{DVector, Minorant, Real};

use super::SubgradientExtension;

/**
 * Trait for master problems without box constraints.
 *
 * Implementors of this trait are supposed to solve quadratic
 * optimization problems of the form
 *

 *
 * \\[ \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 {
    /// Unique index for a minorant.
    type MinorantIndex: Copy + Eq;

    /// Error type for this master problem.
    type Err;

    /// 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;

    /// 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(
        &mut self,
        nnew: usize,
        changed: &[usize],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex>,
    ) -> Result<(), Self::Err>;

    /// 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;

    /// 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);
}

use num_cpus;
use std::sync::Arc;
use threadpool::ThreadPool;

use crate::{DVector, Minorant, Real};

use super::problem::{EvalResult, FirstOrderProblem};
use crate::master::{BoxedMasterProblem, CplexMaster, MasterProblem, UnconstrainedMasterProblem};



/// The default iteration limit.
pub const DEFAULT_ITERATION_LIMIT: usize = 10_000;

type MasterProblemError = <BoxedMasterProblem<CplexMaster> as MasterProblem>::Err;

/// Error raised by the parallel bundle [`Solver`].
#[derive(Debug)]
pub enum Error<E> {
    /// An error raised by the master problem process.
    Master(MasterProblemError),
    /// The iteration limit has been reached.

            //Master(err) => Some(err),
            Evaluation(err) => Some(err),
            _ => None,
        }
    }
}










/// A task for the master problem.
enum MasterTask {
    /// Add a new minorant for a subfunction to the master problem.
    AddMinorant(usize, Minorant),

    /// Move the center of the master problem in the given direction.
    MoveCenter(Real, Arc<DVector>),

//! The main bundle method solver.

use crate::{Aggregatable, DVector, Real};
use crate::{Evaluation, FirstOrderProblem, HKWeighter, Update};

use crate::master::CplexMaster;
use crate::master::{BoxedMasterProblem, MasterProblem, MinimalMaster};



use log::{debug, info, warn};

use std::error::Error;
use std::f64::{INFINITY, NEG_INFINITY};
use std::fmt;
use std::mem::swap;
use std::result::Result;
use std::time::Instant;

/// A solver error.
#[derive(Debug)]
pub enum SolverError<E, MErr> {
    /// An error occurred during oracle evaluation.
    Evaluation(E),
    /// An error occurred during oracle update.
    Update(E),
    /// An error has been raised by the master problem.
    Master(MErr),
    /// The oracle did not return a minorant.
    NoMinorant,
    /// The dimension of some data is wrong.
    Dimension,
    /// Some parameter has an invalid value.
    Parameter(ParameterError),
    /// The lower bound of a variable is larger than the upper bound.
    InvalidBounds { lower: Real, upper: Real },
    /// The value of a variable is outside its bounds.
    ViolatedBounds { lower: Real, upper: Real, value: Real },
    /// The variable index is out of bounds.
    InvalidVariable { index: usize, nvars: usize },
    /// Iteration limit has been reached.
    IterationLimit { limit: usize },
}

impl<E, MErr> fmt::Display for SolverError<E, MErr>
where
    E: fmt::Display,
    MErr: fmt::Display,
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        use self::SolverError::*;
        match self {
            Evaluation(err) => write!(fmt, "Oracle evaluation failed: {}", err),
            Update(err) => write!(fmt, "Oracle update failed: {}", err),
            Master(err) => write!(fmt, "Master problem failed: {}", err),
            NoMinorant => write!(fmt, "The oracle did not return a minorant"),

                write!(fmt, "Variable index out of bounds, got:{} must be < {}", index, nvars)
            }
            IterationLimit { limit } => write!(fmt, "The iteration limit of {} has been reached.", limit),
        }
    }
}

impl<E, MErr> Error for SolverError<E, MErr>
where
    E: Error + 'static,
    MErr: Error + 'static,
{
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            SolverError::Evaluation(err) => Some(err),
            SolverError::Update(err) => Some(err),
            SolverError::Master(err) => Some(err),
            _ => None,
        }
    }
}

impl<E, MErr> From<MErr> for SolverError<E, MErr> {
    fn from(err: MErr) -> SolverError<E, MErr> {






        SolverError::Master(err)
    }
}

/**
 * The current state of the bundle method.
 *

}

impl<P, M> Solver<P, M>
where
    P: FirstOrderProblem,
    P::Err: Into<Box<std::error::Error + Send + Sync + 'static>>,
    M: MasterProblem<MinorantIndex = usize>,
    M::Err: Into<Box<std::error::Error + Send + Sync + 'static>>,
{
    /**
     * Create a new solver for the given problem.
     *
     * Note that the solver owns the problem, so you cannot use the
     * same problem description elsewhere as long as it is assigned to
     * the solver. However, it is possible to get a reference to the
     * internally stored problem using `Solver::problem()`.
     */
    pub fn new_params(problem: P, params: SolverParams) -> Result<Solver<P, M>, SolverError<P::Err, M::Err>> {

        Ok(Solver {
            problem,
            params,
            terminator: Box::new(StandardTerminator {
                termination_precision: 1e-3,
            }),
            weighter: Box::new(HKWeighter::new()),

            nxt_mods: dvec![],
            new_cutval: 0.0,
            sgnorm: 0.0,
            expected_progress: 0.0,
            cnt_descent: 0,
            cnt_null: 0,
            start_time: Instant::now(),
            master: M::new()?,
            minorants: vec![],
            iterinfos: vec![],
        })
    }

    /// A new solver with default parameter.
    pub fn new(problem: P) -> Result<Solver<P, M>, SolverError<P::Err, M::Err>> {
        Solver::new_params(problem, SolverParams::default())
    }

    /**
     * Set the first order problem description associated with this
     * solver.
     *

    /// Returns a reference to the solver's current problem.
    pub fn problem(&self) -> &P {
        &self.problem
    }

    /// Initialize the solver.
    pub fn init(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        self.params.check().map_err(SolverError::Parameter)?;
        if self.cur_y.len() != self.problem.num_variables() {
            self.cur_valid = false;
            self.cur_y.init0(self.problem.num_variables());
        }

        let lb = self.problem.lower_bounds();
        let ub = self.problem.upper_bounds();

        Ok(())
    }

    /// Solve the problem with at most 10_000 iterations.
    ///
    /// Use `solve_with_limit` for an explicit iteration limit.
    pub fn solve(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        const LIMIT: usize = 10_000;
        self.solve_with_limit(LIMIT)
    }

    /// Solve the problem with explicit iteration limit.
    pub fn solve_with_limit(&mut self, iter_limit: usize) -> Result<(), SolverError<P::Err, M::Err>> {
        // First initialize the internal data structures.
        self.init()?;

        if self.solve_iter(iter_limit)? {
            Ok(())
        } else {
            Err(SolverError::IterationLimit { limit: iter_limit })
        }
    }

    /// Solve the problem but stop after `niter` iterations.
    ///
    /// The function returns `Ok(true)` if the termination criterion
    /// has been satisfied. Otherwise it returns `Ok(false)` or an
    /// error code.
    ///
    /// If this function is called again, the solution process is
    /// continued from the previous point. Because of this one must
    /// call `init()` before the first call to this function.
    pub fn solve_iter(&mut self, niter: usize) -> Result<bool, SolverError<P::Err, M::Err>> {
        for _ in 0..niter {
            let mut term = self.step()?;
            let changed = self.update_problem(term)?;
            // do not stop if the problem has been changed
            if changed && term == Step::Term {
                term = Step::Null
            }
            self.show_info(term);
            if term == Step::Term {
                return Ok(true);
            }
        }
        Ok(false)
    }

    /// Called to update the problem.
    ///
    /// Calling this function typically triggers the problem to
    /// separate new constraints depending on the current solution.
    fn update_problem(&mut self, term: Step) -> Result<bool, SolverError<P::Err, M::Err>> {
        let updates = {
            let state = UpdateState {
                minorants: &self.minorants,
                step: term,
                iteration_info: &self.iterinfos,
                // this is a dirty trick: when updating the center, we
                // simply swapped the `cur_*` fields with the `nxt_*`

    /**
     * Initializes the master problem.
     *
     * The oracle is evaluated once at the initial center and the
     * master problem is initialized with the returned subgradient
     * information.
     */
    fn init_master(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        let m = self.problem.num_subproblems();

        let lb = self.problem.lower_bounds().map(DVector);
        let ub = self.problem.upper_bounds().map(DVector);

        if lb
            .as_ref()

        debug!("Init master completed");

        Ok(())
    }

    /// Solve the model (i.e. master problem) to compute the next candidate.
    fn solve_model(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        self.master.solve(self.cur_val)?;
        self.nxt_d = self.master.get_primopt();
        self.nxt_y.add(&self.cur_y, &self.nxt_d);
        self.nxt_mod = self.master.get_primoptval();
        self.sgnorm = self.master.get_dualoptnorm2().sqrt();
        self.expected_progress = self.cur_val - self.nxt_mod;

        debug!("  cur_val ={}", self.cur_val);
        debug!("  nxt_mod ={}", self.nxt_mod);
        debug!("  expected={}", self.expected_progress);
        Ok(())
    }

    /// Reduce size of bundle.
    fn compress_bundle(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        for i in 0..self.problem.num_subproblems() {
            let n = self.master.num_minorants(i);
            if n >= self.params.max_bundle_size {
                // aggregate minorants with smallest coefficients
                self.minorants[i].sort_by_key(|m| -((1e6 * m.multiplier) as isize));
                let aggr = self.minorants[i].split_off(self.params.max_bundle_size - 2);
                let aggr_sum = aggr.iter().map(|m| m.multiplier).sum();

                });
            }
        }
        Ok(())
    }

    /// Perform a descent step.
    fn descent_step(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        let new_weight = self.weighter.weight(&current_state!(self, Step::Descent), &self.params);
        self.master.set_weight(new_weight)?;
        self.cnt_descent += 1;
        swap(&mut self.cur_y, &mut self.nxt_y);
        swap(&mut self.cur_val, &mut self.nxt_val);
        swap(&mut self.cur_mod, &mut self.nxt_mod);
        swap(&mut self.cur_vals, &mut self.nxt_vals);
        swap(&mut self.cur_mods, &mut self.nxt_mods);
        self.master.move_center(1.0, &self.nxt_d);
        debug!("Descent Step");
        debug!("  dir ={}", self.nxt_d);
        debug!("  newy={}", self.cur_y);
        Ok(())
    }

    /// Perform a null step.
    fn null_step(&mut self) -> Result<(), SolverError<P::Err, M::Err>> {
        let new_weight = self.weighter.weight(&current_state!(self, Step::Null), &self.params);
        self.master.set_weight(new_weight)?;
        self.cnt_null += 1;
        debug!("Null Step");
        Ok(())
    }

    /// Perform one bundle iteration.
    #[allow(clippy::collapsible_if)]
    pub fn step(&mut self) -> Result<Step, SolverError<P::Err, M::Err>> {
        self.iterinfos.clear();

        if !self.cur_valid {
            // current point needs new evaluation
            self.init_master()?;
        }