RsBundle  Check-in [814bd7230a]

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

//! Problem description of a first-order convex optimization problem.

use {Real, Vector, DVector, Minorant};
use solver::UpdateState;

use std::error;
use std::vec::IntoIter;

/**
 * Trait for results of an evaluation.
 *

}

impl<P> Evaluation<P> for SimpleEvaluation<P> {
    fn objective(&self) -> Real {
        self.objective
    }
}

/// Problem update information.
///
/// The solver calls the `update` method of the problem regularly.
/// This method can modify the problem by adding (or removing)
/// variables. The possible updates are encoded in this type.
#[derive(Debug, Clone, Copy)]
pub enum Update {
    AddVariable{lower: Real, upper: Real},
}

/**
 * Trait for implementing a first-order problem description.
 *
 */
pub trait FirstOrderProblem<'a> {
    /// Custom error type for evaluating this oracle.

    /// last primal. This should work if the implementing problem does
    /// not provide primal information, e.g. if `Self::Primal = ()`.
    #[allow(unused_variables)]
    fn aggregate_primals(&mut self, coeffs: &[Real], primals: Vec<Self::Primal>) -> Self::Primal {
        let mut primals = primals;
        primals.pop().unwrap()
    }

    /// Return updates of the problem.
    ///
    /// The default implementation returns no updates.
    fn update(&mut self, _state: &UpdateState<Self::Primal>) -> Result<Vec<Update>, Self::Error> {
        Ok(vec![])
    }

    /// Return new components for a subgradient.
    ///
    /// The components are typically generated by some primal
    /// information. The corresponding primal is passed as a
    /// parameter.
    ///
    /// The default implementation fails because it should never be
    /// called.
    fn extend_subgradient(&mut self, _primal: &Self::Primal, _vars: &[usize]) -> Result<DVector, Self::Error> {
        unimplemented!()
    }
}

pub mod vector;
pub use vector::{DVector, Vector};

pub mod minorant;
pub use minorant::Minorant;

pub mod firstorderproblem;
pub use firstorderproblem::{Evaluation, SimpleEvaluation, Update, FirstOrderProblem};

pub mod solver;
pub use solver::{Solver, SolverParams, BundleState, Terminator, StandardTerminator, Weighter, Step, UpdateState};

mod hkweighter;
pub use hkweighter::HKWeighter;

mod master;

pub mod mcf;

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

    fn set_weight(&mut self, weight: Real) {
        self.master.set_weight(weight);
    }

    fn add_vars(&mut self, bounds: &[(Real,Real)], extend_subgradient: &mut FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector) {
        self.lb.extend(bounds.iter().map(|x| x.0));
        self.ub.extend(bounds.iter().map(|x| x.1));
        self.master.add_vars(bounds.len(), extend_subgradient)
    }

    fn solve(&mut self, center_value: Real) -> Result<()> {
        debug!("Solve Master");
        debug!("  lb      ={}", self.lb);
        debug!("  ub      ={}", self.ub);

        if self.need_new_candidate {

            let idx = self.index2min.len();
            self.min2index[fidx].push(idx);
            self.index2min.push((fidx, min_idx));
            self.updateinds.push(idx);
            Ok(idx)
        }
    }

    fn add_vars(&mut self, nvars: usize, extend_subgradient: &mut FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector) {
        unimplemented!()
    }

    #[allow(unused_variables)]
    fn solve(&mut self, eta: &DVector, fbound: Real, augbound: Real, relprec: Real) -> Result<()> {
        if self.force_update || !self.updateinds.is_empty() {
            try!(self.init_qp());
        }

    /// Set the maximal number of inner iterations.
    fn set_max_updates(&mut self, max_updates: usize);

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

    /// Add some variables with bounds.
    fn add_vars(&mut self, bounds: &[(Real,Real)], extend_subgradient: &mut FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector);

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

        if self.minorants.len() >= 2 {
            return Err(Error::MaxMinorants)
        }
        self.minorants.push(minorant);
        self.opt_mult.push(0.0);
        Ok(self.minorants.len()-1)
    }

    fn add_vars(&mut self, nvars: usize, extend_subgradient: &mut FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector) {
        if !self.minorants.is_empty() {
            let noldvars = self.minorants[0].linear.len();
            let newvars = (noldvars .. noldvars + nvars).collect::<Vec<_>>();
            for (i,m) in self.minorants.iter_mut().enumerate() {
                let new_subg = extend_subgradient(0, i, &newvars);
                m.linear.extend_from_slice(&new_subg);
            }
        }
    }

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

    /// 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::Result<Self::MinorantIndex, Self::Error>;

    /// Add a number of variables.
    fn add_vars(&mut self, nvars: usize, extend_subgradient: &mut FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector);

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

    /// Return the current dual optimal solution.
    fn dualopt(&self) -> &DVector;

    /// Return the current dual optimal solution value.

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

