RsBundle  Check-in [80cbe311ac]

//
// 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 crate::solver::UpdateState;
use crate::{Minorant, Real};

use std::result::Result;
use std::vec::IntoIter;

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

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

use crate::Real;
use crate::{BundleState, SolverParams, Step, Weighter};

use std::cmp::{max, min};
use std::f64::NEG_INFINITY;

const FACTOR: Real = 2.0;

/**

    ( $ ( $ x : expr , ) * ) => { DVector(vec![$($x,)*]) };
}

#[macro_use]
extern crate cplex_sys;

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

pub mod minorant;
pub use crate::minorant::Minorant;

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

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

mod hkweighter;
pub use crate::hkweighter::HKWeighter;

mod master;

pub mod mcf;

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

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

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

/// Error type for master problems.
#[derive(Debug)]

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

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

use super::Result;
use itertools::multizip;
use std::error::Error;
use std::f64::{EPSILON, INFINITY, NEG_INFINITY};
use std::result;

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

//! Master problem implementation using CPLEX.

#![allow(unused_unsafe)]

use crate::master::{Error as MasterProblemError, UnconstrainedMasterProblem};
use crate::{DVector, Minorant, Real};

use cplex_sys as cpx;

use super::Result;
use std;
use std::error::Error;
use std::f64::{self, NEG_INFINITY};

        // self.force_update = true;

        Ok(())
    }

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

        let nvars = unsafe { cpx::getnumcols(cpx::env(), self.lp) as usize };
        if nvars == 0 {
            return Err(MasterProblemError::NoMinorants);
        }
        // update linear costs

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use crate::master::{Error as MasterProblemError, UnconstrainedMasterProblem};
use crate::{DVector, Minorant, Real};

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

pub mod minimal;
pub use self::minimal::MinimalMaster;

// pub mod grb;
// pub use master::grb::GurobiMaster;

mod cpx;
pub use crate::master::cpx::CplexMaster;

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

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

use super::Result;

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

/**

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

//! Multi-commodity min-cost-flow subproblems.

mod solver;
pub use crate::mcf::solver::Solver;

mod problem;
pub use crate::mcf::problem::MMCFProblem;

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

use crate::mcf;
use crate::{DVector, FirstOrderProblem, Minorant, Real, SimpleEvaluation};

use std::error::Error;
use std::f64::INFINITY;
use std::fmt;
use std::fs::File;
use std::io::Read;
use std::result;

    c: Vec<DVector>,
}

impl MMCFProblem {
    pub fn read_mnetgen(basename: &str) -> Result<MMCFProblem> {
        let mut buffer = String::new();
        {
            let mut f = File::open(&format!("{}.nod", basename))?;
            f.read_to_string(&mut buffer)?;
        }
        let fnod = buffer
            .split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>();

        if fnod.len() != 4 {
            return Err(MMCFFormatError {
                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];

        // read nodes
        let mut nets = Vec::with_capacity(ncom);
        for _ in 0..ncom {
            nets.push(mcf::Solver::new(nnodes)?)
        }
        {
            let mut f = File::open(&format!("{}.sup", basename))?;
            buffer.clear();
            f.read_to_string(&mut buffer)?;
        }
        for line in buffer.lines() {
            let mut data = line.split_whitespace();
            let node = data.next().unwrap().parse::<usize>()?;
            let com = data.next().unwrap().parse::<usize>()?;
            let supply = data.next().unwrap().parse::<Real>()?;
            nets[com - 1].set_balance(node - 1, supply)?;
        }

        // read arcs
        let mut arcmap = vec![vec![]; ncom];
        let mut cbase = vec![dvec![]; ncom];

        // lhs nonzeros
        let mut lhsidx = vec![vec![vec![]; ncom]; ncaps];
        {
            let mut f = File::open(&format!("{}.arc", basename))?;
            buffer.clear();
            f.read_to_string(&mut buffer)?;
        }
        for line in buffer.lines() {
            let mut data = line.split_whitespace();
            let arc = data.next().unwrap().parse::<usize>()? - 1;
            let src = data.next().unwrap().parse::<usize>()? - 1;
            let snk = data.next().unwrap().parse::<usize>()? - 1;
            let com = data.next().unwrap().parse::<usize>()? - 1;
            let cost = data.next().unwrap().parse::<Real>()?;
            let cap = data.next().unwrap().parse::<Real>()?;
            let mt = data.next().unwrap().parse::<isize>()? - 1;
            assert!(
                arc < narcs,
                format!("Wrong arc number (got: {}, expected in 1..{})", arc + 1, narcs)
            );
            // set internal coeff
            let coeff = arcmap[com].len();
            arcmap[com].push(ArcInfo {
                arc: arc + 1,
                src: src + 1,
                snk: snk + 1,
            });
            // add arc
            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);
            }
        }

        // read rhs of coupling constraints
        {
            let mut f = File::open(&format!("{}.mut", basename))?;
            buffer.clear();
            f.read_to_string(&mut buffer)?;
        }
        let mut rhs = dvec![0.0; ncaps];
        for line in buffer.lines() {
            let mut data = line.split_whitespace();
            let mt = data.next().unwrap().parse::<usize>()? - 1;
            let cap = data.next().unwrap().parse::<Real>()?;
            rhs[mt] = cap;
        }

        // set lhs
        let mut lhs = vec![vec![vec![]; ncom]; ncaps];
        for i in 0..ncaps {
            for fidx in 0..ncom {

        let mut aggr = primals[0]
            .1
            .iter()
            .map(|x| {
                let mut r = dvec![];
                r.scal(primals[0].0, x);
                r
            })
            .collect::<Vec<_>>();

        for &(alpha, primal) in &primals[1..] {
            for (j, x) in primal.iter().enumerate() {
                aggr[j].add_scaled(alpha, x);
            }
        }

                }
            }
        }

        debug!("y={:?}", y);
        for i in 0..self.nets.len() {
            debug!("c[{}]={}", i, self.c[i]);
            self.nets[i].set_objective(&self.c[i])?;
        }

        // solve subproblems
        for (i, net) in self.nets.iter_mut().enumerate() {
            net.solve()?;
            debug!("c[{}]={}", i, net.objective()?);
        }

        // compute minorant
        if self.multimodel {
            let objective;
            let mut subg;
            if fidx == 0 {
                subg = self.rhs.clone();
                objective = self.rhsval - self.nets[fidx].objective()?;
            } else {
                subg = dvec![0.0; self.rhs.len()];
                objective = -self.nets[fidx].objective()?;
            }

            let sol = self.nets[fidx].get_solution()?;
            for (i, lhs) in self.lhs.iter().enumerate() {
                subg[i] -= lhs[fidx].iter().map(|elem| elem.val * sol[elem.ind]).sum::<Real>();
            }

            Ok(SimpleEvaluation {
                objective,
                minorants: vec![(
                    Minorant {
                        constant: objective,
                        linear: subg,
                    },
                    vec![sol],
                )],
            })
        } else {
            let mut objective = self.rhsval;
            let mut sols = Vec::with_capacity(self.nets.len());
            for i in 0..self.nets.len() {
                objective -= self.nets[i].objective()?;
                sols.push(self.nets[i].get_solution()?);
            }

            let mut subg = self.rhs.clone();
            for (i, lhs) in self.lhs.iter().enumerate() {
                for (fidx, flhs) in lhs.iter().enumerate() {
                    subg[i] -= flhs.iter().map(|elem| elem.val * sols[fidx][elem.ind]).sum::<Real>();
                }

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

#![allow(unused_unsafe)]

use crate::{DVector, Real};

use cplex_sys as cpx;

use std;
use std::error::Error;
use std::ffi::CString;
use std::ptr;

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

//! A linear minorant.

use crate::{DVector, Real};

use std::fmt;

/**
 * A linear minorant of a convex function.
 *
 * A linear minorant of a convex function $f \colon \mathbb{R}\^n \to

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

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 {

//
// 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 crate::{DVector, Real};
use crate::{Evaluation, FirstOrderProblem, HKWeighter, Update};

use crate::master::{BoxedMasterProblem, Error as MasterProblemError, MasterProblem, UnconstrainedMasterProblem};
use crate::master::{CplexMaster, MinimalMaster};

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

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

//! Finite-dimensional sparse and dense vectors.

use crate::Real;
use std::fmt;
use std::ops::{Deref, DerefMut};

// use std::cmp::min;
use std::iter::FromIterator;
use std::vec::IntoIter;

/// Type of dense vectors.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct DVector(pub Vec<Real>);

    fn deref_mut(&mut self) -> &mut Vec<Real> {
        &mut self.0
    }
}

impl fmt::Display for DVector {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "(")?;
        for (i, x) in self.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}", x)?
        }
        write!(f, ")")?;
        Ok(())
    }
}

impl FromIterator<Real> for DVector {
    fn from_iter<I: IntoIterator<Item = Real>>(iter: I) -> Self {
        DVector(Vec::from_iter(iter))

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();
                write!(f, "{}:(", size)?;
                if let Some(&(i, x)) = it.next() {
                    write!(f, "{}:{}", i, x)?;
                    for &(i, x) in it {
                        write!(f, ", {}:{}", i, x)?;
                    }
                }
                write!(f, ")")
            }
        }
    }
}