RsBundle  Check-in [25714ffdea]

 * The subgradients (linear minorants) can be obtained by iterating over the result. The
 * subgradients are centered around the point of evaluation.
 */
pub trait Evaluation<P>: IntoIterator<Item = (Minorant, P)> {
    /// Return the function value at the point of evaluation.
    fn objective(&self) -> Real;
}


/**
 * Simple standard evaluation result.
 *
 * This result consists of the function value and a list of one or
 * more minorants and associated primal information.
 */

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


//! Weight updating rule according to Helmberg and Kiwiel.
//!
//! The procedure is described in
//!
//! > Helmberg, C. and Kiwiel, K.C. (2002): A spectral bundle method
//! > with bounds, Math. Programming A 93, 173--194
//!

                self.iter = -1
            } else {
                self.iter = min(self.iter - 1, -1);
            }

            debug!(
                "  sgnorm={} cur_val={} new_cutval={} lin_err={} eps_weight={}",
                sgnorm,
                state.cur_val,
                state.new_cutval,
                lin_err,
                self.eps_weight
            );
            debug!("  new_weight={}", new_weight);

            new_weight
        } else {
            self.model_max = self.model_max.max(state.nxt_mod);
            let new_weight = if self.iter > 0 && cur_nxt > self.m_r * cur_mod {

    /// 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 FnMut(usize, Self::MinorantIndex, &[usize]) -> DVector,
    ) -> Result<(), Error>;


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

    /// Current number of updates.
    cnt_updates: usize,

    /// The unconstrained master problem solver.
    master: M,
}


impl<M: UnconstrainedMasterProblem> BoxedMasterProblem<M> {
    pub fn new(master: M) -> BoxedMasterProblem<M> {
        BoxedMasterProblem {
            lb: dvec![],
            ub: dvec![],
            eta: dvec![],
            primopt: dvec![],

            .iter()
            .zip(self.eta.iter())
            .map(|(x, y)| x * y)
            .sum()
    }
}


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

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

            debug!(
                "  cut-lin={} < eps*(cur-lin)={}",
                cutval - linval,
                self.model_eps * (curval - linval)
            );
            debug!(
                "  cnt_update={} max_updates={}",
                cnt_updates,
                self.max_updates
            );

            self.primoptval = linval;

