Index: examples/cflp.rs ================================================================== --- examples/cflp.rs +++ examples/cflp.rs @@ -31,11 +31,11 @@ use ordered_float::NotNan; use threadpool::ThreadPool; use bundle::problem::{FirstOrderProblem as ParallelProblem, ResultSender}; use bundle::solver::sync::{DefaultSolver, NoBundleSolver}; -use bundle::{dvec, DVector, Minorant, Real}; +use bundle::{dvec, DVector, Real}; const Nfac: usize = 3; const Ncus: usize = 5; const F: [Real; Nfac] = [1000.0, 1000.0, 1000.0]; const CAP: [Real; Nfac] = [500.0, 500.0, 500.0]; @@ -43,10 +43,12 @@ [4.0, 5.0, 6.0, 8.0, 10.0], // [6.0, 4.0, 3.0, 5.0, 8.0], // [9.0, 7.0, 4.0, 3.0, 4.0], // ]; const DEMAND: [Real; 5] = [80.0, 270.0, 250.0, 160.0, 180.0]; + +type Minorant = (Real, DVector, DVector); #[derive(Debug)] enum EvalError { Customer(usize), } @@ -69,11 +71,11 @@ fn new() -> CFLProblem { CFLProblem { pool: None } } } -fn solve_facility_problem(j: usize, lambda: &[Real]) -> Result<(Real, Minorant), EvalError> { +fn solve_facility_problem(j: usize, lambda: &[Real]) -> Result<(Real, Minorant), EvalError> { // facility subproblem max\{-F[j] + CAP[j] * lambda[j] * y[j] | y_j \in \{0,1\}\} let objective; let mut subg = dvec![0.0; lambda.len()]; let primal; if -F[j] + CAP[j] * lambda[j] > 0.0 { @@ -83,21 +85,14 @@ } else { objective = 0.0; primal = dvec![0.0; 1]; } - Ok(( - objective, - Minorant { - constant: objective, - linear: subg, - primal, - }, - )) + Ok((objective, (objective, subg, primal))) } -fn solve_customer_problem(i: usize, lambda: &[Real]) -> Result<(Real, Minorant), EvalError> { +fn solve_customer_problem(i: usize, lambda: &[Real]) -> Result<(Real, Minorant), EvalError> { // customer subproblem let opt = (0..Nfac) .map(|j| (j, -DEMAND[i] * C[j][i] - DEMAND[i] * lambda[j])) .flat_map(|x| NotNan::new(x.1).map(|y| (x.0, y))) .max_by_key(|x| x.1) @@ -107,24 +102,17 @@ let mut subg = dvec![0.0; lambda.len()]; subg[opt.0] = -DEMAND[i]; let mut primal = dvec![0.0; Nfac]; primal[opt.0] = 1.0; - Ok(( - objective, - Minorant { - constant: objective, - linear: subg, - primal, - }, - )) + Ok((objective, (objective, subg, primal))) } impl ParallelProblem for CFLProblem { type Err = EvalError; - type Primal = DVector; + type Minorant = Minorant; fn num_variables(&self) -> usize { Nfac } Index: examples/mmcf.rs ================================================================== --- examples/mmcf.rs +++ examples/mmcf.rs @@ -23,20 +23,22 @@ use bundle::master::{Builder, FullMasterBuilder, MasterProblem, MinimalMasterBuilder}; use bundle::mcf::MMCFProblem; use bundle::solver::asyn::Solver as AsyncSolver; use bundle::solver::sync::Solver as SyncSolver; -use bundle::DVector; use bundle::{terminator::StandardTerminator, weighter::HKWeighter}; +use bundle::{DVector, Real}; use std::error::Error; use std::result::Result; + +type Minorant = (Real, DVector, DVector); fn solve_parallel(master: M, mmcf: MMCFProblem) -> Result<(), Box> where - M: Builder, - M::MasterProblem: MasterProblem, + M: Builder, + M::MasterProblem: MasterProblem, { let mut slv = AsyncSolver::<_, StandardTerminator, HKWeighter, M>::with_master(mmcf, master); slv.weighter.set_weight_bounds(1e-1, 100.0); slv.terminator.termination_precision = 1e-6; slv.solve()?; @@ -51,12 +53,12 @@ Ok(()) } fn solve_sync(master: M, mmcf: MMCFProblem) -> Result<(), Box> where - M: Builder, - M::MasterProblem: MasterProblem, + M: Builder, + M::MasterProblem: MasterProblem, { let mut slv = SyncSolver::<_, StandardTerminator, HKWeighter, M>::with_master(mmcf, master); slv.weighter.set_weight_bounds(1e-1, 100.0); slv.terminator.termination_precision = 1e-6; slv.solve()?; Index: examples/quadratic.rs ================================================================== --- examples/quadratic.rs +++ examples/quadratic.rs @@ -26,11 +26,11 @@ use std::sync::Arc; use std::thread; use bundle::problem::{FirstOrderProblem as ParallelProblem, ResultSender}; use bundle::solver::sync::{DefaultSolver, NoBundleSolver}; -use bundle::{DVector, Minorant, Real}; +use bundle::{DVector, Real}; #[derive(Clone)] struct QuadraticProblem { a: [[Real; 2]; 2], b: [Real; 2], @@ -47,11 +47,12 @@ } } impl ParallelProblem for QuadraticProblem { type Err = Box; - type Primal = (); + + type Minorant = (Real, DVector); fn num_variables(&self) -> usize { 2 } @@ -83,16 +84,11 @@ debug!("Evaluation at {:?}", x); debug!(" objective={}", objective); debug!(" subgradient={}", g); tx.objective(objective).unwrap(); - tx.minorant(Minorant { - constant: objective, - linear: g, - primal: (), - }) - .unwrap(); + tx.minorant((objective, g)).unwrap(); }); Ok(()) } } Index: src/data/aggregatable.rs ================================================================== --- src/data/aggregatable.rs +++ src/data/aggregatable.rs @@ -19,30 +19,30 @@ use super::Real; use std::borrow::Borrow; /// An aggregatable object. -pub trait Aggregatable: Default { +pub trait Aggregatable: Default { /// Return a scaled version of `other`, i.e. `alpha * other`. fn new_scaled(alpha: Real, other: A) -> Self where - A: Borrow; + A: Borrow; /// Add a scaled version of `other` to `self`. /// /// This sets `self = self + alpha * other`. fn add_scaled(&mut self, alpha: Real, other: A) where - A: Borrow; + A: Borrow; /// Return $\sum\_{i=1}\^n alpha_i m_i$. /// /// If `aggregates` is empty return the default value. fn combine(aggregates: I) -> Self where I: IntoIterator, - A: Borrow, + A: Borrow, { let mut it = aggregates.into_iter(); let mut x; if let Some((alpha, y)) = it.next() { x = Self::new_scaled(alpha, y); @@ -70,10 +70,64 @@ where A: Borrow, { } } + +/// Implement for pairs. +impl Aggregatable for (T1, T2) +where + T1: Aggregatable, + T2: Aggregatable, +{ + fn new_scaled(alpha: Real, other: A) -> Self + where + A: Borrow, + { + let x = other.borrow(); + (T1::new_scaled(alpha, &x.0), T2::new_scaled(alpha, &x.1)) + } + + fn add_scaled(&mut self, alpha: Real, other: A) + where + A: Borrow, + { + let x = other.borrow(); + self.0.add_scaled(alpha, &x.0); + self.1.add_scaled(alpha, &x.1); + } +} + +/// Implement for triples. +impl Aggregatable for (T1, T2, T3) +where + T1: Aggregatable, + T2: Aggregatable, + T3: Aggregatable, +{ + fn new_scaled(alpha: Real, other: A) -> Self + where + A: Borrow, + { + let x = other.borrow(); + ( + T1::new_scaled(alpha, &x.0), + T2::new_scaled(alpha, &x.1), + T3::new_scaled(alpha, &x.2), + ) + } + + fn add_scaled(&mut self, alpha: Real, other: A) + where + A: Borrow, + { + let x = other.borrow(); + self.0.add_scaled(alpha, &x.0); + self.1.add_scaled(alpha, &x.1); + self.2.add_scaled(alpha, &x.2); + } +} /// Implement for scalar values. impl Aggregatable for Real { fn new_scaled(alpha: Real, other: A) -> Self where Index: src/data/minorant.rs ================================================================== --- src/data/minorant.rs +++ src/data/minorant.rs @@ -15,13 +15,14 @@ // //! A linear minorant. use super::{Aggregatable, DVector, Real}; - +use num_traits::Zero; use std::borrow::Borrow; -use std::fmt; + +use crate::data::raw::BLAS1; /// A linear minorant of a convex function. /// /// A linear minorant of a convex function $f \colon \mathbb{R}\^n \to /// \mathbb{R}$ is a linear function of the form @@ -32,109 +33,170 @@ /// such that $l(x) \le f(x)$ for all $x \in \mathbb{R}\^n$. /// /// Each minorant may have an additional "primal" data, that is /// linearly combined along with the minorant itself. This data can /// be used for separation algorithms. -#[derive(Clone)] -pub struct Minorant { - /// The constant term. - pub constant: Real, - - /// The linear term. - pub linear: DVector, - - /// The associated primal data. - pub primal: P, -} - -impl fmt::Debug for Minorant

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

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

