RsBundle  Check-in [1318918860]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Make `aggregate_primals` take ownership of minorants. This makes sure the problem can track exactly when minorants are not used anymore.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 131891886089422a45aa5e0987c4c1cc95f51058
User & Date: fifr 2016-10-01 20:44:09.344
Context
2016-10-02
07:02
mcf: Verify arc numbers when reading files. check-in: d98bdda26e user: fifr tags: trunk
2016-10-01
20:44
Make `aggregate_primals` take ownership of minorants. check-in: 1318918860 user: fifr tags: trunk
20:03
Implement computation of aggregated primals. check-in: 39420cd8e3 user: fifr tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to examples/mmcf.rs.
43
44
45
46
47
48
49
50

51
52
53
54
55
56
57
        }).unwrap();
        solver.terminator = Box::new(StandardTerminator{
            termination_precision: 1e-6
        });
        solver.solve().unwrap();

        let costs : f64 = (0..solver.problem().num_subproblems()).map(|i| {
            let primals = solver.aggregated_primals(i);

            solver.problem().get_primal_costs(i, &primals)
        }).sum();
        info!("Primal costs: {}", costs);
    } else {
        panic!("Usage: {} FILENAME", program);
    }
}







|
>
|






43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
        }).unwrap();
        solver.terminator = Box::new(StandardTerminator{
            termination_precision: 1e-6
        });
        solver.solve().unwrap();

        let costs : f64 = (0..solver.problem().num_subproblems()).map(|i| {
            let (coeffs, primals) : (Vec<_>, Vec<_>) = solver.aggregated_primals(i).into_iter().unzip();
            let aggr_primals = solver.problem().aggregate_primals_ref(&coeffs, &primals);
            solver.problem().get_primal_costs(i, &aggr_primals)
        }).sum();
        info!("Primal costs: {}", costs);
    } else {
        panic!("Usage: {} FILENAME", program);
    }
}
Changes to examples/quadratic.rs.
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
                (Minorant {
                    constant: objective,
                    linear: g,
                },())
            ],
        })
    }

    #[allow(unused_variables)]
    fn aggregate_primals(&mut self, coeffs: &[Real], primals: &[&Self::Primal]) -> Self::Primal {
        ()
    }
}

fn main() {
    env_logger::init().unwrap();

    let f = QuadraticProblem::new();
    let mut solver = Solver::new_params(f, SolverParams {







<
<
<
<
<







72
73
74
75
76
77
78





79
80
81
82
83
84
85
                (Minorant {
                    constant: objective,
                    linear: g,
                },())
            ],
        })
    }





}

fn main() {
    env_logger::init().unwrap();

    let f = QuadraticProblem::new();
    let mut solver = Solver::new_params(f, SolverParams {
Changes to src/firstorderproblem.rs.
137
138
139
140
141
142
143
144



145
    ///
    /// The function must return the new aggregated primal.
    ///
    /// The default implementation does nothing and simply returns the
    /// last primal. This should work if the implementing problem does
    /// not provide primal information, e.g. if `Self::Primal = ()`.
    #[allow(unused_variables)]
    fn aggregate_primals(&mut self, coeffs: &[Real], primals: &[&Self::Primal]) -> Self::Primal;



}







|
>
>
>

137
138
139
140
141
142
143
144
145
146
147
148
    ///
    /// The function must return the new aggregated primal.
    ///
    /// The default implementation does nothing and simply returns the
    /// last primal. This should work if the implementing problem does
    /// not provide primal information, e.g. if `Self::Primal = ()`.
    #[allow(unused_variables)]
    fn aggregate_primals(&mut self, coeffs: &[Real], primals: Vec<Self::Primal>) -> Self::Primal {
        let mut primals = primals;
        primals.pop().unwrap()
    }
}
Changes to src/mcf/problem.rs.
182
183
184
185
186
187
188

















189
190
191
192
193
194
195
                for (i, x) in p.iter().enumerate() {
                    sum += x * self.cbase[fidx][i];
                }
            }
            sum
        }
    }

















}

impl<'a> FirstOrderProblem<'a> for MMCFProblem {
    type Error = Error;

    type Primal = Vec<DVector>;








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
                for (i, x) in p.iter().enumerate() {
                    sum += x * self.cbase[fidx][i];
                }
            }
            sum
        }
    }

    /// Aggregate primal vectors.
    pub fn aggregate_primals_ref(&self, coeffs: &[Real], primals: &[&Vec<DVector>]) -> Vec<DVector> {
        let mut aggr = primals[0].iter().map(|x| {
            let mut r = dvec![];
            r.scal(coeffs[0], x);
            r
        }).collect::<Vec<_>>();

        for i in 1..primals.len() {
            for (j,x) in primals[i].iter().enumerate() {
                aggr[j].add_scaled(coeffs[i], x);
            }
        }

        aggr
    }
}

impl<'a> FirstOrderProblem<'a> for MMCFProblem {
    type Error = Error;

