generic_bnp/
lib.rs

1#![warn(warnings)]
2#![warn(clippy::all, clippy::pedantic)]
3#![allow(non_upper_case_globals)]
4#![allow(clippy::needless_return)]
5#![allow(clippy::items_after_statements)]
6#![allow(unused_variables, unused_imports, dead_code)]
7
8pub mod misc;
9mod generic_master_problem;
10mod ui;
11pub mod solvers;
12
13use std::fmt::Debug;
14use std::marker::PhantomData;
15use std::sync::Arc;
16use std::thread;
17pub use generic_master_problem::*;
18
19pub use ui::*;
20use crate::branch::{Branch, BranchComparator};
21use crate::column_pool::{ColumnId, ColumnPool, ColumnPoolFilter};
22use crate::misc::blocking_queue::BlockingQueue;
23
24
25pub trait BnPFactory<Type, ProblemInstance> {
26    fn new(&self, instance : &ProblemInstance) -> Type;
27}
28
29pub struct BranchAndPrice<BranchFilter: IBranchFilter, Column : PartialEq + 'static, DualStore : UserDualStore + Sync,  ModelMeta : UserModelMeta<Constr,Var,Env,Model>,
30    BranchGroupType : Clone + Debug + Send + Sync, Constr : Clone, Env : LPEnv,Model : LPModel<Constr,Var,Env>,Var : Clone,
31    PricingSolver : UserPricingSolver<ProblemInstance, BranchFilter, Column, DualStore> ,
32    ProblemInstance : Clone + Send + Sync,
33    UMasterProblem : UserMasterProblem<ProblemInstance, PricingSolver, Column, DualStore, ModelMeta, BranchFilter, BranchGroupType, Constr,Env,Model,Var> + Clone,
34>
35where ColumnPool<Column, BranchFilter> : ColumnPoolFilter<Column, BranchFilter>{
36
37    _b : PhantomData<BranchFilter>,
38    _c : PhantomData<Column>,
39    _bpt: PhantomData<BranchGroupType>,
40    _mm: PhantomData<ModelMeta>,
41    _ds: PhantomData<DualStore>,
42    _cs: PhantomData<Constr>,
43    _ev: PhantomData<Env>,
44    _md: PhantomData<Model>,
45    _vr: PhantomData<Var>,
46    _pi: PhantomData<ProblemInstance>,
47    _ps : PhantomData<PricingSolver>,
48    _mp : PhantomData<UMasterProblem>,
49
50
51    problem_instance : ProblemInstance,
52}
53
54impl<BranchFilter: IBranchFilter + Sync + Send, Column : PartialEq + 'static + Clone + Send + Sync, DualStore : UserDualStore + Sync + Send,  ModelMeta : UserModelMeta<Constr,Var,Env,Model>,
55    BranchGroupType : Clone + Debug + Send + Sync, Constr : Clone, Env : LPEnv,Model : LPModel<Constr,Var,Env>,Var : Clone,
56    PricingSolver : UserPricingSolver<ProblemInstance, BranchFilter, Column, DualStore>,
57    ProblemInstance: Clone + Send + Sync,
58    UMasterProblem : UserMasterProblem<ProblemInstance,PricingSolver, Column, DualStore, ModelMeta, BranchFilter, BranchGroupType, Constr,Env,Model,Var> + Clone + Send + Sync,
59> BranchAndPrice<BranchFilter, Column, DualStore, ModelMeta, BranchGroupType, Constr, Env, Model, Var, PricingSolver, ProblemInstance, UMasterProblem> where ColumnPool<Column, BranchFilter> : ColumnPoolFilter<Column, BranchFilter>{
60    
61    
62    pub fn new(   problem_instance : ProblemInstance) -> Self {
63        
64        BranchAndPrice {
65            _b: PhantomData,
66            _c: PhantomData,
67            _bpt: PhantomData,
68            _mm: PhantomData,
69            _ds: PhantomData,
70            _cs: PhantomData,
71            _ev: PhantomData,
72            _md: PhantomData,
73            _vr: PhantomData,
74            _pi : PhantomData,
75            _ps: PhantomData,
76            _mp: PhantomData,
77
78            problem_instance
79        }
80    }
81
82
83    pub fn solve(&self, ui : &UI, num_threads : usize, column_pool : ColumnPool<Column, BranchFilter>) -> (f64, Vec<(f64, Column)>) {
84
85        let open_branches = BlockingQueue::new(
86            BranchComparator::with_bound(),
87            BranchComparator::without_bound()
88        );
89
90
91
92        let shared = Arc::new(SharedState::new(column_pool, &ui, None, open_branches));
93
94
95
96
97
98
99        // start with phase main
100        {
101            *shared.phase.write().unwrap() = Phase::PrimalHeuristic;
102        }
103        shared
104            .open_branches
105            .add_job(Branch::create_lds_root());
106
107
108        shared.ui_sender.send(UIUserMessage::StartPhase("Primal Heuristic", 0));
109        // run main
110        thread::scope(|s| {
111            for i in 0..num_threads {
112                let shared = shared.clone();
113
114                let pi = self.problem_instance.clone();
115                s.spawn(move || {
116                    let mp  = UMasterProblem::new(&pi, shared.ui_sender.clone());
117                    let ps = PricingSolver::new(&pi, shared.ui_sender.clone());
118                    let mut master_problem = MasterProblem::new(
119                        shared,
120                        mp, ps
121                    );
122                    master_problem.run_worker(0.0, f64::INFINITY, (0 + i) as i32);
123                });
124            }
125        });
126
127        // start with phase main
128        {
129            *shared.phase.write().unwrap() = Phase::Main;
130        }
131        shared
132            .open_branches
133            .add_job(Branch::default());
134
135        shared.ui_sender.send(UIUserMessage::StartPhase("Main Phase", 0));
136        thread::scope(|s| {
137            for i in 0..num_threads {
138                let shared = shared.clone();
139
140                let pi = self.problem_instance.clone();
141                s.spawn(move || {
142                    let mp  = UMasterProblem::new(&pi, shared.ui_sender.clone());
143                    let ps = PricingSolver::new(&pi, shared.ui_sender.clone());
144                    let mut master_problem = MasterProblem::new(
145                        shared,
146                        mp, ps
147                    );
148                    master_problem.run_worker(0.0, f64::INFINITY, (0 + i) as i32);
149                });
150            }
151        });
152
153        ui.get_sender().send(UIUserMessage::ExitUi {
154            root_node: shared.duration_root_node.lock().unwrap().clone(),
155            lds_root_node_duration: shared.duration_lds_root_node.lock().unwrap().clone(),
156        });
157
158
159        let (best,pattern) =  { shared.best.read().unwrap().to_owned() };
160
161
162        let columns: Vec<(f64, Column)> = pattern
163            .iter()
164            .filter(|(v, _)| *v > 0.0)
165            .map(|(v, c)| {
166                let c = shared
167                    .column_pool
168                    .read()
169                    .unwrap()
170                    .get_column(*c)
171                    .data
172                    .clone();
173                (*v,c)
174            })
175            .collect();
176
177
178        (best, columns)
179    }
180    
181    
182}
generic_bnp/lib.rs

generic_bnp/
lib.rs