{ - fn default() -> Minorant

{ - Minorant { - constant: 0.0, - linear: dvec![], - primal: P::default(), - } - } -} - -impl Minorant

{ - /// Return a new 0 minorant. - pub fn new(constant: Real, linear: Vec, primal: P) -> Minorant

{ - Minorant { - constant, - linear: DVector(linear), - primal, - } - } - - /** - * Evaluate minorant at some point. - * - * This function computes $c + \langle g, x \rangle$ for this minorant - * \\[\ell \colon \mathbb{R}\^n \to \mathbb{R}, x \mapsto c + \langle g, x \rangle\\] - * and the given point $x \in \mathbb{R}\^n$. - */ - pub fn eval(&self, x: &DVector) -> Real { - self.constant + self.linear.dot(x) - } - - /** - * Move the center of the minorant. - */ - pub fn move_center(&mut self, alpha: Real, d: &DVector) { - self.constant += alpha * self.linear.dot(d); +pub trait Minorant: Aggregatable + Default + Send + 'static { + type Primal: Aggregatable + Send; + + /// Return the constant value. + fn constant(&self) -> Real; + + /// Return the dimension of the linear term. + fn dim(&self) -> usize; + + /// Evaluate the linear term at some point. + fn linear(&self, x: &DVector) -> Real; + + /// Return the associated primal data. + fn primal(&self) -> &Self::Primal; + + /// Compute the inner product with another minorant. + fn product(&self, other: &Self) -> Real; + + /// Add a scaled `self.linear` to `target`. + /// + /// This sets `target = target + alpha * self.linear`. + fn add_scaled_to(&self, alpha: Real, target: &mut [Real]); + + /// Compute linear combination of (linear terms of) the given minorants and + /// store in a dense vector. + fn combine_to_vec(minorants: I, target: &mut (Real, DVector)) + where + I: IntoIterator, + A: Borrow, + { + target.0 = Real::zero(); + let mut it = minorants.into_iter(); + if let Some((alpha, m)) = it.next() { + let m = m.borrow(); + target.1.init0(m.dim()); + m.add_scaled_to(alpha, &mut target.1); + target.0 += alpha * m.constant(); + for (alpha, m) in it { + let m = m.borrow(); + m.add_scaled_to(alpha, &mut target.1); + target.0 += alpha * m.constant(); + } + } else { + target.1.clear(); + } + } + + /// Evaluate minorant at some point. + /// + /// This function computes $c + \langle g, x \rangle$ for this minorant + /// \\[\ell \colon \mathbb{R}\^n \to \mathbb{R}, x \mapsto c + \langle g, x \rangle\\] + /// and the given point $x \in \mathbb{R}\^n$. + /// + fn eval(&self, x: &DVector) -> Real { + self.constant() + self.linear(x) + } + + /// Move the center of the minorant along direction `d`. + fn move_center(&mut self, alpha: Real, d: &DVector) { + debug_assert_eq!(d.len(), self.dim(), "Minorant and direction must have same dimension"); + self.move_center_begin(alpha, d) } /// Move the center of the minorant. /// /// In contrast to [`move_center`] the vector `d` might be shorter than the /// linear term of the minorant. The missing elements are assumed to be /// zero. /// /// [`move_center`]: Minorant::move_center - pub fn move_center_begin(&mut self, alpha: Real, d: &DVector) { - debug_assert!(self.linear.len() >= d.len()); - self.constant += alpha * self.linear.dot_begin(d); - } -} - -impl Aggregatable for Minorant

{ - fn new_scaled(alpha: Real, other: A) -> Self - where - A: Borrow, - { - let m = other.borrow(); - Minorant { - constant: alpha * m.constant, - linear: DVector::scaled(&m.linear, alpha), - primal: P::new_scaled(alpha, &m.primal), - } - } - - fn add_scaled(&mut self, alpha: Real, other: A) - where - A: Borrow, - { - let m = other.borrow(); - self.constant += alpha * m.constant; - self.linear.add_scaled(alpha, &m.linear); - self.primal.add_scaled(alpha, &m.primal); - } -} - -/// The subgradient extender is a callback used to update existing minorants -/// given their associated primal data. -pub type SubgradientExtender = dyn FnMut(usize, &P, &[usize]) -> Result + Send; + fn move_center_begin(&mut self, alpha: Real, d: &DVector); + + fn debug(&self) -> &dyn std::fmt::Debug; +} + +impl Minorant for (Real, DVector, P) { + type Primal = P; + + fn dim(&self) -> usize { + self.1.len() + } + + fn constant(&self) -> Real { + self.0 + } + + fn linear(&self, x: &DVector) -> Real { + self.1.dot(x) + } + + fn primal(&self) -> &P { + &self.2 + } + + fn product(&self, other: &Self) -> Real { + self.1.dot(&other.1) + } + + fn add_scaled_to(&self, alpha: Real, target: &mut [Real]) { + debug_assert_eq!(self.1.len(), target.len()); + if !alpha.is_zero() { + BLAS1::add_scaled(target, alpha, &self.1); + } + } + + fn move_center(&mut self, alpha: Real, d: &DVector) { + self.0 += alpha * self.1.dot(d); + } + + fn move_center_begin(&mut self, alpha: Real, d: &DVector) { + debug_assert!(self.1.len() >= d.len()); + self.0 += alpha * self.1.dot_begin(d); + } + + fn debug(&self) -> &dyn std::fmt::Debug { + &self.1 + } +} + +impl Minorant for (Real, DVector) { + type Primal = (); + + fn dim(&self) -> usize { + self.1.len() + } + + fn constant(&self) -> Real { + self.0 + } + + fn linear(&self, x: &DVector) -> Real { + self.1.dot(x) + } + + fn primal(&self) -> &Self::Primal { + &() + } + + fn product(&self, other: &Self) -> Real { + self.1.dot(&other.1) + } + + fn add_scaled_to(&self, alpha: Real, target: &mut [Real]) { + debug_assert_eq!(self.1.len(), target.len()); + if !alpha.is_zero() { + BLAS1::add_scaled(target, alpha, &self.1); + } + } + + fn move_center(&mut self, alpha: Real, d: &DVector) { + self.0 += alpha * self.1.dot(d); + } + + fn move_center_begin(&mut self, alpha: Real, d: &DVector) { + debug_assert!(self.1.len() >= d.len()); + self.0 += alpha * self.1.dot_begin(d); + } + + fn debug(&self) -> &dyn std::fmt::Debug { + self + } +} + +/// The subgradient extender is a callback used to update an existing minorant. +pub type SubgradientExtender = dyn FnMut(usize, &mut M) -> Result<(), E> + Send; Index: src/data/mod.rs ================================================================== --- src/data/mod.rs +++ src/data/mod.rs @@ -1,7 +1,7 @@ /* - * Copyright (c) 2019 Frank Fischer + * Copyright (c) 2019, 2020 Frank Fischer * * 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. @@ -14,10 +14,12 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see */ //! General types and data structures. + +pub(crate) mod raw; pub mod vector; pub use vector::{DVector, Vector}; pub mod aggregatable; ADDED src/data/raw.rs Index: src/data/raw.rs ================================================================== --- /dev/null +++ src/data/raw.rs @@ -0,0 +1,81 @@ +/* + * Copyright (c) 2020 Frank Fischer + * + * 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 + */ + +///! BLAS-like low-level vector routines. + +#[cfg(feature = "blas")] +use {openblas_src as _, rs_blas as blas, std::os::raw::c_int}; + +pub trait BLAS1 { + /// Compute the inner product. + fn dot(&self, y: &[T]) -> T; + + /// Compute the inner product. + /// + /// The inner product is computed on the smaller of the two + /// dimensions. All other elements are assumed to be zero. + fn dot_begin(&self, y: &[T]) -> T; + + /// Compute `self = self + alpha * y`. + fn add_scaled(&mut self, alpha: T, y: &[T]); + + /// Return the 2-norm of this vector. + fn norm2(&self) -> T; +} + +impl BLAS1 for [f64] { + fn dot(&self, other: &[f64]) -> f64 { + debug_assert_eq!(self.len(), other.len(), "Vectors must have the same size"); + Self::dot_begin(self, other) + } + + fn dot_begin(&self, other: &[f64]) -> f64 { + #[cfg(feature = "blas")] + unsafe { + blas::ddot(self.len().min(other.len()) as c_int, &self, 1, &other, 1) + } + #[cfg(not(feature = "blas"))] + { + self.iter().zip(other.iter()).map(|(x, y)| x * y).sum::() + } + } + + fn add_scaled(&mut self, alpha: f64, y: &[f64]) { + assert_eq!(self.len(), y.len()); + #[cfg(feature = "blas")] + unsafe { + blas::daxpy(self.len() as c_int, alpha, &y, 1, &mut self[..], 1) + } + #[cfg(not(feature = "blas"))] + { + for (x, y) in self.iter_mut().zip(y.iter()) { + *x += alpha * y; + } + } + } + + fn norm2(&self) -> f64 { + #[cfg(feature = "blas")] + unsafe { + blas::dnrm2(self.len() as c_int, &self, 1) + } + #[cfg(not(feature = "blas"))] + { + self.iter().map(|x| x * x).sum::().sqrt() + } + } +} Index: src/data/vector.rs ================================================================== --- src/data/vector.rs +++ src/data/vector.rs @@ -1,6 +1,6 @@ -// Copyright (c) 2016, 2017, 2018, 2019 Frank Fischer +// Copyright (c) 2016-2020 Frank Fischer // // 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. @@ -22,12 +22,11 @@ use std::fmt; use std::iter::FromIterator; use std::ops::{Deref, DerefMut}; use std::vec::IntoIter; -#[cfg(feature = "blas")] -use {openblas_src as _, rs_blas as blas, std::os::raw::c_int}; +use super::raw::BLAS1; /// Type of dense vectors. #[derive(Debug, Clone, PartialEq, Default)] pub struct DVector(pub Vec); @@ -137,18 +136,11 @@ /// Return the inner product with another vector. /// /// The inner product is computed on the smaller of the two /// dimensions. All other elements are assumed to be zero. pub fn dot_begin(&self, other: &DVector) -> Real { - #[cfg(feature = "blas")] - unsafe { - blas::ddot(self.len().min(other.len()) as c_int, &self, 1, &other, 1) - } - #[cfg(not(feature = "blas"))] - { - self.iter().zip(other.iter()).map(|(x, y)| x * y).sum::() - } + BLAS1::dot_begin(&self[..], other) } /// Add two vectors and store result in this vector. pub fn add(&mut self, x: &DVector, y: &DVector) { assert_eq!(x.len(), y.len()); @@ -156,57 +148,32 @@ self.extend(x.iter().zip(y.iter()).map(|(a, b)| a + b)); } /// Add two vectors and store result in this vector. pub fn add_scaled(&mut self, alpha: Real, y: &DVector) { - assert_eq!(self.len(), y.len()); - #[cfg(feature = "blas")] - unsafe { - blas::daxpy(self.len() as c_int, alpha, &y, 1, &mut self[..], 1) - } - #[cfg(not(feature = "blas"))] - { - for (x, y) in self.iter_mut().zip(y.iter()) { - *x += alpha * y; - } - } + BLAS1::add_scaled(&mut self[..], alpha, y); } /// Add two vectors and store result in this vector. /// /// In contrast to `add_scaled`, the two vectors might have /// different sizes. The size of the resulting vector is the /// larger of the two vector sizes and the remaining entries of /// the smaller vector are assumed to be 0.0. pub fn add_scaled_begin(&mut self, alpha: Real, y: &DVector) { - #[cfg(feature = "blas")] - unsafe { - let n = self.len(); - blas::daxpy(n.min(y.len()) as c_int, alpha, &y, 1, &mut self[..], 1); - } - #[cfg(not(feature = "blas"))] - { - for (x, y) in self.iter_mut().zip(y.iter()) { - *x += alpha * y; - } - } - let n = self.len(); - if n < y.len() { + let n = self.len().min(y.len()); + + BLAS1::add_scaled(&mut self[..n], alpha, &y[..n]); + + if self.len() < y.len() { self.extend(y[n..].iter().map(|y| alpha * y)); } } /// Return the 2-norm of this vector. pub fn norm2(&self) -> Real { - #[cfg(feature = "blas")] - unsafe { - blas::dnrm2(self.len() as c_int, &self, 1) - } - #[cfg(not(feature = "blas"))] - { - self.iter().map(|x| x * x).sum::().sqrt() - } + BLAS1::norm2(&self[..]) } } impl Aggregatable for DVector { fn new_scaled(alpha: Real, other: A) -> Self Index: src/master/boxed.rs ================================================================== --- src/master/boxed.rs +++ src/master/boxed.rs @@ -17,11 +17,11 @@ pub mod unconstrained; use self::unconstrained::UnconstrainedMasterProblem; use super::MasterProblem; use crate::problem::SubgradientExtender; -use crate::{Aggregatable, DVector, Minorant, Real}; +use crate::{DVector, Minorant, Real}; use either::Either; use log::debug; use std::f64::{EPSILON, INFINITY, NEG_INFINITY}; use std::marker::PhantomData; @@ -31,13 +31,13 @@ * * This master problem adds box constraints to an unconstrained * master problem implementation. The box constraints are enforced by * an additional outer optimization loop. */ -pub struct BoxedMasterProblem +pub struct BoxedMasterProblem where - P: Aggregatable, + Mn: Minorant, { /// The unconstrained master problem solver. pub master: M, /// Maximal number of updates of box multipliers. @@ -67,19 +67,19 @@ need_new_candidate: bool, /// Current number of updates. cnt_updates: usize, - phantom: PhantomData

, + phantom: PhantomData, } -impl BoxedMasterProblem +impl BoxedMasterProblem where - P: Aggregatable, - M: UnconstrainedMasterProblem

, + Mn: Minorant, + M: UnconstrainedMasterProblem, { - pub fn with_master(master: M) -> BoxedMasterProblem { + pub fn with_master(master: M) -> BoxedMasterProblem { BoxedMasterProblem { master, max_updates: 50, lb: dvec![], ub: dvec![], @@ -189,14 +189,14 @@ fn get_norm_subg2(&self) -> Real { self.eta.dot(self.master.dualopt()) } } -impl MasterProblem

for BoxedMasterProblem +impl MasterProblem for BoxedMasterProblem where - P: Aggregatable + Send + 'static, - M: UnconstrainedMasterProblem

, + Mn: Minorant, + M: UnconstrainedMasterProblem, { type MinorantIndex = M::MinorantIndex; type Err = M::Err; @@ -230,11 +230,11 @@ fn num_minorants(&self, fidx: usize) -> usize { self.master.num_minorants(fidx) } - fn add_minorant(&mut self, fidx: usize, minorant: Minorant

) -> Result { + fn add_minorant(&mut self, fidx: usize, minorant: Mn) -> Result { self.master.add_minorant(fidx, minorant) } fn weight(&self) -> Real { self.master.weight() @@ -244,25 +244,21 @@ self.master.set_weight(weight) } fn add_vars( &mut self, - bounds: &[(Option, Real, Real)], - extend_subgradient: &mut SubgradientExtender, + bounds: &[(Real, Real)], + extend_subgradient: &mut SubgradientExtender, ) -> Result<(), Either> { + debug_assert!(bounds.iter().all(|&(l, u)| l <= u)); 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.lb.extend(bounds.iter().map(|x| x.0)); + self.ub.extend(bounds.iter().map(|x| x.1)); 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::>(); - self.master.add_vars(nnew, &changed, extend_subgradient) + let nnew = bounds.len(); + self.master.add_vars(nnew, extend_subgradient) } else { Ok(()) } } @@ -358,11 +354,11 @@ fn multiplier(&self, min: Self::MinorantIndex) -> Real { self.master.multiplier(min) } - fn aggregated_primal(&self, fidx: usize) -> Result { + fn aggregated_primal(&self, fidx: usize) -> Result { self.master.aggregated_primal(fidx) } fn move_center(&mut self, alpha: Real, d: &DVector) { self.need_new_candidate = true; @@ -384,19 +380,19 @@ /// /// `B` is a builder of the underlying `UnconstrainedMasterProblem`. #[derive(Default)] pub struct Builder(B); -impl super::Builder

for Builder -where - P: Aggregatable + Send + 'static, - B: unconstrained::Builder

, - B::MasterProblem: UnconstrainedMasterProblem

, -{ - type MasterProblem = BoxedMasterProblem; - - fn build(&mut self) -> Result>::Err> { +impl super::Builder for Builder +where + Mn: Minorant, + B: unconstrained::Builder, + B::MasterProblem: UnconstrainedMasterProblem, +{ + type MasterProblem = BoxedMasterProblem; + + fn build(&mut self) -> Result>::Err> { self.0.build().map(BoxedMasterProblem::with_master) } } impl std::ops::Deref for Builder { Index: src/master/boxed/unconstrained.rs ================================================================== --- src/master/boxed/unconstrained.rs +++ src/master/boxed/unconstrained.rs @@ -16,11 +16,11 @@ pub mod cpx; pub mod minimal; use crate::problem::SubgradientExtender; -use crate::{Aggregatable, DVector, Minorant, Real}; +use crate::{DVector, Minorant, Real}; use either::Either; use std::error::Error; /** @@ -45,12 +45,11 @@ * 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: Send + 'static { - /// Unique index for a minorant. +pub trait UnconstrainedMasterProblem: Send + 'static { type MinorantIndex: Copy + Eq; /// Error type for this master problem. type Err: Error + Send + Sync; @@ -80,22 +79,17 @@ /// 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>; /// Add a new minorant to the model. - fn add_minorant(&mut self, fidx: usize, minorant: Minorant

) -> Result; + fn add_minorant(&mut self, fidx: usize, minorant: M) -> Result; - /// 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. + /// Add `nnew` new variables. fn add_vars( &mut self, nnew: usize, - changed: &[usize], - extend_subgradient: &mut SubgradientExtender, + extend_subgradient: &mut SubgradientExtender, ) -> Result<(), Either>; /// Solve the master problem. fn solve(&mut self, eta: &DVector, fbound: Real, augbound: Real, relprec: Real) -> Result<(), Self::Err>; @@ -110,19 +104,19 @@ /// Return the value of the current model at the given point. fn eval_model(&self, y: &DVector) -> Real; /// Return the aggregated primal. - fn aggregated_primal(&self, fidx: usize) -> Result; + fn aggregated_primal(&self, fidx: usize) -> Result; /// 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 { +pub trait Builder { /// The master problem to be build. - type MasterProblem: UnconstrainedMasterProblem

; + type MasterProblem: UnconstrainedMasterProblem; /// Create a new master problem. - fn build(&mut self) -> Result>::Err>; + fn build(&mut self) -> Result>::Err>; } Index: src/master/boxed/unconstrained/cpx.rs ================================================================== --- src/master/boxed/unconstrained/cpx.rs +++ src/master/boxed/unconstrained/cpx.rs @@ -69,25 +69,18 @@ } pub type Result = std::result::Result; /// A minorant and its unique index. -struct MinorantInfo { - minorant: Minorant

, +struct MinorantInfo { + minorant: Mn, index: usize, } -impl Deref for MinorantInfo

{ - type Target = Minorant

; - fn deref(&self) -> &Minorant

{ - &self.minorant - } -} - -impl DerefMut for MinorantInfo

{ - fn deref_mut(&mut self) -> &mut Minorant

{ - &mut self.minorant +impl MinorantInfo { + fn new(minorant: Mn, index: usize) -> Self { + MinorantInfo { minorant, index } } } /// Maps a global index to a minorant. #[derive(Clone, Copy)] @@ -100,11 +93,11 @@ /// A submodel. /// /// A submodel is a list of subproblems being aggregated in that model. #[derive(Debug, Clone, Default)] -struct SubModel { +struct SubModel { /// The list of subproblems. subproblems: Vec, /// The number of minorants in this subproblem. /// @@ -112,27 +105,27 @@ num_mins: usize, /// The aggregated minorants of this submodel. /// /// This is just the sum of the corresponding minorants of the single /// functions contained in this submodel. - minorants: Vec>, + minorants: Vec<(Real, DVector)>, } -impl Deref for SubModel

{ +impl Deref for SubModel { type Target = Vec; fn deref(&self) -> &Vec { &self.subproblems } } -impl DerefMut for SubModel

{ +impl DerefMut for SubModel { fn deref_mut(&mut self) -> &mut Vec { &mut self.subproblems } } -pub struct CplexMaster { +pub struct CplexMaster { env: *mut cpx::Env, lp: *mut cpx::Lp, /// True if the QP must be updated. @@ -155,44 +148,44 @@ /// The weight of the quadratic term. weight: Real, /// The minorants for each subproblem in the model. - minorants: Vec>>, + minorants: Vec>>, /// The callback for the submodel for each subproblem. select_model: Arc usize>, /// For each submodel the list of subproblems contained in that model. - submodels: Vec>, + submodels: Vec, /// For each subproblem the submodel it is contained in. in_submodel: Vec, /// Optimal multipliers for each subproblem in the model. opt_mults: Vec, /// Optimal aggregated minorant. - opt_minorant: Minorant

, + opt_minorant: (Real, DVector), /// Maximal bundle size. pub max_bundle_size: usize, } -unsafe impl Send for CplexMaster

{} +unsafe impl Send for CplexMaster {} -impl Drop for CplexMaster

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

for CplexMaster

{ +impl UnconstrainedMasterProblem for CplexMaster { type MinorantIndex = usize; type Err = CplexMasterError; - fn new() -> Result> { + fn new() -> Result> { let env; trycpx!({ let mut status = 0; env = cpx::openCPLEX(&mut status); @@ -212,11 +205,11 @@ minorants: vec![], select_model: Arc::new(|i| i), submodels: vec![], in_submodel: vec![], opt_mults: vec![], - opt_minorant: Minorant::default(), + opt_minorant: Default::default(), max_bundle_size: 50, }) } fn num_subproblems(&self) -> usize { @@ -270,21 +263,26 @@ } } Ok(()) } - fn add_minorant(&mut self, fidx: usize, minorant: Minorant

) -> Result { + fn add_minorant(&mut self, fidx: usize, minorant: Mn) -> Result { debug!("Add minorant"); - debug!(" fidx={} index={}: {}", fidx, self.minorants[fidx].len(), minorant); + debug!( + " fidx={} index={}: {:?}", + fidx, + self.minorants[fidx].len(), + minorant.debug() + ); debug_assert!( self.minorants[fidx] .last() - .map_or(true, |m| m.linear.len() == minorant.linear.len()), + .map_or(true, |m| m.minorant.dim() == minorant.dim()), "Newly added minorant has wrong size (got: {}, expected: {})", - minorant.linear.len(), - self.minorants[fidx].last().map_or(0, |m| m.linear.len()) + minorant.dim(), + self.minorants[fidx].last().map_or(0, |m| m.minorant.dim()) ); // find new unique minorant index let min_idx = self.minorants[fidx].len(); let index = if let Some(index) = self.freeinds.pop() { @@ -295,39 +293,29 @@ self.index2min.len() - 1 }; self.updateinds.push(index); // store minorant - self.minorants[fidx].push(MinorantInfo { minorant, index }); + self.minorants[fidx].push(MinorantInfo::new(minorant, index)); self.opt_mults[fidx].push(0.0); Ok(index) } fn add_vars( &mut self, nnew: usize, - changed: &[usize], - extend_subgradient: &mut SubgradientExtender, + extend_subgradient: &mut SubgradientExtender, ) -> std::result::Result<(), Either> { debug_assert!(!self.minorants[0].is_empty()); - if changed.is_empty() && nnew == 0 { + if nnew == 0 { return Ok(()); } - 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); for (fidx, mins) in self.minorants.iter_mut().enumerate() { for m in &mut mins[..] { - let new_subg = (extend_subgradient)(fidx, &m.primal, &changedvars).map_err(Either::Right)?; - for (&j, &g) in changed.iter().zip(new_subg.iter()) { - m.linear[j] = g; - } - m.linear.extend_from_slice(&new_subg[changed.len()..]); + (extend_subgradient)(fidx, &mut m.minorant).map_err(Either::Right)?; } } // update qterm because all minorants have changed self.force_update = true; @@ -356,11 +344,11 @@ let mut c = Vec::with_capacity(nvars); let mut inds = Vec::with_capacity(nvars); for submodel in &self.submodels { for i in 0..submodel.num_mins { let m = &submodel.minorants[i]; - let cost = -m.constant * self.weight - m.linear.dot(eta); + let cost = -m.constant() * self.weight - m.linear(eta); inds.push(c.len() as c_int); c.push(cost); } } debug_assert_eq!(inds.len(), nvars); @@ -400,21 +388,21 @@ *mult = 0.0; } } } - self.opt_minorant = Aggregatable::combine(mults.into_iter().zip(mins)); + Mn::combine_to_vec(mults.into_iter().zip(mins), &mut self.opt_minorant); Ok(()) } fn dualopt(&self) -> &DVector { - &self.opt_minorant.linear + &self.opt_minorant.1 } fn dualopt_cutval(&self) -> Real { - self.opt_minorant.constant + self.opt_minorant.constant() } fn multiplier(&self, min: usize) -> Real { let MinorantIdx { fidx, idx } = self.index2min[min]; self.opt_mults[fidx][idx] @@ -430,23 +418,23 @@ result += this_val; } result } - fn aggregated_primal(&self, fidx: usize) -> Result

{ - Ok(P::combine( + fn aggregated_primal(&self, fidx: usize) -> Result { + Ok(Aggregatable::combine( self.opt_mults[fidx] .iter() .enumerate() - .map(|(i, alpha)| (*alpha, &self.minorants[fidx][i].primal)), + .map(|(i, alpha)| (*alpha, self.minorants[fidx][i].minorant.primal())), )) } fn move_center(&mut self, alpha: Real, d: &DVector) { for mins in &mut self.minorants { for m in mins.iter_mut() { - m.move_center_begin(alpha, d); + m.minorant.move_center_begin(alpha, d); } } for submod in &mut self.submodels { for m in &mut submod.minorants { m.move_center_begin(alpha, d); @@ -453,11 +441,11 @@ } } } } -impl CplexMaster

{ +impl CplexMaster { /// Set a custom submodel selector. /// /// For each subproblem index the selector should return a submodel index. /// All subproblems with the same submodel index are aggregated in a single /// cutting plane model. @@ -512,11 +500,11 @@ let minorants = &self.minorants; // Compute the number of minorants in each submodel. for submodel in self.submodels.iter_mut() { submodel.num_mins = submodel.iter().map(|&fidx| minorants[fidx].len()).min().unwrap_or(0); - submodel.minorants.resize_with(submodel.num_mins, Minorant::default); + submodel.minorants.resize_with(submodel.num_mins, Default::default); } // Only minorants belonging to the first subproblem of each submodel // must be updated. // @@ -543,12 +531,17 @@ .collect::>(); // Compute the aggregated minorants. for &(_, mod_i, i) in &updateinds { let submodel = &mut self.submodels[mod_i]; - submodel.minorants[i] = - Aggregatable::combine(submodel.iter().map(|&fidx| (1.0, &minorants[fidx][i].minorant))); + Mn::combine_to_vec( + submodel + .subproblems + .iter() + .map(|&fidx| (1.0, &minorants[fidx][i].minorant)), + &mut submodel.minorants[i], + ); } let submodels = &self.submodels; // Build quadratic term, this is for all pairs of minorants where each g_i @@ -571,15 +564,15 @@ for submodel_i in submodels.iter() { // Compute the minorant g_i for each i for i in 0..submodel_i.num_mins { // Store the computed values at the index of the first subproblem in this model. let idx_i = minorants[submodel_i[0]][i].index; - let g_i = &submodel_i.minorants[i].linear; + let g_i = &submodel_i.minorants[i].1; // Now compute the inner product with each other minorant // that has to be updated. for &(idx_j, mod_j, j) in updateinds.iter() { - let x = submodels[mod_j].minorants[j].linear.dot(g_i); + let x = submodels[mod_j].minorants[j].linear(g_i); self.qterm[idx_i][idx_j] = x; self.qterm[idx_j][idx_i] = x; } } } @@ -590,11 +583,11 @@ for i in 0..submod_i.num_mins { let idx_i = self.minorants[submod_i[0]][i].index; for submod_j in submodels.iter() { for j in 0..submod_j.num_mins { let idx_j = self.minorants[submod_j[0]][j].index; - let x = submod_i.minorants[i].linear.dot(&submod_j.minorants[j].linear); + let x = submod_i.minorants[i].linear(&submod_j.minorants[j].1); debug_assert!((x - self.qterm[idx_i][idx_j]) < 1e-6); } } } } @@ -778,14 +771,14 @@ select_model: Arc::new(|i| i), } } } -impl super::Builder

for Builder { - type MasterProblem = CplexMaster

; +impl super::Builder for Builder { + type MasterProblem = CplexMaster; - fn build(&mut self) -> Result> { + fn build(&mut self) -> Result> { let mut cpx = CplexMaster::new()?; cpx.max_bundle_size = self.max_bundle_size; cpx.select_model = self.select_model.clone(); cpx.update_submodels(); Ok(cpx) Index: src/master/boxed/unconstrained/minimal.rs ================================================================== --- src/master/boxed/unconstrained/minimal.rs +++ src/master/boxed/unconstrained/minimal.rs @@ -58,11 +58,11 @@ * * 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 { +pub struct MinimalMaster { /// The weight of the quadratic term. weight: Real, /// The minorants in the model. /// @@ -69,11 +69,11 @@ /// There are up to two minorants, each minorant consists of one part for /// each subproblem. /// /// The minorants for the i-th subproblem have the indices `2*i` and /// `2*i+1`. - minorants: [Vec>; 2], + minorants: [Vec; 2], /// The number of minorants. Only the minorants with index less than this /// number are valid. num_minorants: usize, /// The number of minorants for each subproblem. num_minorants_of: Vec, @@ -84,29 +84,29 @@ /// The number of subproblems with at least 2 minorants. num_subproblems_with_2: usize, /// Optimal multipliers. opt_mult: [Real; 2], /// Optimal aggregated minorant. - opt_minorant: Minorant

, + opt_minorant: (Real, DVector), } -impl UnconstrainedMasterProblem

for MinimalMaster

{ +impl UnconstrainedMasterProblem for MinimalMaster { type MinorantIndex = usize; type Err = MinimalMasterError; - fn new() -> Result, Self::Err> { + fn new() -> Result, Self::Err> { Ok(MinimalMaster { weight: 1.0, num_minorants: 0, num_minorants_of: vec![], num_subproblems: 0, num_subproblems_with_1: 0, num_subproblems_with_2: 0, minorants: [vec![], vec![]], opt_mult: [0.0, 0.0], - opt_minorant: Minorant::default(), + opt_minorant: Default::default(), }) } fn num_subproblems(&self) -> usize { self.num_subproblems @@ -117,30 +117,41 @@ self.num_minorants = 0; self.num_minorants_of = vec![0; n]; self.num_subproblems_with_1 = 0; self.num_subproblems_with_2 = 0; self.minorants = [ - (0..n).map(|_| Minorant::default()).collect(), - (0..n).map(|_| Minorant::default()).collect(), + (0..n).map(|_| Default::default()).collect(), + (0..n).map(|_| Default::default()).collect(), ]; Ok(()) } fn compress(&mut self) -> Result<(), Self::Err> { if self.num_minorants == 2 { debug!("Aggregate"); - debug!(" {} * {:?}", self.opt_mult[0], self.minorants[0]); - debug!(" {} * {:?}", self.opt_mult[1], self.minorants[1]); + debug!( + " {} * {:?}", + self.opt_mult[0], + self.minorants[0].iter().map(|m| m.debug()).collect::>() + ); + debug!( + " {} * {:?}", + self.opt_mult[1], + self.minorants[1].iter().map(|m| m.debug()).collect::>() + ); self.minorants[0] = Aggregatable::combine(self.opt_mult.iter().cloned().zip(&self.minorants)); self.opt_mult[0] = 1.0; self.num_minorants = 1; self.num_minorants_of.clear(); self.num_minorants_of.resize(self.num_subproblems, 1); self.num_subproblems_with_2 = 0; - debug!(" {:?}", self.minorants[0]); + debug!( + " {:?}", + self.minorants[0].iter().map(|m| m.debug()).collect::>() + ); } Ok(()) } fn weight(&self) -> Real { @@ -155,11 +166,11 @@ fn num_minorants(&self, fidx: usize) -> usize { self.num_minorants_of[fidx] } - fn add_minorant(&mut self, fidx: usize, minorant: Minorant

) -> Result { + fn add_minorant(&mut self, fidx: usize, minorant: Mn) -> Result { if self.num_minorants_of[fidx] >= 2 { return Err(MinimalMasterError::MaxMinorants { subproblem: fidx }); } let minidx = self.num_minorants_of[fidx]; @@ -188,38 +199,19 @@ } fn add_vars( &mut self, nnew: usize, - changed: &[usize], - extend_subgradient: &mut SubgradientExtender, + extend_subgradient: &mut SubgradientExtender, ) -> Result<(), Either> { - if self.num_subproblems_with_1 == 0 { + if nnew == 0 || self.num_subproblems_with_1 == 0 { return Ok(()); } - let noldvars = self.minorants[0][self - .num_minorants_of - .iter() - .position(|&n| n > 0) - .ok_or(MinimalMasterError::NoMinorants) - .map_err(Either::Left)?] - .linear - .len(); - let mut changedvars = vec![]; - changedvars.extend_from_slice(changed); - changedvars.extend(noldvars..noldvars + nnew); - for fidx in 0..self.num_subproblems { for i in 0..self.num_minorants_of[fidx] { - let new_subg = - (extend_subgradient)(fidx, &self.minorants[i][fidx].primal, &changedvars).map_err(Either::Right)?; - let m = &mut self.minorants[i][fidx]; - for (&j, &g) in changed.iter().zip(new_subg.iter()) { - m.linear[j] = g; - } - m.linear.extend_from_slice(&new_subg[changed.len()..]); + (extend_subgradient)(fidx, &mut self.minorants[i][fidx]).map_err(Either::Right)?; } } Ok(()) } @@ -226,67 +218,73 @@ #[allow(unused_variables)] fn solve(&mut self, eta: &DVector, fbound: Real, augbound: Real, relprec: Real) -> Result<(), Self::Err> { for fidx in 0..self.num_subproblems { for i in 0..self.num_minorants_of[fidx] { - debug!(" min(fidx:{}, i:{}) = {}", fidx, i, self.minorants[i][fidx]); + debug!(" min(fidx:{}, i:{}) = {:?}", fidx, i, self.minorants[i][fidx].debug()); } } if self.num_minorants == 2 { - let min0 = Minorant::combine((0..self.num_subproblems).map(|fidx| (1.0, &self.minorants[0][fidx]))); - let min1 = Minorant::combine((0..self.num_subproblems).map(|fidx| (1.0, &self.minorants[1][fidx]))); - let xx = min0.linear.dot(&min0.linear); - let yy = min1.linear.dot(&min1.linear); - let xy = min0.linear.dot(&min1.linear); - let xeta = min0.linear.dot(eta); - let yeta = min1.linear.dot(eta); + let min0: Mn = Aggregatable::combine((0..self.num_subproblems).map(|fidx| (1.0, &self.minorants[0][fidx]))); + let min1: Mn = Aggregatable::combine((0..self.num_subproblems).map(|fidx| (1.0, &self.minorants[1][fidx]))); + let xx = min0.product(&min0); + let yy = min1.product(&min1); + let xy = min0.product(&min1); + let xeta = min0.linear(eta); + let yeta = min1.linear(eta); let a = yy - 2.0 * xy + xx; let b = xy - xx - yeta + xeta; let mut alpha2 = 0.0; if a > 0.0 { - alpha2 = ((min1.constant - min0.constant) * self.weight - b) / a; + alpha2 = ((min1.constant() - min0.constant()) * self.weight - b) / a; alpha2 = alpha2.max(0.0).min(1.0); } self.opt_mult[0] = 1.0 - alpha2; self.opt_mult[1] = alpha2; - self.opt_minorant = Aggregatable::combine(self.opt_mult.iter().cloned().zip([min0, min1].iter())); + Mn::combine_to_vec( + self.opt_mult.iter().cloned().zip([min0, min1].iter()), + &mut self.opt_minorant, + ); } else if self.num_minorants == 1 { - let min0 = Aggregatable::combine((0..self.num_subproblems).map(|fidx| (1.0, &self.minorants[0][fidx]))); - self.opt_minorant = min0; + let mins0 = &self.minorants[0]; + Mn::combine_to_vec( + std::iter::repeat(1.0).zip(mins0).take(self.num_subproblems), + &mut self.opt_minorant, + ); self.opt_mult[0] = 1.0; } else { return Err(MinimalMasterError::NoMinorants); } debug!("Unrestricted"); - debug!(" opt_minorant={}", self.opt_minorant); + debug!(" opt_minorant={:?}", self.opt_minorant.debug()); debug!(" opt_mult={:?}", &self.opt_mult[0..self.num_minorants]); Ok(()) } fn dualopt(&self) -> &DVector { - &self.opt_minorant.linear + &self.opt_minorant.1 } fn dualopt_cutval(&self) -> Real { - self.opt_minorant.constant + self.opt_minorant.0 } fn multiplier(&self, min: usize) -> Real { self.opt_mult[min % 2] } - fn aggregated_primal(&self, fidx: usize) -> Result { - Ok(P::combine( + fn aggregated_primal(&self, fidx: usize) -> Result { + Ok(Aggregatable::combine( self.opt_mult .iter() .take(self.num_minorants_of[fidx]) .enumerate() - .map(|(i, alpha)| (*alpha, &self.minorants[i][fidx].primal)), + .map(|(i, alpha)| (*alpha, self.minorants[i][fidx].primal())), )) } fn eval_model(&self, y: &DVector) -> Real { let mut result = NEG_INFINITY; @@ -311,12 +309,12 @@ fn default() -> Self { Builder } } -impl super::Builder

for Builder { - type MasterProblem = MinimalMaster

; +impl super::Builder for Builder { + type MasterProblem = MinimalMaster; - fn build(&mut self) -> Result, MinimalMasterError> { + fn build(&mut self) -> Result, MinimalMasterError> { MinimalMaster::new() } } Index: src/master/mod.rs ================================================================== --- src/master/mod.rs +++ src/master/mod.rs @@ -38,11 +38,11 @@ pub mod boxed; pub use self::boxed::BoxedMasterProblem; use crate::problem::SubgradientExtender; -use crate::{Aggregatable, DVector, Minorant, Real}; +use crate::{DVector, Minorant, Real}; use either::Either; use std::error::Error; use std::result::Result; /// Trait for master problems of a proximal bundle methods. @@ -49,11 +49,11 @@ /// /// Note that solvers are allowed to create multiple master problems potentially /// running them in different threads. Because of this they must implement `Send /// + 'static`, i.e. they must be quite self-contained and independent from /// everything else. -pub trait MasterProblem: Send + 'static { +pub trait MasterProblem: Send + 'static { /// Unique index for a minorant. type MinorantIndex: Copy + Eq; /// The error returned by the master problem. type Err: Error + Send + Sync; @@ -88,26 +88,23 @@ 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. + /// Add some variables with bounds. fn add_vars( &mut self, - bounds: &[(Option, Real, Real)], - extend_subgradient: &mut SubgradientExtender, + bounds: &[(Real, Real)], + extend_subgradient: &mut SubgradientExtender, ) -> Result<(), Either>; /// 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; + fn add_minorant(&mut self, fidx: usize, minorant: M) -> Result; /// Solve the master problem. fn solve(&mut self, cur_value: Real) -> Result<(), Self::Err>; /// Compress the bundle. @@ -134,28 +131,28 @@ /// Return the multiplier associated with a minorant. fn multiplier(&self, min: Self::MinorantIndex) -> Real; /// Return the aggregated primal. - fn aggregated_primal(&self, fidx: usize) -> Result; + fn aggregated_primal(&self, fidx: usize) -> Result; /// Move the center of the master problem to $\alpha \cdot d$. /// /// The vector `d` is allowed to be shorter than the current number of /// variables in the master. The missing elements are assumed to be zero. fn move_center(&mut self, alpha: Real, d: &DVector); } /// A builder for creating a master problem solvers. -pub trait Builder { +pub trait Builder { /// The master problem to be build. - type MasterProblem: MasterProblem

; + type MasterProblem: MasterProblem; /// Create a new master problem. - fn build(&mut self) -> Result>::Err>; + fn build(&mut self) -> Result>::Err>; } /// The full bundle builder. pub type FullMasterBuilder = boxed::Builder; /// The minimal bundle builder. pub type MinimalMasterBuilder = boxed::Builder; Index: src/mcf/problem.rs ================================================================== --- src/mcf/problem.rs +++ src/mcf/problem.rs @@ -419,11 +419,11 @@ } impl ParallelProblem for MMCFProblem { type Err = Error; - type Primal = DVector; + type Minorant = (Real, DVector, DVector); fn num_variables(&self) -> usize { self.active_constraints.read().unwrap().len() } @@ -460,25 +460,20 @@ .as_ref() .unwrap() .execute(move || match sub.write().unwrap().evaluate(&y, active_constraints) { Ok((objective, subg, primal)) => { tx.objective(objective).unwrap(); - tx.minorant(Minorant { - constant: objective, - linear: subg, - primal, - }) - .unwrap(); + tx.minorant((objective, subg, primal)).unwrap(); } Err(err) => tx.error(err).unwrap(), }); Ok(()) } fn update(&mut self, state: U, tx: S) -> Result<()> where - U: ParallelUpdateState, + U: ParallelUpdateState<::Primal>, S: UpdateSender + 'static, { if self.inactive_constraints.read().unwrap().is_empty() { return Ok(()); } @@ -527,16 +522,16 @@ let nnew = active.len() - nold; if nnew > 0 { let actives = active.clone(); if let Err(err) = tx.add_variables( vec![(0.0, Real::infinity()); nnew], - Box::new(move |fidx: usize, primal: &DVector, inds: &[usize]| { + Box::new(move |fidx: usize, m: &mut Self::Minorant| { let sub = subs[fidx].read().unwrap(); - Ok(inds - .iter() - .map(|&i| sub.evaluate_constraint(primal, actives[i])) - .collect()) + let n = m.dim(); + let primal = &m.2; + m.1.extend((n..n + nnew).map(|i| sub.evaluate_constraint(primal, actives[i]))); + Ok(()) }), ) { warn!("Error sending problem update: {}", err); } } Index: src/problem.rs ================================================================== --- src/problem.rs +++ src/problem.rs @@ -16,11 +16,11 @@ */ //! An asynchronous first-order oracle. pub use crate::data::minorant::SubgradientExtender; -use crate::{Aggregatable, DVector, Minorant, Real}; +use crate::{DVector, Minorant, Real}; use std::sync::Arc; /// Channel to send evaluation results to. pub trait ResultSender

: Send where @@ -30,11 +30,11 @@ /// Send a new objective `value`. fn objective(&self, value: Real) -> Result<(), Self::Err>; /// Send a new `minorant` with associated `primal`. - fn minorant(&self, minorant: Minorant) -> Result<(), Self::Err>; + fn minorant(&self, minorant: P::Minorant) -> Result<(), Self::Err>; /// Send an error message. fn error(&self, err: P::Err) -> Result<(), Self::Err>; } @@ -51,11 +51,11 @@ /// computes subgradients for the given variables based on the associated /// primals. fn add_variables( &self, bounds: Vec<(Real, Real)>, - sgext: Box>, + sgext: Box>, ) -> Result<(), Self::Err>; /// Send an error message. fn error(&self, err: P::Err) -> Result<(), Self::Err>; } @@ -92,12 +92,12 @@ /// asynchronous. pub trait FirstOrderProblem { /// Error raised by this oracle. type Err; - /// The primal information associated with a minorant. - type Primal: Aggregatable + Send + 'static; + /// The minorant information. + type Minorant: Minorant; /// Return the number of variables. fn num_variables(&self) -> usize; /// Return the lower bounds on the variables. @@ -175,12 +175,12 @@ /// The updates might be generated asynchronously. /// /// The default implementation does nothing. fn update(&mut self, _state: U, _tx: S) -> Result<(), Self::Err> where - U: UpdateState, + U: UpdateState<::Primal>, S: UpdateSender + 'static, Self: Sized, { Ok(()) } } Index: src/solver/asyn.rs ================================================================== --- src/solver/asyn.rs +++ src/solver/asyn.rs @@ -28,11 +28,11 @@ use std::iter::repeat; use std::sync::Arc; use std::time::Instant; use threadpool::ThreadPool; -use crate::{DVector, Real}; +use crate::{DVector, Minorant, Real}; use super::channels::{ ChannelResultSender, ChannelUpdateSender, ClientReceiver, ClientSender, EvalResult, Message, Update, }; use super::masterprocess::{self, MasterConfig, MasterProcess, MasterResponse, Response}; @@ -87,12 +87,12 @@ /// - `P` is the `FirstOrderProblem` associated with the solver, /// - `M` is the `MasterBuilder` associated with the solver. pub type Result = std::result::Result< T, Error< - <::Primal>>::MasterProblem as MasterProblem< -

::Primal, + <::Minorant>>::MasterProblem as MasterProblem< +

::Minorant, >>::Err,

::Err, >, >; @@ -397,11 +397,11 @@ /// Implementation of a parallel bundle method. pub struct Solver where P: FirstOrderProblem, P::Err: 'static, - M: MasterBuilder, + M: MasterBuilder, { /// Parameters for the solver. pub params: Parameters, /// Termination predicate. @@ -450,11 +450,11 @@ where P: FirstOrderProblem, P::Err: Send + 'static, T: Terminator + Default, W: Weighter + Default, - M: MasterBuilder, + M: MasterBuilder, { /// Create a new parallel bundle solver. pub fn new(problem: P) -> Self where M: Default, @@ -680,11 +680,11 @@ /// /// The function returns /// - `Ok(true)` if the final iteration count has been reached, /// - `Ok(false)` if the final iteration count has not been reached, /// - `Err(_)` on error. - fn handle_client_response(&mut self, msg: EvalResult) -> Result { + fn handle_client_response(&mut self, msg: EvalResult) -> Result { let master = self.master_proc.as_mut().ok_or(Error::NotInitialized)?; match msg { EvalResult::ObjectiveValue { index, value } => { debug!("Receive objective from subproblem {}: {}", index, value); if self.data.nxt_ubs[index].is_infinite() { @@ -697,11 +697,11 @@ if self.data.nxt_cutvals[index].is_infinite() { self.data.cnt_remaining_mins -= 1; } // move center of minorant to cur_y minorant.move_center(-1.0, &self.data.nxt_d); - self.data.nxt_cutvals[index] = self.data.nxt_cutvals[index].max(minorant.constant); + self.data.nxt_cutvals[index] = self.data.nxt_cutvals[index].max(minorant.constant()); // add minorant to master problem master.add_minorant(index, minorant)?; } EvalResult::Done { .. } => return Ok(false), // currently we do nothing ... EvalResult::Error { err, .. } => return Err(Error::Evaluation(err)), @@ -928,19 +928,19 @@ /// Handles an update response `update` of the problem. /// /// The method is called if the problem informs the solver about a change of /// the problem, e.g. adding a new variable. This method updates the other /// parts of the solver, e.g. the master problem, about the modification. - fn handle_update_response(&mut self, update: Update) -> Result<(), P, M> { + fn handle_update_response(&mut self, update: Update) -> Result<(), P, M> { match update { Update::AddVariables { bounds, sgext, .. } => { if !bounds.is_empty() { // add new variables self.master_proc .as_mut() .unwrap() - .add_vars(bounds.into_iter().map(|(l, u)| (None, l, u)).collect(), sgext)?; + .add_vars(bounds.into_iter().map(|(l, u)| (l, u)).collect(), sgext)?; } } Update::Done { .. } => self.data.update_in_progress = false, // currently we do nothing ... Update::Error { err, .. } => { self.data.update_in_progress = false; @@ -985,13 +985,13 @@ self.data.cur_val ); } /// Return the aggregated primal of the given subproblem. - pub fn aggregated_primal(&self, subproblem: usize) -> Result { + pub fn aggregated_primal(&self, subproblem: usize) -> Result<::Primal, P, M> { Ok(self .master_proc .as_ref() .ok_or(Error::NotSolved)? .get_aggregated_primal(subproblem)?) } } Index: src/solver/channels.rs ================================================================== --- src/solver/channels.rs +++ src/solver/channels.rs @@ -18,11 +18,11 @@ //! Implementation for `ResultSender` using channels. use super::masterprocess::Response as MasterResponse; use crate::master::MasterProblem; use crate::problem::{FirstOrderProblem, ResultSender, SubgradientExtender, UpdateSender}; -use crate::{Aggregatable, Minorant, Real}; +use crate::{Minorant, Real}; #[cfg(feature = "crossbeam")] use rs_crossbeam::channel::{Receiver, SendError, Sender}; #[cfg(not(feature = "crossbeam"))] use std::sync::mpsc::{Receiver, SendError, Sender}; @@ -31,39 +31,39 @@ /// /// The client might be either a subproblem or a master problem process. /// /// A client may send one of two possible messages: either an evaluation result /// or a problem update. -pub enum Message +pub enum Message where - P: Aggregatable, + Mn: Minorant, { /// An evaluation result. - Eval(EvalResult), + Eval(EvalResult), /// A problem update. - Update(Update), + Update(Update), /// A master problem result. Master(MasterResponse), } /// The sender for client messages. pub type ClientSender = Sender< Message< usize, -

::Primal, +

::Minorant,

::Err, - ::Primal>>::Err, + ::Minorant>>::Err, >, >; /// The receiver for client messages. pub type ClientReceiver = Receiver< Message< usize, -

::Primal, +

::Minorant,

::Err, - ::Primal>>::Err, + ::Minorant>>::Err, >, >; /// Parameters for tuning the solver. @@ -74,18 +74,18 @@ /// essentially two types of information: /// /// 1. The (exact) function value of a sub-function at some point. /// 2. A minorant of some sub-function. #[derive(Debug)] -pub enum EvalResult +pub enum EvalResult where - P: Aggregatable, + Mn: Minorant, { /// The objective value at some point. ObjectiveValue { index: I, value: Real }, /// A minorant with an associated primal. - Minorant { index: I, minorant: Minorant

}, + Minorant { index: I, minorant: Mn }, /// An error occurred. Error { index: I, err: E }, /// Done, no further message will be received from this evaluation. Done { index: I }, } @@ -93,62 +93,65 @@ /// Problem update information. /// /// The solver calls the `update` method of the problem regularly. /// This method can modify the problem by adding (or moving) /// variables. The possible updates are encoded in this type. -pub enum Update { +pub enum Update +where + Mn: Minorant, +{ /// Add new variables with bounds. /// /// The initial value of each variable will be the feasible value /// closest to 0. AddVariables { index: I, bounds: Vec<(Real, Real)>, - sgext: Box>, + sgext: Box>, }, /// An error occurred. Error { index: I, err: E }, /// Done, no further message will be received from this evaluation. Done { index: I }, } -pub struct ChannelResultSender -where - I: Clone, - P: Aggregatable, -{ - index: I, - tx: Sender>, -} - -impl ChannelResultSender -where - I: Clone, - P: Aggregatable, -{ - pub fn new(index: I, tx: Sender>) -> Self { - ChannelResultSender { index, tx } - } -} - -impl ResultSender

for ChannelResultSender +pub struct ChannelResultSender +where + I: Clone, + Mn: Minorant, +{ + index: I, + tx: Sender>, +} + +impl ChannelResultSender +where + I: Clone, + Mn: Minorant, +{ + pub fn new(index: I, tx: Sender>) -> Self { + ChannelResultSender { index, tx } + } +} + +impl ResultSender

for ChannelResultSender where I: Clone + Send, P: FirstOrderProblem, P::Err: Send, M: Send, { - type Err = SendError>; + type Err = SendError>; fn objective(&self, value: Real) -> Result<(), Self::Err> { self.tx.send(Message::Eval(EvalResult::ObjectiveValue { index: self.index.clone(), value, })) } - fn minorant(&self, minorant: Minorant) -> Result<(), Self::Err> { + fn minorant(&self, minorant: P::Minorant) -> Result<(), Self::Err> { self.tx.send(Message::Eval(EvalResult::Minorant { index: self.index.clone(), minorant, })) } @@ -159,14 +162,14 @@ err, })) } } -impl Drop for ChannelResultSender +impl Drop for ChannelResultSender where I: Clone, - P: Aggregatable, + Mn: Minorant, { fn drop(&mut self) { self.tx .send(Message::Eval(EvalResult::Done { index: self.index.clone(), @@ -173,42 +176,42 @@ })) .unwrap() } } -pub struct ChannelUpdateSender -where - I: Clone, - P: Aggregatable, -{ - index: I, - tx: Sender>, -} - -impl ChannelUpdateSender -where - I: Clone, - P: Aggregatable, -{ - pub fn new(index: I, tx: Sender>) -> Self { +pub struct ChannelUpdateSender +where + I: Clone, + Mn: Minorant, +{ + index: I, + tx: Sender>, +} + +impl ChannelUpdateSender +where + I: Clone, + Mn: Minorant, +{ + pub fn new(index: I, tx: Sender>) -> Self { ChannelUpdateSender { index, tx } } } -impl UpdateSender

for ChannelUpdateSender +impl UpdateSender

for ChannelUpdateSender where I: Clone + Send, P: FirstOrderProblem, P::Err: Send, M: Send, { - type Err = SendError>; + type Err = SendError>; fn add_variables( &self, bounds: Vec<(Real, Real)>, - sgext: Box>, + sgext: Box>, ) -> Result<(), Self::Err> { self.tx.send(Message::Update(Update::AddVariables { index: self.index.clone(), bounds, sgext, @@ -221,18 +224,18 @@ err, })) } } -impl Drop for ChannelUpdateSender +impl Drop for ChannelUpdateSender where I: Clone, - P: Aggregatable, + Mn: Minorant, { fn drop(&mut self) { self.tx .send(Message::Update(Update::Done { index: self.index.clone(), })) .unwrap() } } Index: src/solver/masterprocess.rs ================================================================== --- src/solver/masterprocess.rs +++ src/solver/masterprocess.rs @@ -28,11 +28,11 @@ use threadpool::ThreadPool; use super::channels::{ClientSender, Message}; use crate::master::MasterProblem; use crate::problem::{FirstOrderProblem, SubgradientExtender}; -use crate::{Aggregatable, DVector, Minorant, Real}; +use crate::{DVector, Minorant, Real}; #[derive(Debug)] pub enum Error { /// The communication channel for sending requests has been disconnected. DisconnectedSender, @@ -106,20 +106,20 @@ /// The lower bounds on the variables. pub upper_bounds: Option, } /// A task for the master problem. -enum MasterTask +enum MasterTask where - M: MasterProblem, - Pr: Aggregatable, + Mn: Minorant, + M: MasterProblem, { - /// Add new variables to the master problem. - AddVariables(Vec<(Option, Real, Real)>, Box>), + /// Add new variables with bounds to the master problem. + AddVariables(Vec<(Real, Real)>, Box>), /// Add a new minorant for a subfunction to the master problem. - AddMinorant(usize, Minorant), + AddMinorant(usize, Mn), /// Move the center of the master problem in the given direction. MoveCenter(Real, Arc), /// Start a new computation of the master problem. @@ -132,11 +132,11 @@ SetWeight { weight: Real }, /// Return the current aggregated primal. GetAggregatedPrimal { subproblem: usize, - tx: Sender>, + tx: Sender>, }, } /// The response send from a master process. /// @@ -154,20 +154,21 @@ Error(Error), } /// Convenient type for `Response`. pub type MasterResponse = - Response<::Primal>>::Err,

::Err>; + Response<::Minorant>>::Err,

::Err>; -type ToMasterSender = Sender::Primal,

::Err, M>>; +type ToMasterSender = Sender::Minorant,

::Err, M>>; -type ToMasterReceiver = Receiver::Primal,

::Err, M>>; +type ToMasterReceiver = + Receiver::Minorant,

::Err, M>>; pub struct MasterProcess where P: FirstOrderProblem, - M: MasterProblem, + M: MasterProblem, { /// The channel to transmit new tasks to the master problem. tx: ToMasterSender, phantom: std::marker::PhantomData, @@ -174,13 +175,13 @@ } impl MasterProcess where P: FirstOrderProblem, - P::Primal: Send + 'static, + P::Minorant: Send + 'static, P::Err: Send + 'static, - M: MasterProblem + Send + 'static, + M: MasterProblem + Send + 'static, M::Err: Send + 'static, { pub fn start(master: M, master_config: MasterConfig, tx: ClientSender, threadpool: &mut ThreadPool) -> Self { // Create a pair of communication channels. let (to_master_tx, to_master_rx) = channel(); @@ -206,12 +207,12 @@ } /// Add new variables to the master problem. pub fn add_vars( &mut self, - vars: Vec<(Option, Real, Real)>, - sgext: Box>, + vars: Vec<(Real, Real)>, + sgext: Box>, ) -> Result<(), Error> where P::Err: 'static, { Ok(self.tx.send(MasterTask::AddVariables(vars, sgext))?) @@ -219,11 +220,11 @@ /// Add a new minorant to the master problem model. /// /// This adds the specified `minorant` with associated `primal` data to the /// model of subproblem `i`. - pub fn add_minorant(&mut self, i: usize, minorant: Minorant) -> Result<(), Error> { + pub fn add_minorant(&mut self, i: usize, minorant: P::Minorant) -> Result<(), Error> { Ok(self.tx.send(MasterTask::AddMinorant(i, minorant))?) } /// Move the center of the master problem. /// @@ -250,11 +251,14 @@ pub fn set_weight(&mut self, weight: Real) -> Result<(), Error> { Ok(self.tx.send(MasterTask::SetWeight { weight })?) } /// Get the current aggregated primal for a certain subproblem. - pub fn get_aggregated_primal(&self, subproblem: usize) -> Result> { + pub fn get_aggregated_primal( + &self, + subproblem: usize, + ) -> Result<::Primal, Error> { let (tx, rx) = channel(); self.tx.send(MasterTask::GetAggregatedPrimal { subproblem, tx })?; rx.recv()?.map_err(Error::Aggregation) } @@ -262,11 +266,11 @@ fn master_main( master: M, master_config: MasterConfig, tx: &mut ClientSender, rx: ToMasterReceiver, - subgradient_extender: &mut Option>>, + subgradient_extender: &mut Option>>, ) -> Result<(), Error> { let mut master = master; // Initialize the master problem. master @@ -296,16 +300,13 @@ // It may happen the number new minorant belongs to an earlier evaluation // with less variables (i.e. new variables have been added // after the start of the evaluation but before the new // minorant is added, i.e. now). In this case we must add // extend the minorant accordingly. - if m.linear.len() < master.num_variables() { + if m.dim() < master.num_variables() { if let Some(ref mut sgext) = subgradient_extender { - let newinds = (m.linear.len()..master.num_variables()).collect::>(); - let new_subg = - sgext(i, &m.primal, &newinds).map_err(Error::::SubgradientExtension)?; - m.linear.extend(new_subg); + sgext(i, &mut m).map_err(Error::::SubgradientExtension)?; } } master.add_minorant(i, m).map_err(Error::Master)?; } MasterTask::MoveCenter(alpha, d) => { Index: src/solver/sync.rs ================================================================== --- src/solver/sync.rs +++ src/solver/sync.rs @@ -22,16 +22,16 @@ #[cfg(not(feature = "crossbeam"))] use std::sync::mpsc::{channel, RecvError}; use log::{debug, info, warn}; use num_cpus; -use num_traits::Float; +use num_traits::{Float, Zero}; use std::sync::Arc; use std::time::Instant; use threadpool::ThreadPool; -use crate::{DVector, Real}; +use crate::{DVector, Minorant, Real}; use super::channels::{ ChannelResultSender, ChannelUpdateSender, ClientReceiver, ClientSender, EvalResult, Message, Update, }; use super::masterprocess::{self, MasterConfig, MasterProcess, MasterResponse, Response}; @@ -86,12 +86,12 @@ /// - `P` is the `FirstOrderProblem` associated with the solver, /// - `M` is the `MasterBuilder` associated with the solver. pub type Result = std::result::Result< T, Error< - <::Primal>>::MasterProblem as MasterProblem< -

::Primal, + <::Minorant>>::MasterProblem as MasterProblem< +

::Minorant, >>::Err,

::Err, >, >; @@ -395,11 +395,11 @@ /// Implementation of a parallel bundle method. pub struct Solver where P: FirstOrderProblem, - M: MasterBuilder, + M: MasterBuilder, P::Err: 'static, { /// Parameters for the solver. pub params: Parameters, @@ -449,11 +449,11 @@ where P: FirstOrderProblem, P::Err: Send + 'static, T: Terminator + Default, W: Weighter + Default, - M: MasterBuilder, + M: MasterBuilder, { /// Create a new parallel bundle solver. pub fn new(problem: P) -> Self where M: Default, @@ -652,11 +652,11 @@ } /// Handle a response from a subproblem evaluation. /// /// The function returns `Ok(true)` if the final iteration count has been reached. - fn handle_client_response(&mut self, msg: EvalResult) -> Result { + fn handle_client_response(&mut self, msg: EvalResult) -> Result { let master = self.master_proc.as_mut().ok_or(Error::NotInitialized)?; match msg { EvalResult::ObjectiveValue { index, value } => { debug!("Receive objective from subproblem {}: {}", index, value); if self.data.nxt_ubs[index].is_infinite() { @@ -669,11 +669,11 @@ if self.data.nxt_cutvals[index].is_infinite() { self.data.cnt_remaining_mins -= 1; } // move center of minorant to cur_y minorant.move_center(-1.0, &self.data.nxt_d); - self.data.nxt_cutvals[index] = self.data.nxt_cutvals[index].max(minorant.constant); + self.data.nxt_cutvals[index] = self.data.nxt_cutvals[index].max(minorant.constant()); // add minorant to master problem master.add_minorant(index, minorant)?; } EvalResult::Done { .. } => return Ok(false), // nothing to do here EvalResult::Error { err, .. } => return Err(Error::Evaluation(err)), @@ -849,37 +849,26 @@ for msg in update_rx { if let Message::Update(update) = msg { match update { Update::AddVariables { bounds, sgext, .. } => { have_update = true; - let mut newvars = Vec::with_capacity(bounds.len()); - for (lower, upper) in bounds { - if lower > upper { - return Err(Error::InvalidBounds { lower, upper }); - } - let value = if lower > 0.0 { - lower - } else if upper < 0.0 { - upper - } else { - 0.0 - }; - //self.bounds.push((lower, upper)); - newvars.push((None, lower - value, upper - value, value)); - } + let newvars = bounds + .into_iter() + .map(|(lower, upper)| { + if lower <= upper { + let value = lower.max(Real::zero()).min(upper); + Ok((lower - value, upper - value, value)) + } else { + Err(Error::InvalidBounds { lower, upper }) + } + }) + .collect::, P, M>>()?; if !newvars.is_empty() { - // modify moved variables - for (index, val) in newvars.iter().filter_map(|v| v.0.map(|i| (i, v.3))) { - self.data.cur_y[index] = val; - } - - // add new variables - self.data - .cur_y - .extend(newvars.iter().filter(|v| v.0.is_none()).map(|v| v.3)); - - master_proc.add_vars(newvars.iter().map(|v| (v.0, v.1, v.2)).collect(), sgext)?; + // add new variables + self.data.cur_y.extend(newvars.iter().map(|v| v.2)); + + master_proc.add_vars(newvars.iter().map(|v| (v.0, v.1)).collect(), sgext)?; } } Update::Done { .. } => (), // there's nothing to do Update::Error { err, .. } => return Err(Error::Update(err)), } @@ -924,13 +913,13 @@ self.data.cur_val ); } /// Return the aggregated primal of the given subproblem. - pub fn aggregated_primal(&self, subproblem: usize) -> Result { + pub fn aggregated_primal(&self, subproblem: usize) -> Result<::Primal, P, M> { Ok(self .master_proc .as_ref() .ok_or(Error::NotSolved)? .get_aggregated_primal(subproblem)?) } }