    type Primal = Vec<DVector>;

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
            Ok(SimpleEvaluation {
                objective: objective,
                minorants: vec![(Minorant { constant: objective, linear: subg }, sols)],
            })
        }
    }

    fn aggregate_primals(&mut self, coeffs: &[Real], primals: &[&Vec<DVector>]) -> Vec<DVector> {
        let mut aggr = primals[0].iter().map(|x| {
            let mut r = dvec![];
            r.scal(coeffs[0], x);
            r
        }).collect::<Vec<_>>();

        for i in 1..primals.len() {
            for (j,x) in primals[i].iter().enumerate() {
                aggr[j].add_scaled(coeffs[i], x);
            }
        }

        aggr
    }
}







|
<
<
<
<
|
|
<
<
<
|
<
<
<
<
<
301
302
303
304
305
306
307
308




309
310



311





            Ok(SimpleEvaluation {
                objective: objective,
                minorants: vec![(Minorant { constant: objective, linear: subg }, sols)],
            })
        }
    }

    fn aggregate_primals(&mut self, coeffs: &[Real], primals: Vec<Vec<DVector>>) -> Vec<DVector> {




        self.aggregate_primals_ref(coeffs, &primals.iter().map(|x| x).collect::<Vec<_>>())
    }



}





Changes to src/solver.rs.
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509

    /// Return the current aggregated primal information for a subproblem.
    ///
    /// This function returns all currently used minorants $x_i$ along
    /// with their coefficients $\alpha_i$. The aggregated primal can
    /// be computed by combining the minorants $\bar{x} =
    /// \sum_{i=1}\^m \alpha_i x_i$.
    pub fn aggregated_primals(&mut self, subproblem : usize) -> Pr {
        let (coeffs, primals) : (Vec<_>, Vec<_>) = self.minorants[subproblem].iter().map(|m| {
            (m.multiplier, m.primal.as_ref().unwrap())
        }).unzip();
        self.problem.aggregate_primals(&coeffs, &primals)
    }

    fn show_info(&self, step: Step) {
        let time = self.start_time.elapsed();
        info!("{} {:0>2}:{:0>2}:{:0>2}.{:0>2} {:4} {:4} {:4}{:1}  {:9.4} {:9.4} {:12.6e}({:12.6e}) {:12.6e}",
              if step == Step::Term { "_endit" } else { "endit " },
              time.as_secs() / 3600,







|
|

|
<







491
492
493
494
495
496
497
498
499
500
501

502
503
504
505
506
507
508

    /// Return the current aggregated primal information for a subproblem.
    ///
    /// This function returns all currently used minorants $x_i$ along
    /// with their coefficients $\alpha_i$. The aggregated primal can
    /// be computed by combining the minorants $\bar{x} =
    /// \sum_{i=1}\^m \alpha_i x_i$.
    pub fn aggregated_primals(&self, subproblem : usize) -> Vec<(Real, &Pr)> {
        self.minorants[subproblem].iter().map(|m| {
            (m.multiplier, m.primal.as_ref().unwrap())
        }).collect()

    }

    fn show_info(&self, step: Step) {
        let time = self.start_time.elapsed();
        info!("{} {:0>2}:{:0>2}:{:0>2}.{:0>2} {:4} {:4} {:4}{:1}  {:9.4} {:9.4} {:12.6e}({:12.6e}) {:12.6e}",
              if step == Step::Term { "_endit" } else { "endit " },
              time.as_secs() / 3600,
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
            }
            let n = self.master.num_minorants(i);
            if n >= self.params.max_bundle_size {
                // aggregate minorants with smallest coefficients
                self.minorants[i].sort_by_key(|m| -((1e6 * m.multiplier) as isize));
                let aggr = self.minorants[i].split_off(self.params.max_bundle_size-2);
                let aggr_sum = aggr.iter().map(|m| m.multiplier).sum();
                let (aggr_mins, aggr_primals) : (Vec<_>, Vec<_>) = aggr.iter().map(|m| {
                    (m.index, m.primal.as_ref().unwrap())
                }).unzip();
                let (aggr_min, aggr_coeffs) = try!(self.master.aggregate(i, &aggr_mins));
                // append aggregated minorant
                self.minorants[i].push(MinorantInfo{
                    index: aggr_min,
                    multiplier: aggr_sum,
                    primal: Some(self.problem.aggregate_primals(&aggr_coeffs, &aggr_primals)),
                });
            }
        }
        Ok(())
    }

    /// Perform a descent step.







|
|






|







628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
            }
            let n = self.master.num_minorants(i);
            if n >= self.params.max_bundle_size {
                // aggregate minorants with smallest coefficients
                self.minorants[i].sort_by_key(|m| -((1e6 * m.multiplier) as isize));
                let aggr = self.minorants[i].split_off(self.params.max_bundle_size-2);
                let aggr_sum = aggr.iter().map(|m| m.multiplier).sum();
                let (aggr_mins, aggr_primals) : (Vec<_>, Vec<_>) = aggr.into_iter().map(|m| {
                    (m.index, m.primal.unwrap())
                }).unzip();
                let (aggr_min, aggr_coeffs) = try!(self.master.aggregate(i, &aggr_mins));
                // append aggregated minorant
                self.minorants[i].push(MinorantInfo{
                    index: aggr_min,
                    multiplier: aggr_sum,
                    primal: Some(self.problem.aggregate_primals(&aggr_coeffs, aggr_primals)),
                });
            }
        }
        Ok(())
    }

    /// Perform a descent step.