RsBundle  Check-in [f6352834ce]

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

/// Error type for master problems.
#[derive(Debug)]
pub enum MasterProblemError<E> {
    /// Extension of the subgradient failed with some user error.
    SubgradientExtension(E),
    /// 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<E> fmt::Display for MasterProblemError<E>
where
    E: fmt::Display,
{
    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<E> Error for MasterProblemError<E>
where
    E: Error + 'static,
{
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        use self::MasterProblemError::*;
        match self {
            SubgradientExtension(err) => Some(err),
            Solver(err) | Custom(err) => Some(err.as_ref()),
            NoMinorants => None,
        }
    }
}

/// Result type of master problems.
pub type Result<T, E> = result::Result<T, MasterProblemError<E>>;

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


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

    /// Error returned by the subgradient-extension callback.
    type SubgradientExtensionErr;

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

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

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

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

    /// 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, Self::SubgradientExtensionErr>,
    ) -> Result<(), Self::SubgradientExtensionErr>;

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

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

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

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

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

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

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

        self.eta.dot(self.master.dualopt())
    }
}

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

    type SubgradientExtensionErr = M::SubgradientExtensionErr;

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

    fn set_vars(
        &mut self,
        n: usize,
        lb: Option<DVector>,
        ub: Option<DVector>,
    ) -> Result<(), Self::SubgradientExtensionErr> {
        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::SubgradientExtensionErr> {
        self.master.add_minorant(fidx, minorant)
    }

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

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

    fn add_vars(
        &mut self,
        bounds: &[(Option<usize>, Real, Real)],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex, Self::SubgradientExtensionErr>,
    ) -> Result<(), Self::SubgradientExtensionErr> {
        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::SubgradientExtensionErr> {
        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::SubgradientExtensionErr> {
        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::SubgradientExtensionErr> {
        BoxedMasterProblem::set_max_updates(self, max_updates)
    }

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

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::marker::PhantomData;
use std::os::raw::{c_char, c_int};
use std::ptr;

impl<E> From<cpx::CplexError> for MasterProblemError<E> {
    fn from(err: cpx::CplexError) -> MasterProblemError<E> {
        MasterProblemError::Solver(Box::new(err))
    }
}

pub struct CplexMaster<E> {
    lp: *mut cpx::Lp,

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

    /// List of free minorant indices.
    freeinds: Vec<usize>,

    /// The minorants for each subproblem in the model.
    minorants: Vec<Vec<Minorant>>,
    /// Optimal multipliers for each subproblem in the model.
    opt_mults: Vec<DVector>,
    /// Optimal aggregated minorant.
    opt_minorant: Minorant,

    phantom: PhantomData<E>,
}

impl<E> Drop for CplexMaster<E> {
    fn drop(&mut self) {
        unsafe { cpx::freeprob(cpx::env(), &mut self.lp) };
    }
}

impl<E> UnconstrainedMasterProblem for CplexMaster<E> {
    type MinorantIndex = usize;

    type SubgradientExtensionErr = E;

    fn new() -> Result<CplexMaster<E>, E> {
        Ok(CplexMaster {
            lp: ptr::null_mut(),
            force_update: true,
            freeinds: vec![],
            updateinds: vec![],
            min2index: vec![],
            index2min: vec![],
            qterm: vec![],
            weight: 1.0,
            minorants: vec![],
            opt_mults: vec![],
            opt_minorant: Minorant::default(),
            phantom: PhantomData,
        })
    }

    fn num_subproblems(&self) -> usize {
        self.minorants.len()
    }

    fn set_num_subproblems(&mut self, n: usize) -> Result<(), E> {
        trycpx!(cpx::setintparam(
            cpx::env(),
            cpx::Param::Qpmethod.to_c(),
            cpx::Alg::Barrier.to_c()
        ));
        trycpx!(cpx::setdblparam(cpx::env(), cpx::Param::Barepcomp.to_c(), 1e-12));

        self.min2index = vec![vec![]; n];
        self.index2min.clear();
        self.freeinds.clear();
        self.minorants = vec![vec![]; n];
        self.opt_mults = vec![dvec![]; n];

        Ok(())
    }

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

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

    fn num_minorants(&self, fidx: usize) -> usize {
        self.minorants[fidx].len()
    }

    fn add_minorant(&mut self, fidx: usize, minorant: Minorant) -> Result<usize, E> {
        debug!("Add minorant");
        debug!("  fidx={} index={}: {}", fidx, self.minorants[fidx].len(), minorant);

        let min_idx = self.minorants[fidx].len();
        self.minorants[fidx].push(minorant);
        self.opt_mults[fidx].push(0.0);

        }
    }

    fn add_vars(
        &mut self,
        nnew: usize,
        changed: &[usize],
        extend_subgradient: &mut SubgradientExtension<Self::MinorantIndex, Self::SubgradientExtensionErr>,
    ) -> Result<(), E> {
        debug_assert!(!self.minorants[0].is_empty());
        let noldvars = self.minorants[0][0].linear.len();
        let nnewvars = noldvars + nnew;

        let mut changedvars = vec![];
        changedvars.extend_from_slice(changed);
        changedvars.extend(noldvars..nnewvars);

        // WORST CASE: DO THIS
        // self.force_update = true;

        Ok(())
    }

    fn solve(&mut self, eta: &DVector, _fbound: Real, _augbound: Real, _relprec: Real) -> Result<(), E> {
        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(MasterProblemError::NoMinorants);

                this_val = this_val.max(m.eval(y));
            }
            result += this_val;
        }
        result
    }

    fn aggregate(&mut self, fidx: usize, mins: &[usize]) -> Result<(usize, DVector), E> {
        assert!(!mins.is_empty(), "No minorants specified to be aggregated");

        if mins.len() == 1 {
            return Ok((mins[0], dvec![1.0]));
        }

        // scale coefficients

            for m in mins.iter_mut() {
                m.move_center(alpha, d);
            }
        }
    }
}

