1687a9c05b0c
problem.rs
use super::lp::{Row, Sense};
use super::model::{Model, Rel, Rhs};
use super::{CellRef, Trial, Value};
/// The values the solvers see at a point: the objective and `lhs − rhs` per row.
#[derive(Clone, Debug)]
pub(super) struct Point {
pub(super) f: f64,
pub(super) g: Vec<f64>,
}
pub(super) struct Evaluator {
pub(super) trial: Trial,
pub(super) sheet: usize,
pub(super) vars: Vec<CellRef>,
pub(super) objective: CellRef,
pub(super) rows: Vec<Row>,
pub(super) evals: u64,
pub(super) budget: u64,
/// The Limits report: the objective is this variable itself.
pub(super) target: Option<usize>,
}
pub(super) fn as_num(v: &Value) -> f64 {
match v {
Value::Number(n) => *n,
Value::Empty => 0.0,
Value::Bool(b) => f64::from(u8::from(*b)),
_ => f64::NAN,
}
}
impl Evaluator {
pub(super) fn exhausted(&self) -> bool {
self.evals >= self.budget
}
/// Evaluates the model at `x`; `None` once the budget is spent.
pub(super) fn eval(&mut self, x: &[f64]) -> Option<Point> {
if self.exhausted() {
return None;
}
self.evals += 1;
let sets: Vec<(usize, CellRef, Value)> = self.vars.iter().zip(x).map(|(c, v)| (self.sheet, *c, Value::number(*v))).collect();
let mut reads = Vec::with_capacity(1 + 2 * self.rows.len());
reads.push((self.sheet, self.objective));
for r in &self.rows {
reads.push((self.sheet, r.lhs));
if let Some(c) = r.rhs {
reads.push((self.sheet, c));
}
}
let vals = self.trial.run(&sets, &reads);
let mut it = vals.iter().map(as_num);
let f = it.next().unwrap_or(f64::NAN);
let f = match self.target {
Some(j) => x.get(j).copied().unwrap_or(f64::NAN),
None => f,
};
let mut g = Vec::with_capacity(self.rows.len());
for r in &self.rows {
let l = it.next().unwrap_or(f64::NAN);
let rv = if r.rhs.is_some() { it.next().unwrap_or(f64::NAN) } else { r.rhs_const };
g.push(l - rv);
}
Some(Point { f, g })
}
}
// ---------------------------------------------------------------- problem
pub(super) struct Problem {
pub(super) lo: Vec<f64>,
pub(super) hi: Vec<f64>,
pub(super) integer: Vec<bool>,
pub(super) rows: Vec<Row>,
}
/// Splits the constraints into variable bounds and general rows.
pub(super) fn build_problem(m: &Model) -> Problem {
let n = m.vars.len();
let mut lo = vec![f64::NEG_INFINITY; n];
let mut hi = vec![f64::INFINITY; n];
let mut has_lower = vec![false; n];
let mut integer = vec![false; n];
let mut rows = Vec::new();
let var_index = |c: &CellRef| m.vars.iter().position(|v| v == c);
for c in &m.cons {
for (k, cell) in c.lhs.iter().enumerate() {
let j = var_index(cell);
match c.rel {
Rel::Int | Rel::Bin => {
if let Some(j) = j {
if let Some(b) = integer.get_mut(j) {
*b = true;
}
if c.rel == Rel::Bin
&& let (Some(l), Some(h), Some(hl)) = (lo.get_mut(j), hi.get_mut(j), has_lower.get_mut(j))
{
*l = l.max(0.0);
*h = h.min(1.0);
*hl = true;
}
}
}
rel => {
let sense = match rel {
Rel::Le => Sense::Le,
Rel::Ge => Sense::Ge,
_ => Sense::Eq,
};
let (rhs, rhs_const) = match &c.rhs {
Rhs::Const(v) => (None, *v),
Rhs::Cells(cells) => (cells.get(k).or_else(|| cells.first()).copied(), 0.0),
Rhs::None => (None, 0.0),
};
match (j, rhs) {
// A constant bound on a variable cell is a box bound.
(Some(j), None) => {
if let (Some(l), Some(h), Some(hl)) = (lo.get_mut(j), hi.get_mut(j), has_lower.get_mut(j)) {
if sense != Sense::Ge {
*h = h.min(rhs_const);
}
if sense != Sense::Le {
*l = l.max(rhs_const);
*hl = true;
}
}
}
_ => rows.push(Row { lhs: *cell, sense, rhs, rhs_const }),
}
}
}
}
}
if m.non_negative {
for (l, hl) in lo.iter_mut().zip(&has_lower) {
if !hl {
*l = l.max(0.0);
}
}
}
Problem { lo, hi, integer, rows }
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.