gurobi/
expr.rs

1// Copyright (c) 2016 Yusuke Sasaki
2//
3// This software is released under the MIT License.
4// See http://opensource.org/licenses/mit-license.php or <LICENSE>.
5
6use attr;
7use super::{Var, Model};
8use error::Result;
9use itertools::*;
10
11use std::ops::{Add, Sub, Mul, Neg, AddAssign, Div};
12use std::iter::Sum;
13
14/// Linear expression of variables
15///
16/// A linear expression consists of a constant term plus a list of coefficients and variables.
17#[derive(Debug, Clone, Default)]
18pub struct LinExpr {
19  vars: Vec<Var>,
20  coeff: Vec<f64>,
21  offset: f64
22}
23
24impl<'a> From<&'a Var> for LinExpr {
25    fn from(var : &Var) -> LinExpr {
26        LinExpr::new() + var
27    }
28}
29
30impl From<Var> for LinExpr {
31    fn from(var : Var) -> LinExpr {
32        LinExpr::from(&var)
33    }
34}
35
36impl From<f64> for LinExpr {
37  fn from(offset : f64) -> LinExpr {
38    LinExpr::new() + offset
39  }
40}
41
42impl Into<(Vec<i32>, Vec<f64>, f64)> for LinExpr {
43  fn into(self) -> (Vec<i32>, Vec<f64>, f64) {
44    (self.vars.into_iter().map(|e| e.index()).collect(), self.coeff, self.offset)
45  }
46}
47
48
49impl LinExpr {
50  /// Create an empty linear expression.
51  pub fn new() -> Self {
52    LinExpr::default()
53  }
54
55  /// Add a linear term into the expression.
56  pub fn add_term(mut self, coeff: f64, var: Var) -> Self {
57    self.coeff.push(coeff);
58    self.vars.push(var);
59    self
60  }
61
62  /// Add linear terms into the expression. Panics if the lengths do not match.
63  pub fn add_terms(mut self, coeffs: &[f64], vars: &[Var]) -> Self {
64    assert_eq!(coeffs.len(), vars.len());
65    self.coeff.extend_from_slice(coeffs);
66    self.vars.extend_from_slice(vars);
67    self
68  }
69
70  /// Add a constant into the expression.
71  pub fn add_constant(mut self, constant: f64) -> Self {
72    self.offset += constant;
73    self
74  }
75
76  /// Get actual value of the expression.
77  pub fn get_value(&self, model: &Model) -> Result<f64> {
78    let vars = try!(model.get_values(attr::X, self.vars.as_slice()));
79
80    Ok(Zip::new((vars, self.coeff.iter())).fold(0.0, |acc, (ind, val)| acc + ind * val) + self.offset)
81  }
82}
83
84
85/// Quadratic expression of variables
86///
87/// A quadratic expression consists of a linear expression and a set of
88/// variable-variable-coefficient triples to express the quadratic term.
89#[derive(Debug, Clone, Default)]
90pub struct QuadExpr {
91  lind: Vec<Var>,
92  lval: Vec<f64>,
93  qrow: Vec<Var>,
94  qcol: Vec<Var>,
95  qval: Vec<f64>,
96  offset: f64
97}
98
99impl Into<(Vec<i32>, Vec<f64>, Vec<i32>, Vec<i32>, Vec<f64>, f64)> for QuadExpr {
100  fn into(self) -> (Vec<i32>, Vec<f64>, Vec<i32>, Vec<i32>, Vec<f64>, f64) {
101    (self.lind.into_iter().map(|e| e.index()).collect(),
102     self.lval,
103     self.qrow.into_iter().map(|e| e.index()).collect(),
104     self.qcol.into_iter().map(|e| e.index()).collect(),
105     self.qval,
106     self.offset)
107  }
108}
109
110impl QuadExpr {
111  pub fn new() -> Self {
112    QuadExpr::default()
113  }
114
115  /// Add a linear term into the expression.
116  pub fn add_term(mut self, coeff: f64, var: Var) -> Self {
117    self.lind.push(var);
118    self.lval.push(coeff);
119    self
120  }
121
122  /// Add a quadratic term into the expression.
123  pub fn add_qterm(mut self, coeff: f64, row: Var, col: Var) -> Self {
124    self.qval.push(coeff);
125    self.qrow.push(row);
126    self.qcol.push(col);
127    self
128  }
129
130  /// Add a constant into the expression.
131  pub fn add_constant(mut self, constant: f64) -> Self {
132    self.offset += constant;
133    self
134  }
135
136  /// Get actual value of the expression.
137  pub fn get_value(&self, model: &Model) -> Result<f64> {
138    let lind = try!(model.get_values(attr::X, self.lind.as_slice()));
139    let qrow = try!(model.get_values(attr::X, self.qrow.as_slice()));
140    let qcol = try!(model.get_values(attr::X, self.qcol.as_slice()));
141
142    Ok(Zip::new((lind, self.lval.iter())).fold(0.0, |acc, (ind, val)| acc + ind * val) +
143       Zip::new((qrow, qcol, self.qval.iter())).fold(0.0, |acc, (row, col, val)| acc + row * col * val) +
144       self.offset)
145  }
146}
147
148// Conversion into QuadExpr
149
150impl Into<QuadExpr> for Var {
151  fn into(self) -> QuadExpr { QuadExpr::new().add_term(1.0, self) }
152}
153
154impl<'a> Into<QuadExpr> for &'a Var {
155  fn into(self) -> QuadExpr { QuadExpr::new().add_term(1.0, self.clone()) }
156}
157
158impl Into<QuadExpr> for LinExpr {
159  fn into(self) -> QuadExpr {
160    QuadExpr {
161      lind: self.vars,
162      lval: self.coeff,
163      offset: self.offset,
164      qrow: Vec::new(),
165      qcol: Vec::new(),
166      qval: Vec::new()
167    }
168  }
169}
170
171
172// /////// Operator definition.
173
174
175/// `Var` + `Var`  => `LinExpr`
176impl Add for Var {
177  type Output = LinExpr;
178  fn add(self, rhs: Var) -> LinExpr { LinExpr::new().add_term(1.0, self).add_term(1.0, rhs) }
179}
180impl<'a> Add<&'a Var> for Var {
181  type Output = LinExpr;
182  fn add(self, rhs: &Var) -> LinExpr { LinExpr::new().add_term(1.0, self).add_term(1.0, rhs.clone()) }
183}
184impl<'a> Add<Var> for &'a Var {
185  type Output = LinExpr;
186  fn add(self, rhs: Var) -> LinExpr { LinExpr::new().add_term(1.0, self.clone()).add_term(1.0, rhs) }
187}
188impl<'a, 'b> Add<&'b Var> for &'a Var {
189  type Output = LinExpr;
190  fn add(self, rhs: &Var) -> LinExpr { LinExpr::new().add_term(1.0, self.clone()).add_term(1.0, rhs.clone()) }
191}
192impl Add<f64> for Var {
193  type Output = LinExpr;
194  fn add(self, rhs: f64) -> LinExpr { LinExpr::new() + self + rhs }
195}
196impl<'a> Add<f64> for &'a Var {
197  type Output = LinExpr;
198  fn add(self, rhs: f64) -> LinExpr { LinExpr::new() + self.clone() + rhs }
199}
200
201/// `Var` - `Var` => `LinExpr`
202impl Sub for Var {
203  type Output = LinExpr;
204  fn sub(self, rhs: Var) -> LinExpr { LinExpr::new().add_term(1.0, self).add_term(-1.0, rhs) }
205}
206impl<'a> Sub<&'a Var> for Var {
207  type Output = LinExpr;
208  fn sub(self, rhs: &Var) -> LinExpr { LinExpr::new().add_term(1.0, self).add_term(-1.0, rhs.clone()) }
209}
210impl<'a> Sub<Var> for &'a Var {
211  type Output = LinExpr;
212  fn sub(self, rhs: Var) -> LinExpr { LinExpr::new().add_term(1.0, self.clone()).add_term(-1.0, rhs) }
213}
214impl<'a, 'b> Sub<&'b Var> for &'a Var {
215  type Output = LinExpr;
216  fn sub(self, rhs: &Var) -> LinExpr { LinExpr::new().add_term(1.0, self.clone()).add_term(-1.0, rhs.clone()) }
217}
218impl Sub<LinExpr> for Var {
219  type Output = LinExpr;
220  fn sub(self, expr: LinExpr) -> LinExpr {  self + (-expr) }
221}
222impl<'a> Sub<LinExpr> for &'a Var {
223  type Output = LinExpr;
224  fn sub(self, expr: LinExpr) -> LinExpr {  self.clone() + (-expr) }
225}
226impl Sub<Var> for f64 {
227  type Output = LinExpr;
228  fn sub(self, rhs: Var) -> LinExpr { LinExpr::new() + self + (-rhs) }
229}
230impl<'a> Sub<&'a Var> for f64 {
231  type Output = LinExpr;
232  fn sub(self, rhs: &Var) -> LinExpr { LinExpr::new() + self + (-rhs.clone()) }
233}
234
235
236/// -`Var` => `LinExpr`
237impl Neg for Var {
238  type Output = LinExpr;
239  fn neg(self) -> LinExpr { LinExpr::new().add_term(-1.0, self) }
240}
241impl<'a> Neg for &'a Var {
242  type Output = LinExpr;
243  fn neg(self) -> LinExpr { LinExpr::new().add_term(-1.0, self.clone()) }
244}
245
246
247
248/// `Var` * `f64` => `LinExpr`
249impl Mul<f64> for Var {
250  type Output = LinExpr;
251  fn mul(self, rhs: f64) -> Self::Output { LinExpr::new().add_term(rhs, self) }
252}
253impl<'a> Mul<f64> for &'a Var {
254  type Output = LinExpr;
255  fn mul(self, rhs: f64) -> Self::Output { LinExpr::new().add_term(rhs, self.clone()) }
256}
257impl Mul<Var> for f64 {
258  type Output = LinExpr;
259  fn mul(self, rhs: Var) -> Self::Output { LinExpr::new().add_term(self, rhs) }
260}
261impl<'a> Mul<&'a Var> for f64 {
262  type Output = LinExpr;
263  fn mul(self, rhs: &'a Var) -> Self::Output { LinExpr::new().add_term(self, rhs.clone()) }
264}
265
266
267/// `Var` * `Var` => `QuadExpr`
268impl Mul for Var {
269  type Output = QuadExpr;
270  fn mul(self, rhs: Var) -> Self::Output { QuadExpr::new().add_qterm(1.0, self, rhs) }
271}
272impl<'a> Mul<&'a Var> for Var {
273  type Output = QuadExpr;
274  fn mul(self, rhs: &Var) -> Self::Output { QuadExpr::new().add_qterm(1.0, self, rhs.clone()) }
275}
276impl<'a> Mul<Var> for &'a Var {
277  type Output = QuadExpr;
278  fn mul(self, rhs: Var) -> Self::Output { QuadExpr::new().add_qterm(1.0, self.clone(), rhs) }
279}
280impl<'a, 'b> Mul<&'b Var> for &'a Var {
281  type Output = QuadExpr;
282  fn mul(self, rhs: &Var) -> Self::Output { QuadExpr::new().add_qterm(1.0, self.clone(), rhs.clone()) }
283}
284
285
286/// `LinExpr` + `Var` => `LinExpr`
287impl Add<LinExpr> for Var {
288  type Output = LinExpr;
289  fn add(self, rhs: LinExpr) -> LinExpr { rhs.add_term(1.0, self) }
290}
291impl<'a> Add<LinExpr> for &'a Var {
292  type Output = LinExpr;
293  fn add(self, rhs: LinExpr) -> LinExpr { rhs.add_term(1.0, self.clone()) }
294}
295impl Add<Var> for LinExpr {
296  type Output = LinExpr;
297  fn add(self, rhs: Var) -> LinExpr { self.add_term(1.0, rhs) }
298}
299impl<'a> Add<&'a Var> for LinExpr {
300  type Output = LinExpr;
301  fn add(self, rhs: &'a Var) -> LinExpr { self.add_term(1.0, rhs.clone()) }
302}
303
304
305/// `LinExpr` + `f64` => `LinExpr`
306impl Add<f64> for LinExpr {
307  type Output = LinExpr;
308  fn add(self, rhs: f64) -> Self::Output { self.add_constant(rhs) }
309}
310impl Add<LinExpr> for f64 {
311  type Output = LinExpr;
312  fn add(self, rhs: LinExpr) -> Self::Output { rhs.add_constant(self) }
313}
314
315
316/// `LinExpr` - `f64` => `LinExpr`
317impl Sub<f64> for LinExpr {
318  type Output = LinExpr;
319  fn sub(self, rhs: f64) -> Self::Output { self.add_constant(-rhs) }
320}
321
322/// `f64` - `LinExpr` => `LinExpr`
323impl Sub<LinExpr> for f64 {
324  type Output = LinExpr;
325  fn sub(self, mut rhs: LinExpr) -> Self::Output {
326    self + (-rhs)
327  }
328}
329
330
331impl Add for LinExpr {
332  type Output = LinExpr;
333  fn add(mut self, rhs: LinExpr) -> Self::Output {
334    self += rhs;
335    self
336  }
337}
338
339impl Neg for LinExpr {
340  type Output = LinExpr;
341  fn neg(mut self) -> LinExpr {
342      for coeff in &mut self.coeff {
343        *coeff = -*coeff;
344      }
345      self.offset = -self.offset;
346      self
347  }
348}
349
350impl AddAssign for LinExpr {
351    fn add_assign(&mut self, rhs: LinExpr) {
352      for (var, &coeff) in rhs.vars.into_iter().zip(rhs.coeff.iter()) {
353        if let Some(idx) = self.vars.iter().position(|v| *v == var) {
354          self.coeff[idx] += coeff;
355        } else {
356          self.vars.push(var);
357          self.coeff.push(coeff);
358        }
359      }
360      self.offset += rhs.offset;
361    }
362}
363
364impl AddAssign<Var> for LinExpr {
365    fn add_assign(&mut self, rhs: Var) {
366        let expr : LinExpr = rhs.into();
367        *self += expr;
368    }
369}
370
371impl Sub for LinExpr {
372  type Output = LinExpr;
373  fn sub(self, rhs: LinExpr) -> Self::Output {
374    self + (-rhs)
375  }
376}
377
378impl Mul<f64> for LinExpr {
379  type Output = LinExpr;
380  fn mul(mut self, rhs: f64) -> Self::Output {
381    for coeff in &mut self.coeff {
382      *coeff *= rhs;
383    }
384    self.offset *= rhs;
385    self
386  }
387}
388
389impl Div<f64> for LinExpr {
390  type Output = LinExpr;
391  fn div(mut self, rhs: f64) -> Self::Output {
392    for coeff in &mut self.coeff {
393      *coeff /= rhs;
394    }
395    self.offset /= rhs;
396    self
397  }
398}
399
400impl Mul<LinExpr> for f64 {
401  type Output = LinExpr;
402  fn mul(self, rhs: LinExpr) -> Self::Output {
403      rhs * self
404  }
405}
406
407impl Mul<f64> for QuadExpr {
408  type Output = QuadExpr;
409  fn mul(mut self, rhs: f64) -> Self::Output {
410    for i in 0..(self.lval.len()) {
411      self.lval[i] *= rhs;
412    }
413    for j in 0..(self.qval.len()) {
414      self.qval[j] *= rhs;
415    }
416    self.offset *= rhs;
417    self
418  }
419}
420
421impl Sum for LinExpr {
422    fn sum<I: Iterator<Item=LinExpr>>(iter: I) -> LinExpr {
423        iter.fold(LinExpr::new(), |acc, expr| acc + expr)
424    }
425}
426
427
428impl Add<LinExpr> for QuadExpr {
429  type Output = QuadExpr;
430  fn add(mut self, rhs: LinExpr) -> Self::Output {
431    self.lind.extend(rhs.vars);
432    self.lval.extend(rhs.coeff);
433    self.offset += rhs.offset;
434    self
435  }
436}
437
438impl Sub<LinExpr> for QuadExpr {
439  type Output = QuadExpr;
440  fn sub(mut self, rhs: LinExpr) -> Self::Output {
441    self.lind.extend(rhs.vars);
442    self.lval.extend(rhs.coeff.into_iter().map(|c| -c));
443    self.offset -= rhs.offset;
444    self
445  }
446}
447
448impl Add for QuadExpr {
449  type Output = QuadExpr;
450  fn add(mut self, rhs: QuadExpr) -> QuadExpr {
451    self.lind.extend(rhs.lind);
452    self.lval.extend(rhs.lval);
453    self.qrow.extend(rhs.qrow);
454    self.qcol.extend(rhs.qcol);
455    self.qval.extend(rhs.qval);
456    self.offset += rhs.offset;
457    self
458  }
459}
460
461impl Sub for QuadExpr {
462  type Output = QuadExpr;
463  fn sub(mut self, rhs: QuadExpr) -> QuadExpr {
464    self.lind.extend(rhs.lind);
465    self.lval.extend(rhs.lval.into_iter().map(|c| -c));
466    self.qrow.extend(rhs.qrow);
467    self.qcol.extend(rhs.qcol);
468    self.qval.extend(rhs.qval.into_iter().map(|c| -c));
469    self.offset -= rhs.offset;
470    self
471  }
472}
gurobi/expr.rs

gurobi/
expr.rs