//! The main bundle method solver.

use {Real, DVector};
use {FirstOrderProblem, Update, Evaluation, HKWeighter};

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

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

quick_error! {
    /// A solver error.
    #[derive(Debug)]
    pub enum Error {
        /// An error occurred during evaluation of the oracle.
        Eval(err: Box<error::Error>) {
            cause(&**err)
            description(err.description())
            display("Evaluation error: {}", err)
        }

        /// An error occurred during update of the oracle.
        Update(err: Box<error::Error>) {
            cause(&**err)
            description(err.description())
            display("Update error: {}", err)
        }

        /// Error solving the master problem.
        Master(err: Box<error::Error>) {
            cause(&**err)
            description(err.description())
            display("Master problem error: {}", err)
            from(err: master::Error) -> (Box::new(err))

    /// The minorant's index in the master problem
    index: usize,
    /// Current multiplier.
    multiplier: Real,
    /// Primal associated with this minorant.
    primal: Option<Pr>,
}

/// State information for the update callback.
pub struct UpdateState<'a, Pr:'a> {
    /// Current model minorants.
    minorants: &'a [Vec<MinorantInfo<Pr>>],
    /// The last step type.
    pub step: Step,
}

impl<'a, Pr:'a> UpdateState<'a, Pr> {
    pub fn aggregated_primals(&self, subproblem : usize) -> Vec<(Real, &Pr)> {
        self.minorants[subproblem].iter().map(|m| {
            (m.multiplier, m.primal.as_ref().unwrap())
        }).collect()
    }
}

/**
 * Implementation of a bundle method.
 */
pub struct Solver<P, Pr, E>
    where P : for <'a> FirstOrderProblem<'a,Primal=Pr,EvalResult=E>,
          E : Evaluation<Pr>,

    }

    /// Solve the problem.
    pub fn solve(&mut self) -> Result<()> {
        try!(self.init());
        for _ in 0..100000 {
            let term = try!(self.step());
            try!(self.update_problem(term));
            self.show_info(term);
            if term == Step::Term {
                break;
            }
        }
        Ok(())
    }

    /// 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<()> {
        let state = UpdateState {minorants: &self.minorants, step: term};
        let updates = match self.problem.update(&state) {
            Ok(updates) => updates,
            Err(err) => return Err(Error::Update(Box::new(err))),
        };

        let mut newvars = Vec::with_capacity(updates.len());
        for u in updates {
            match u {
                Update::AddVariable{lower, upper} => {
                    newvars.push((lower, upper));
                },
            }
        }

        if !newvars.is_empty() {
            let mut problem = &mut self.problem;
            let minorants = &self.minorants;
            self.master.add_vars(&newvars, &mut move |fidx, minidx, vars| {
                problem.extend_subgradient(minorants[fidx][minidx].primal.as_ref().unwrap(), vars).unwrap()
            });
        }

        Ok(())
    }

    /// Return the current aggregated primal information for a subproblem.
    ///
    /// This function returns all currently used minorants $x_i$ along
    /// with their coefficients $\alpha_i$. The aggregated primal can