RsBundle  Check-in [abf6b6de39]

/*
 * Copyright (c) 2016-2021, 2023 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * 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

use env_logger;
use env_logger::fmt::Color;
use log::{info, Level};
use rustop::opts;
use std::io::Write;

use bundle::master::{Builder, FullMasterBuilder, MasterProblem, MinimalMasterBuilder};
use bundle::mcf::{self, MMCFConfig, MMCFProblem};
use bundle::solver::asyn::{GuessModelType, Parameters, Solver as AsyncSolver};
use bundle::solver::sync::Solver as SyncSolver;
use bundle::{terminator::StandardTerminator, weighter::HKWeighter};
use bundle::{DVector, Real};

use std::error::Error;
use std::result::Result;
use std::time::Duration;

type Minorant = (Real, DVector, DVector);

fn solve_parallel<M>(master: M, mmcf: MMCFProblem, params: Parameters) -> Result<(), Box<dyn Error>>
where
    M: Builder<Minorant>,
    M::MasterProblem: MasterProblem<Minorant>,

        opt bundle_size:usize = 0, name:"NUM", desc:"The bundle size";
        opt nearest_guess:bool, desc:"Use nearest guess model (default: cut-model)";
        opt descent_factor:Real = 0.5, name:"ρ", desc:"Descent parameter in (0,1)";
        opt imprecision_factor:Real = 0.9, name:"α", desc:"Imprecision parameter in (0,1)";
        opt l_guess_factor:Real = 0.1, name:"β", desc:"Lipschitz-guess increase factor in (0,1]";
        opt cpx:bool, desc:"Use Cplex as network flow solver";
        opt netspx:bool, desc:"Use network simplex implementation as network flow solver (default)";
        opt delayed_subs:Vec<usize> = vec![], desc:"0-based indices of delayed subproblems";
        opt delay:u64 = 0, desc:"Maximal delay in ms";
        param file:String, desc:"Input file in MNetGen format";
    }
    .parse_or_exit();

    let filename = args.file;
    info!("Reading instance: {}", filename);

    let mmcfcfg = MMCFConfig {
        separate_constraints: args.separate,
        delayed_subs: args.delayed_subs,
        delay: Duration::from_millis(args.delay),
        ..Default::default()
    };

    if !args.minimal {
        let mut mmcf = if args.netspx || !args.cpx {
            info!("Use rs-graph network simplex solver");
            MMCFProblem::read_mnetgen_with_solver::<mcf::NetSpxSolver>(&filename, mmcfcfg)?
        } else {
            info!("Use Cplex network simplex solver");
            MMCFProblem::read_mnetgen_with_solver::<mcf::CplexSolver>(&filename, mmcfcfg)?
        };
        mmcf.set_separate_constraints(args.separate);

        let mut master = FullMasterBuilder::default();
        if args.aggregated {
            master.max_bundle_size(if args.bundle_size <= 1 { 50 } else { args.bundle_size });
            master.use_full_aggregation();

            params.set_acceptance_factor(args.descent_factor);
            params.set_imprecision_factor(args.imprecision_factor);
            params.set_l_guess_factor(args.l_guess_factor);

            solve_parallel(master, mmcf, params)?;
        }
    } else {
        let mut mmcf = MMCFProblem::read_mnetgen(&filename, mmcfcfg)?;
        mmcf.set_separate_constraints(args.separate);

        let master = MinimalMasterBuilder::default();
        if args.sync {
            solve_sync(master, mmcf)?;
        } else {
            let mut params = Parameters::default();

// Copyright (c) 2016, 2021, 2023 Frank Fischer <frank-fischer@shadow-soft.de>
//
// 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

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

mod problem;
pub use crate::mcf::problem::{MMCFConfig, MMCFProblem};

// Copyright (c) 2016-2023 Frank Fischer <frank-fischer@shadow-soft.de>
//
// 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

use threadpool::ThreadPool;

use std::f64::INFINITY;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::result;
use std::sync::{Arc, RwLock};
use std::time::Duration;

/// An error in the mmcf file format.
#[derive(Debug, Error)]
#[non_exhaustive]
pub enum MMCFReadError {
    #[error("format error")]
    Format(#[source] Box<dyn std::error::Error>),

}

/// A single MMCF subproblem, i.e. one network.
struct Subproblem {
    /// The (net, cost) pair.
    net: Box<dyn mcf::Solver>,
    c: DVector,
    /// optional delay for evaluation
    delay: Option<Duration>,
}

/// Constraint data of one subproblem.
///
/// This information is used to create the augmented objective function, i.e.
/// cbase - lhs'* y as well as the constant term rhs' * y
struct SubData {
    /// The lhs of all constraints. For each constraint this is a list of coefficients.
    lhs: Vec<Vec<Elem>>,
    /// The right-hand side of each constraint
    rhs: DVector,
    /// The base costs of each arc
    cbase: DVector,
}

unsafe impl Send for Subproblem {}
unsafe impl Sync for Subproblem {}

/// Configuration options for MMCFProblem
pub struct MMCFConfig {
    /// If coupling constraints should be separated.
    pub separate_constraints: bool,
    /// A list of subproblems to be delayed.
    pub delayed_subs: Vec<usize>,
    /// Delay
    pub delay: Duration,
}

impl Default for MMCFConfig {
    fn default() -> MMCFConfig {
        MMCFConfig {
            separate_constraints: false,
            delayed_subs: vec![],
            delay: Duration::default(),
        }
    }
}

/// A single multi-commodity flow problem instance.
///
/// The current implementation always keeps a list of all potential
/// coupling constraints but, depending on the separation choice, the
/// may not be in the model. If separation is used a list of "active"
/// constraints is maintained holding the list of those constraints

            (-self.net.objective()?, dvec![0.0; y.len()])
        };

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

        if let Some(delay) = self.delay {
            std::thread::sleep(delay);
        }

        Ok((objective, subg, sol))
    }
}

impl SubData {
    fn evaluate_constraint(&self, primal: &DVector, cidx: usize) -> Real {

}

impl MMCFProblem {
    pub fn num_subproblems(&self) -> usize {
        self.subs.len()
    }

    pub fn read_mnetgen(basename: &str, config: MMCFConfig) -> std::result::Result<MMCFProblem, MMCFReadError> {
        MMCFProblem::read_mnetgen_with_solver::<mcf::NetSpxSolver>(basename, config)
    }

    pub fn read_mnetgen_with_solver<S>(
        basename: &str,
        config: MMCFConfig,
    ) -> std::result::Result<MMCFProblem, MMCFReadError>
    where
        S: Solver + 'static,
    {
        use MMCFReadError::*;

        let ncom;
        let nnodes;

            .zip(std::iter::once(rhs).chain(std::iter::repeat(dvec![])))
            .map(|((cbase, lhs), rhs)| SubData { lhs, rhs, cbase })
            .map(Arc::new)
            .collect();

        let subproblems = nets
            .into_iter()
            .enumerate()
            .map(|(i, net)| Subproblem {
                net: Box::new(net),
                c: dvec![],
                delay: if config.delayed_subs.contains(&i) {
                    Some(config.delay)
                } else {
                    None
                },
            })
            .map(RwLock::new)
            .map(Arc::new)
            .collect();

        let mut mcf = MMCFProblem {
            subs: subproblems,
            subdatas,
            active_constraints: Arc::new(RwLock::new((0..ncaps).collect())),
            inactive_constraints: Arc::new(RwLock::new(vec![])),
            pool: None,
        };
        mcf.set_separate_constraints(config.separate_constraints);
        Ok(mcf)
    }

    /// Set whether coupling constraints should be separated.
    ///
    /// If `separate` is true than all constraints will be made
    /// inactive, otherwise all constraints will be made active.
    pub fn set_separate_constraints(&mut self, separate: bool) {