impl<E> CplexMaster<E> {
    fn init_qp(&mut self) -> Result<(), E> {
        if !self.lp.is_null() {
            trycpx!(cpx::freeprob(cpx::env(), &mut self.lp));
        }
        trycpx!({
            let mut status = 0;
            self.lp = cpx::createprob(cpx::env(), &mut status, c_str!("mastercp").as_ptr());
            status

use super::Result;

use log::debug;

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

/// Minimal master problem error.
#[derive(Debug)]
pub enum MinimalMasterError {
    NumSubproblems { nsubs: usize },
    MaxMinorants,

            MaxMinorants => write!(fmt, "The minimal master problem allows at most two minorants"),
        }
    }
}

impl Error for MinimalMasterError {}

impl<E> From<MinimalMasterError> for MasterProblemError<E> {
    fn from(err: MinimalMasterError) -> MasterProblemError<E> {
        MasterProblemError::Custom(Box::new(err))
    }
}

/**
 * A minimal master problem with only two minorants.
 *
 * This is the simplest possible master problem for bundle methods. It
 * has only two minorants and only one function model. The advantage
 * is that this model can be solved explicitely and very quickly, but
 * it is only a very loose approximation of the objective function.
 *
 * Because of its properties, it can only be used if the problem to be
 * solved has a maximal number of minorants of two and only one
 * subproblem.
 */
pub struct MinimalMaster<E> {
    /// The weight of the quadratic term.
    weight: Real,

    /// The minorants in the model.
    minorants: Vec<Minorant>,
    /// Optimal multipliers.
    opt_mult: DVector,
    /// Optimal aggregated minorant.
    opt_minorant: Minorant,
    phantom: PhantomData<E>,
}

impl<E> UnconstrainedMasterProblem for MinimalMaster<E> {
    type MinorantIndex = usize;

    type SubgradientExtensionErr = E;

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

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

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

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

    fn set_weight(&mut self, weight: Real) -> Result<(), E> {
        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, E> {
        assert_eq!(fidx, 0);
        if self.minorants.len() >= 2 {
            return Err(MinimalMasterError::MaxMinorants.into());
        }
        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, Self::SubgradientExtensionErr>,
    ) -> Result<(), E> {
        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(MasterProblemError::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<(), E> {
        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);

        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), E> {
        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);

 *
 * \\[ \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 returned by the subgradient-extension callback.
    type SubgradientExtensionErr;

    /// Return a new instance of the unconstrained master problem.
    fn new() -> Result<Self, Self::SubgradientExtensionErr>
    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::SubgradientExtensionErr>;

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

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

    /// 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, Self::SubgradientExtensionErr>,
    ) -> Result<(), Self::SubgradientExtensionErr>;

    /// Solve the master problem.
    fn solve(
        &mut self,
        eta: &DVector,
        fbound: Real,
        augbound: Real,
        relprec: Real,
    ) -> Result<(), Self::SubgradientExtensionErr>;

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

    /// Move the center of the master problem along $\alpha \cdot d$.
    fn move_center(&mut self, alpha: Real, d: &DVector);
}

#[derive(Debug)]
pub enum SolverError<E> {
    /// 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(MasterProblemError<E>),
    /// 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.

                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: Error> Error for SolverError<E>
where
    E: 'static,
{
    fn cause(&self) -> Option<&Error> {
        match self {
            SolverError::Evaluation(err) => Some(err),
            SolverError::Update(err) => Some(err),
            SolverError::Master(err) => Some(err),
            _ => None,
        }
    }
}

impl<E> From<ParameterError> for SolverError<E> {
    fn from(err: ParameterError) -> SolverError<E> {
        SolverError::Parameter(err)
    }
}

impl<E> From<MasterProblemError<E>> for SolverError<E> {
    fn from(err: MasterProblemError<E>) -> SolverError<E> {
        SolverError::Master(err)
    }
}

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

     * Time when the solution process started.
     *
     * This is actually the time of the last call to `Solver::init`.
     */
    start_time: Instant,

    /// The master problem.
    master: Box<MasterProblem<MinorantIndex = usize, SubgradientExtensionErr = P::Err>>,

    /// The active minorant indices for each subproblem.
    minorants: Vec<Vec<MinorantInfo<P::Primal>>>,

    /// Accumulated information about the last iteration.
    iterinfos: Vec<IterationInfo>,
}

impl<P: FirstOrderProblem> Solver<P>
where
    P::Err: Into<Box<dyn 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

            let minorants = &self.minorants;
            self.master.add_vars(
                &newvars.iter().map(|v| (v.0, v.1, v.2)).collect::<Vec<_>>(),
                &mut |fidx, minidx, vars| {
                    problem
                        .extend_subgradient(minorants[fidx][minidx].primal.as_ref().unwrap(), vars)
                        .map(DVector)

                },
            )?;
            // modify moved variables
            for (index, val) in newvars.iter().filter_map(|v| v.0.map(|i| (i, v.3))) {
                self.cur_y[index] = val;
                self.nxt_y[index] = val;
                self.nxt_d[index] = 0.0;