            if augval < old_augval + 1e-10 || cutval - linval < self.model_eps * (curval - linval)
                || cnt_updates >= self.max_updates
            {

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


impl UnconstrainedMasterProblem for CplexMaster {
    type MinorantIndex = usize;

    fn new() -> Result<CplexMaster, Error> {
        Ok(CplexMaster {
            lp: ptr::null_mut(),
            force_update: true,

        for mins in &mut self.minorants {
            for m in mins.iter_mut() {
                m.move_center(alpha, d);
            }
        }
    }
}


impl CplexMaster {
    fn init_qp(&mut self) -> Result<(), Error> {
        if !self.lp.is_null() {
            trycpx!(cpx::freeprob(cpx::env(), &mut self.lp));
        }
        trycpx!({

use master::UnconstrainedMasterProblem;

use std::f64::NEG_INFINITY;
use std::result::Result;

use failure::Error;


/// Minimal master problem error.
#[derive(Debug, Fail)]
pub enum MinimalMasterError {
    #[fail(display = "Solver Error: too many subproblems (got: {} must be <= 2)", nsubs)]
    NumSubproblems {
        nsubs: usize,
    },

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


impl UnconstrainedMasterProblem for MinimalMaster {
    type MinorantIndex = usize;

    fn new() -> Result<MinimalMaster, Error> {
        Ok(MinimalMaster {
            weight: 1.0,

        }
        let fnod = buffer
            .split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>();

        if fnod.len() != 4 {
            return Err(
                MCFFormatError {
                    msg: format!(
                        "Expected 4 numbers in {}.nod, but got {}",
                        basename,
                        fnod.len()
                    ),
                }.into(),
            );
        }

        let ncom = fnod[0];
        let nnodes = fnod[1];
        let narcs = fnod[2];
        let ncaps = fnod[3];

            let coeff = arcmap[com].len();
            arcmap[com].push(ArcInfo {
                arc: arc + 1,
                src: src + 1,
                snk: snk + 1,
            });
            // add arc
            try!(nets[com].add_arc(
                src,
                snk,
                cost,
                if cap < 0.0 { INFINITY } else { cap }
            ));
            // set objective
            cbase[com].push(cost); // + 1e-6 * coeff
                                   // add to mutual capacity constraint
            if mt >= 0 {
                lhsidx[mt as usize][com].push(coeff);
            }
        }

use failure::{err_msg, Error};

pub struct Solver {
    net: *mut cpx::Net,
    logfile: *mut cpx::File,
}


impl Drop for Solver {
    fn drop(&mut self) {
        unsafe {
            cpx::NETfreeprob(cpx::env(), &mut self.net);
            cpx::fclose(self.logfile);
        }
    }

            if status != 0 {
                let msg = CString::new(vec![0; cpx::MESSAGE_BUF_SIZE])
                    .unwrap()
                    .into_raw();
                cpx::geterrorstring(cpx::env(), status, msg);
                cpx::NETfreeprob(cpx::env(), &mut net);
                cpx::fclose(logfile);
                return Err(
                    cpx::CplexError {
                        code: status,
                        msg: CString::from_raw(msg).to_string_lossy().into_owned(),
                    }.into(),
                );
            }
        }

        Ok(Solver {
            net: net,
            logfile: logfile,
        })

pub struct Minorant {
    /// The constant term.
    pub constant: Real,

    /// The linear term.
    pub linear: DVector,
}



impl fmt::Display for Minorant {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        try!(write!(f, "{} + y * {}", self.constant, self.linear));
        Ok(())
    }
}

 * whether the solution process should be stopped.
 */
pub trait Terminator {
    /// Return true if the method should stop.
    fn terminate(&mut self, state: &BundleState, params: &SolverParams) -> bool;
}


/**
 * Terminates if expected progress is small enough.
 */
pub struct StandardTerminator {
    pub termination_precision: Real,
}

            Err(SolverError::Parameter(format!(
                "acceptance_factor must be in (0,1) (got: {})",
                self.acceptance_factor
            )))
        } else if self.nullstep_factor <= 0.0 || self.nullstep_factor > self.acceptance_factor {
            Err(SolverError::Parameter(format!(
                "nullstep_factor must be in (0,acceptance_factor] (got: {}, acceptance_factor:{})",
                self.nullstep_factor,
                self.acceptance_factor
            )))
        } else if self.min_weight <= 0.0 {
            Err(SolverError::Parameter(format!(
                "min_weight must be in > 0 (got: {})",
                self.min_weight
            )))
        } else if self.max_weight < self.min_weight {
            Err(SolverError::Parameter(format!(
                "max_weight must be in >= min_weight (got: {}, min_weight: {})",
                self.max_weight,
                self.min_weight
            )))
        } else if self.max_updates == 0 {
            Err(SolverError::Parameter(format!(
                "max_updates must be in > 0 (got: {})",
                self.max_updates
            )))
        } else {

            max_weight: 1000.0,

            max_updates: 50,
        }
    }
}


/// The step type that has been performed.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Step {
    /// A null step has been performed.
    Null,
    /// A descent step has been performed.
    Descent,
    /// No step but the algorithm has been terminated.
    Term,
}


/// Information about a minorant.
#[derive(Debug, Clone)]
struct MinorantInfo<Pr> {
    /// The minorant's index in the master problem
    index: usize,
    /// Current multiplier.
    multiplier: Real,
    /// Primal associated with this minorant.
    primal: Option<Pr>,
}

/// Information about the last iteration.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum IterationInfo {
    NewMinorantTooHigh { new: Real, old: Real },
    UpperBoundNullStep,
    ShallowCut,
}


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

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

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


impl<P, Pr, E> Solver<P, Pr, E>
where
    P: for<'a> FirstOrderProblem<'a, Primal = Pr, EvalResult = E>,
    E: Evaluation<Pr>,
{
    /**
     * Create a new solver for the given problem.

            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: Box::new(BoxedMasterProblem::new(
                MinimalMaster::new().map_err(SolverError::Master)?,
            )),
            minorants: vec![],
            iterinfos: vec![],
        })
    }

    /// A new solver with default parameter.
    pub fn new(problem: P) -> Result<Solver<P, Pr, E>, SolverError> {

     * information.
     */
    fn init_master(&mut self) -> Result<(), SolverError> {
        let m = self.problem.num_subproblems();

        self.master = if m == 1 && self.params.max_bundle_size == 2 {
            debug!("Use minimal master problem");
            Box::new(BoxedMasterProblem::new(
                MinimalMaster::new().map_err(SolverError::Master)?,
            ))
        } else {
            debug!("Use CPLEX master problem");
            Box::new(BoxedMasterProblem::new(
                CplexMaster::new().map_err(SolverError::Master)?,
            ))
        };

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

        if lb.as_ref()
            .map(|lb| lb.len() != self.problem.num_variables())

            .map_err(SolverError::Master)?;

        debug!("Init master completed");

        Ok(())
    }


    /// Solve the model (i.e. master problem) to compute the next candidate.
    fn solve_model(&mut self) -> Result<(), SolverError> {
        self.master
            .solve(self.cur_val)
            .map_err(SolverError::Master)?;
        self.nxt_d = self.master.get_primopt();
        self.nxt_y.add(&self.cur_y, &self.nxt_d);

        debug!("Model result");
        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> {
        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

                primal: Some(nxt_primal),
            });
        }

        if self.new_cutval > self.cur_val + 1e-3 {
            warn!(
                "New minorant has higher value in center new:{} old:{}",
                self.new_cutval,
                self.cur_val
            );
            self.cur_val = self.new_cutval;
            self.iterinfos.push(IterationInfo::NewMinorantTooHigh {
                new: self.new_cutval,
                old: self.cur_val,
            });
        }

     * This value is $f(\hat{y}) + \varrho' \cdot \Delta$ where
     * $\Delta = f(\hat{y}) - \hat{f}(\bar{y})$ is the expected
     * progress and $\varrho'$ is the `nullstep_factor`.
     */
    fn get_nullstep_bound(&self) -> Real {
        self.cur_val - self.params.nullstep_factor * (self.cur_val - self.nxt_mod)
    }


    /**
     * Return the bound the function value must be below of to enforce a descent step.
     *
     * If the oracle guarantees that $f(\bar{y}) \le$ this bound, the
     * bundle method will perform a descent step.
     *

     */
    Sparse {
        size: usize,
        elems: Vec<(usize, Real)>,
    },
}


impl fmt::Display for Vector {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Vector::Dense(ref v) => write!(f, "{}", v),
            Vector::Sparse { size, ref elems } => {
                let mut it = elems.iter();
                try!(write!(f, "{}:(", size));
                if let Some(&(i, x)) = it.next() {
                    try!(write!(f, "{}:{}", i, x));
                    for &(i, x) in it {
                        try!(write!(f, ", {}:{}", i, x));
                    }
                }
                write!(f, ")")
            }
        }
    }
}


impl DVector {
    /// Set all elements to 0.
    pub fn init0(&mut self, size: usize) {
        self.clear();
        self.extend((0..size).map(|_| 0.0));
        // let n = self.len();

        //     self.resize(y.len(), 0.0);
        // }
        // for i in 0..y.len() {
        //     unsafe { *self.get_unchecked_mut(i) += alpha * *y.get_unchecked(i) };
        // }
    }


    /// Combines this vector with another vector.
    pub fn combine(&self, self_factor: Real, other_factor: Real, other: &DVector) -> DVector {
        assert_eq!(self.len(), other.len());
        let mut result = vec![];
        result.extend(
            self.iter()
                .zip(other.iter())
                .map(|(a, b)| self_factor * a + other_factor * b),
        );
        DVector(result)
        // let mut result = DVector(Vec::with_capacity(self.len()));
        // for i in 0..self.len() {
        //     result.push(unsafe {
        //         self_factor * *self.get_unchecked(i) +
        //             other_factor * *other.get_unchecked(i)
        //     });
        // }
        // result
    }


    /// Return the 2-norm of this vector.
    pub fn norm2(&self) -> Real {
        self.iter().map(|x| x * x).sum::<Real>().sqrt()
        // let mut norm = 0.0;
        // for x in self.iter() {
        //     norm += x * x
        // }
        // norm.sqrt()
    }
}


impl Vector {
    /**
     * Return a sparse vector with the given non-zeros.
     */
    pub fn new_sparse(n: usize, indices: &[usize], values: &[Real]) -> Vector {
        assert_eq!(indices.len(), values.len());