lpsolve/
lib.rs

1//! Wrapper for lpsolve
2//!
3//! ![Build status](https://gitlab.com/cmr/rust-lpsolve/badges/master/build.svg)
4//! [![Crates.io](https://img.shields.io/crates/v/lpsolve.svg)](https://crates.io/crates/lpsolve)
5//!
6//! lpsolve is a free software (LGPL) solver for mixed integer linear programming problems. The
7//! documentation here is nonexistent when it comes to understanding how to model systems or
8//! precisely what the consequences of various methods are.  The [upstream
9//! documentation](http://lpsolve.sourceforge.net/5.5/) for lpsolve is much more comprehensive.
10//!
11//! This wrapper is mostly straightforward.
12//!
13//! The performance of lpsolve is mediocre compared to commercial solvers and some other free
14//! software solvers. Performance here is how how long it takes to solve [benchmark
15//! models](http://plato.asu.edu/bench.html).
16//! 
17//! If you need help chosing a solver, the following is an excellent report:
18//!
19//! http://prod.sandia.gov/techlib/access-control.cgi/2013/138847.pdf
20//!
21//! # Boolean return values
22//!
23//! The boolean return values represent the underlying return value from lpsolve. `true` means
24//! success and `false` means some error occured. There is an error reporting API, although by
25//! default it logs to standard out, and is not yet wrapped.
26//!
27//! # Status
28//!
29//! This wrapper is not complete. In particular, none of the solver setting or debug functions are
30//! wrapped. Additionally, a few of the model building and solution extraction functions are not
31//! wrapped.
32//!
33//! This is not fundamental, merge requests welcome!
34//!
35//! # Stability
36//!
37//! `lpsolve-sys` is versioned separately from this wrapper. This wrapper is provisionally
38//! unstable, but the functions that are currently wrapped are not likely to change.
39//!
40//! # License
41//! 
42//! This crate and `lpsolve-sys` are licensed under either of
43//! 
44//!  * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
45//!  * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
46//! 
47//! at your option. However, please note that lpsolve itself is LGPL. The default configuration right
48//! now builds a bundled copy of lpsolve and links to it statically.
49
50
51extern crate lpsolve_sys as lp;
52extern crate libc;
53#[macro_use] extern crate bitflags;
54
55use std::mem::transmute;
56use std::io::Write;
57use std::ffi::CStr;
58use std::ops::Deref;
59
60#[repr(C)]
61#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
62pub enum Verbosity {
63    Critical = 1,
64    Severe = 2,
65    Important = 3,
66    Normal = 4,
67    Detailed = 5,
68    Full = 6,
69}
70
71#[repr(C)]
72#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
73pub enum ConstraintType {
74    Le = 1,
75    Eq = 3,
76    Ge = 2,
77    Free = 0,
78}
79
80#[repr(C)]
81#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
82pub enum SOSType {
83    Type1 = 1,
84    Type2 = 2,
85}
86
87#[repr(C)]
88#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
89pub enum VarType {
90    Binary = 1,
91    Float = 0,
92}
93
94#[repr(u8)]
95#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
96pub enum BoundsMode {
97    Restrictive = 1,
98    None = 0,
99}
100
101#[repr(C)]
102#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
103pub enum SolveStatus {
104    OutOfMemory = -2,
105    NotRun = -1,
106    Optimal = 0,
107    Suboptimal = 1,
108    Infeasible = 2,
109    Unbounded = 3,
110    Degenerate = 4,
111    NumericalFailure = 5,
112    UserAbort = 6,
113    Timeout = 7,
114    Presolved = 8,
115    ProcFail = 9,
116    ProcBreak = 11,
117    FeasibleFound = 12,
118    NoFeasibleFound = 13,
119}
120
121bitflags! {
122    pub flags MPSOptions: ::libc::c_int {
123        const CRITICAL = 1,
124        const SEVERE = 2,
125        const IMPORTANT = 3,
126        const NORMAL = 4,
127        const DETAILED = 5,
128        const FULL = 6,
129        const FREE = 8,
130        const IBM = 16,
131        const NEGOBJCONST = 32,
132    }
133}
134
135/// A linear programming problem.
136pub struct Problem {
137    lprec: *mut lp::lprec,
138}
139
140macro_rules! cptr {
141    ($e:expr) => { if $e.is_null() { None } else { Some(Problem { lprec: $e }) } }
142}
143
144unsafe extern "C" fn write_modeldata(val: *mut libc::c_void, buf: *mut libc::c_char) -> libc::c_int {
145    let val = transmute::<_, &mut &mut Write>(val);
146    let buf = CStr::from_ptr(buf);
147    match val.write(buf.to_bytes()) {
148        Ok(_) => 0,
149        Err(_) => 1,
150    }
151}
152
153impl Problem {
154    /// Initialize an empty problem with space for `rows` and `cols`.
155    pub fn new(rows: libc::c_int, cols: libc::c_int) -> Option<Problem> {
156        let ptr = unsafe { lp::make_lp(rows, cols) };
157        cptr!(ptr)
158    }
159
160    /// Reads an lp-format model from `path`.
161    pub fn read_lp<P: Deref<Target=CStr>, C: Deref<Target=CStr>>(path: &P, verbosity: Verbosity, initial_name: &C) -> Option<Problem> {
162        let ptr = unsafe { lp::read_LP(path.as_ptr() as *mut _, verbosity as libc::c_int, initial_name.as_ptr() as *mut _) };
163        cptr!(ptr)
164    }
165
166    /// Read an mps-format model from `path` using the "free" formatting.
167    pub fn read_freemps<P: Deref<Target=CStr>>(path: &P, options: MPSOptions) -> Option<Problem> {
168        let ptr = unsafe { lp::read_freeMPS(path.as_ptr() as *mut _, options.bits) };
169        cptr!(ptr)
170    }
171
172    /// Read an mps-format model from `path` using the fixed formatting.
173    pub fn read_fixedmps<P: Deref<Target=CStr>>(path: &P, options: MPSOptions) -> Option<Problem> {
174        let ptr = unsafe { lp::read_MPS(path.as_ptr() as *mut _, options.bits) };
175        cptr!(ptr)
176    }
177
178    /// Write an lp-format model into `out`.
179    ///
180    /// If there are any errors writing to `out`, `false` will be returned. Otherwise, `true`.
181    pub fn write_lp(&self, out: &mut Write) -> bool {
182        1 == unsafe { lp::write_lpex(self.lprec, transmute::<_, *mut libc::c_void>(&out), write_modeldata) }
183    }
184
185    /// Write an mps-format model into `out` using the fixed formatting.
186    ///
187    /// If there are any errors writing to `out`, `false` will be returned. Otherwise, `true`.
188    pub fn write_fixedmps(&self, out: &mut Write) -> bool {
189        self.write_mps(out, 1)
190    }
191
192    /// Write an mps-format model into `out` using the "free" formatting.
193    ///
194    /// If there are any errors writing to `out`, `false` will be returned. Otherwise, `true`.
195    pub fn write_freemps(&self, out: &mut Write) -> bool {
196        self.write_mps(out, 2)
197    }
198
199    /// Write an mps-format model into `out` using `formatting`.
200    ///
201    /// If there are any errors writing to `out`, `false` will be returned. Otherwise, `true`.
202    ///
203    /// `formatting` must be 1 for fixed or 2 for free.
204    pub fn write_mps(&self, out: &mut Write, formatting: libc::c_int) -> bool {
205        debug_assert!(formatting == 1 || formatting == 2);
206        1 == unsafe { lp::MPS_writefileex(self.lprec, formatting, transmute::<_, *mut libc::c_void>(&out), write_modeldata) }
207    }
208
209    /// Reserve enough memory for `rows` and `cols`.
210    ///
211    /// If `rows` or `cols` are less than the current number of rows or columns, the additional
212    /// rows and columns will be deleted.
213    ///
214    /// Returns `true` if successful.
215    pub fn resize(&mut self, rows: libc::c_int, cols: libc::c_int) -> bool {
216        1 == unsafe { lp::resize_lp(self.lprec, rows, cols) }
217    }
218
219    /// Add a column to the model.
220    ///
221    /// If `values` is empty, an all-zero column will be added.
222    ///
223    /// This will assert that `values` has at least as many elements as the underlying model.
224    pub fn add_column(&mut self, values: &[f64]) -> bool {
225        assert!(values.len() == self.num_rows() as usize + 1);
226        1 == unsafe { lp::add_column(self.lprec, values.as_ptr() as *mut _) }
227    }
228
229    /// Add a column to the model, scattering `values` by `indices`.
230    ///
231    /// The values for the column are taken from `values`. The value from `values[i]` will be
232    /// placed into row `indices[i]`. The length used is the max of the lengths of `values` and
233    /// `indices`. There is a debug_assert that these are equal.
234    pub fn add_column_scatter(&mut self, values: &[f64], indices: &[libc::c_int]) -> bool {
235        debug_assert!(values.len() == indices.len());
236        let len = std::cmp::max(values.len(), indices.len());
237        1 == unsafe { lp::add_columnex(self.lprec, len as libc::c_int, values.as_ptr() as *mut _, indices.as_ptr() as *mut _) }
238    }
239
240    /// Read a column from the model.
241    pub fn get_column(&self, values: &mut [f64], column: libc::c_int) -> bool {
242        assert!(values.len() >= self.num_rows() as usize + 1);
243        1 == unsafe { lp::get_column(self.lprec, column, values.as_mut_ptr()) }
244    }
245
246    /// Read a row from the model.
247    pub fn get_row(&self, values: &mut [f64], row: libc::c_int) -> bool {
248        assert!(values.len() >= self.num_cols() as usize + 1);
249        1 == unsafe { lp::get_row(self.lprec, row, values.as_mut_ptr()) }
250    }
251
252
253    /// Add a constraint to the model.
254    /// 
255    /// The constraint is that `coeffs * vars OP target`, where `OP` is specified by `kind`.
256    /// 
257    /// For optimal performance, use the `matrix_builder` method and add the objective function
258    /// first. This method is otherwise very slow for large models.
259    ///
260    /// Asserts that `coeffs` has at least as many elements as the underlying model.
261    pub fn add_constraint(&mut self, coeffs: &[f64], target: f64, kind: ConstraintType) -> bool {
262        assert!(coeffs.len() >= self.num_cols() as usize + 1);
263        1 == unsafe { lp::add_constraint(self.lprec, coeffs.as_ptr() as *mut _, kind as libc::c_int, target) }
264    }
265
266    /// Add a [Special Ordered Set](http://lpsolve.sourceforge.net/5.5/SOS.htm) constraint.
267    ///
268    /// The `weights` are scattered by `variables`, that is, `weights[i]` will be specified for
269    /// column `variables[i]`.
270    ///
271    /// The length used is the max of the lengths of `values` and `indices`. There is a
272    /// debug_assert that these are equal.
273    pub fn add_sos_constraint(&mut self, name: &CStr, sostype: SOSType, priority: libc::c_int,
274                              weights: &[f64], variables: &[libc::c_int]) -> bool {
275        let len = std::cmp::max(weights.len(), variables.len());
276        debug_assert!(weights.len() == variables.len());
277        0 != unsafe { lp::add_SOS(self.lprec, name.as_ptr() as *mut _, sostype as libc::c_int, priority, 
278                             len as libc::c_int, variables.as_ptr() as *mut _, weights.as_ptr() as *mut _) }
279    }
280
281    /// Delete a column from the model.
282    ///
283    /// The other columns are shifted leftward. `col` cannot be 0, as that column represents the
284    /// RHS, which must always be present.
285    pub fn del_column(&mut self, col: libc::c_int) -> bool {
286        1 == unsafe { lp::del_column(self.lprec, col) }
287    }
288
289    /// Delete a constraint from the model.
290    ///
291    /// The other constraints are shifted upwards. `row` cannot be 0, as that row represents the
292    /// objective function, which must always be present.
293    pub fn del_constraint(&mut self, row: libc::c_int) -> bool {
294        1 == unsafe { lp::del_constraint(self.lprec, row) }
295    }
296
297    /// Returns `Some(true)` if the specified column can be negative, `Some(false)` otherwise.
298    ///
299    /// If the column is out-of-bounds, `None` is returned.
300    pub fn is_negative(&self, col: libc::c_int) -> Option<bool> {
301        if col > self.num_cols()+1 {
302            None
303        } else {
304            Some(unsafe { lp::is_negative(self.lprec, col) } == 1)
305        }
306    }
307
308    /// Set a variable to be either binary or floating point.
309    pub fn set_variable_type(&mut self, col: libc::c_int, vartype: VarType) -> bool {
310        1 == unsafe { lp::set_binary(self.lprec, col, vartype as libc::c_uchar) }
311    }
312
313    /// Get the type of a variable, `None` if `col` is out of bounds.
314    pub fn get_variable_type(&self, col: libc::c_int) -> Option<VarType> {
315        if col > self.num_cols()+1 {
316            None
317        } else {
318            let res = if unsafe { lp::is_binary(self.lprec, col) } == 1 {
319                VarType::Binary
320            } else {
321                VarType::Float
322            };
323            Some(res)
324        }
325    }
326
327    /// Set the upper and lower bounds of a variable.
328    pub fn set_bounds(&mut self, col: libc::c_int, lower: f64, upper: f64) -> bool {
329        1 == unsafe { lp::set_bounds(self.lprec, col, lower, upper) }
330    }
331
332    /// Set the bounds mode to 'tighten'.
333    ///
334    /// If the bounds mode is `true`, then when `set_bounds`, `set_lower_bound`, or
335    /// `set_upper_bound` is used and the provided bound is less restrictive than the current bound
336    /// (ie, its absolute value is larger), then the request will be ignored. However, if the new
337    /// bound is more restrictive (ie, its absolute value is smaller) the request will go through.
338    ///
339    /// If the bounds mode is `false`, the bounds will always be set as specified.
340    pub fn set_bounds_mode(&mut self, tighten: BoundsMode) {
341        unsafe { lp::set_bounds_tighter(self.lprec, tighten as libc::c_uchar) };
342    }
343
344    /// Get the bounds mode.
345    ///
346    /// See `set_bounds_mode` for what this value means.
347    pub fn get_bounds_mode(&self) -> BoundsMode {
348        if unsafe { lp::get_bounds_tighter(self.lprec) } == 1 {
349            BoundsMode::Restrictive
350        } else {
351            BoundsMode::None
352        }
353    }
354
355    /// Set the type of a constraint.
356    pub fn set_constraint_type(&mut self, row: libc::c_int, contype: ConstraintType) -> bool {
357        1 == unsafe { lp::set_constr_type(self.lprec, row, contype as libc::c_int) }
358    }
359
360    /// Get the type of a constraint, or `None` if out of bounds or another error occurs.
361    pub fn get_constraint_type(&self, row: libc::c_int) -> Option<ConstraintType> {
362        if row > self.num_rows()+1 {
363            None
364        } else {
365            let res = unsafe { lp::get_constr_type(self.lprec, row) };
366            match res {
367                1 => Some(ConstraintType::Le),
368                2 => Some(ConstraintType::Ge),
369                3 => Some(ConstraintType::Eq),
370                _ => None,
371            }
372        }
373    }
374
375    /// Set a variable to be unbounded.
376    pub fn set_unbounded(&mut self, col: libc::c_int) -> bool {
377        1 == unsafe { lp::set_unbounded(self.lprec, col) }
378    }
379
380    /// Check if a variable is unbounded.
381    pub fn is_unbounded(&self, col: libc::c_int) -> Option<bool> {
382        if col > self.num_cols()+1 {
383            None
384        } else {
385            Some(unsafe { lp::is_unbounded(self.lprec, col) } == 1)
386        }
387    }
388
389    /// Set the practical value for "infinite"
390    ///
391    /// This is the bound of the absolute value of all variables. If the absolute value of a
392    /// variable is larger than this, it is considered to have diverged.
393    pub fn set_infinite(&mut self, infinity: f64) {
394        unsafe { lp::set_infinite(self.lprec, infinity) };
395    }
396
397    /// Get the value of "infinite"
398    ///
399    /// See set_infinite for more details.
400    pub fn get_infinite(&self) -> f64 {
401        unsafe { lp::get_infinite(self.lprec) }
402    }
403
404    /// Set a variable's integer type.
405    pub fn set_integer(&mut self, col: libc::c_int, must_be_integer: bool) -> bool {
406        1 == unsafe { lp::set_int(self.lprec, col, if must_be_integer { 1 } else { 0 }) }
407    }
408
409    /// Check if a variable is an integer.
410    pub fn is_integer(&self, col: libc::c_int) -> Option<bool> {
411        if col > self.num_cols()+1 {
412            None
413        } else {
414            Some(unsafe { lp::is_int(self.lprec, col) } == 1)
415        }
416    }
417
418    /// Sets the objective function.
419    ///
420    /// Asserts that `coeffs` has at least as many elements as the underlying model.
421    pub fn set_objective_function(&mut self, coeffs: &[f64]) -> bool {
422        assert!(coeffs.len() >= self.num_cols() as usize + 1);
423        1 == unsafe { lp::set_obj_fn(self.lprec, coeffs.as_ptr() as *mut _) }
424    }
425
426    /// Scatters `coeffs` into the objective function coefficients with `indices`.
427    ///
428    /// The length used is the max of the lengths of `coeffs` and `indices`. There is a
429    /// debug_assert that these are equal.
430    pub fn scatter_objective_function(&mut self, coeffs: &[f64], indices: &[libc::c_int]) -> bool {
431        let len = std::cmp::max(coeffs.len(), indices.len());
432        debug_assert!(coeffs.len() == indices.len());
433        1 == unsafe { lp::set_obj_fnex(self.lprec, len as libc::c_int, coeffs.as_ptr() as *mut _, indices.as_ptr() as *mut _) }
434    }
435
436    /// Sets the range of a constraint.
437    ///
438    /// If the constraint type is `<=`, then the "actual" constraint will be `RHS - range <= v <= RHS`.
439    ///
440    /// If the constraint type is `>=`, then the "actual" constraint will be `RHS <= v <= RHS + range`.
441    ///
442    /// This puts a bound on the constraint and can give the solver more freedom, and is more
443    /// efficient than adding an extra constraint.
444    pub fn set_constraint_range(&mut self, row: libc::c_int, range: f64) -> bool {
445        1 == unsafe { lp::set_rh_range(self.lprec, row, range) }
446    }
447
448    /// Get the range on a constraint if one is set, otherwise `None`.
449    pub fn get_constraint_range(&self, row: libc::c_int) -> Option<f64> {
450        if row > self.num_rows() + 1 {
451            None
452        } else {
453            let delta = unsafe { lp::get_rh_range(self.lprec, row) };
454            if delta == self.get_infinite() {
455                None
456            } else {
457                Some(delta)
458            }
459        }
460    }
461
462    /// Solve the model.
463    pub fn solve(&mut self) -> SolveStatus {
464        use SolveStatus::*;
465        match unsafe { lp::solve(self.lprec) } {
466            -2 => OutOfMemory,
467            -1 => NotRun,
468            0 => Optimal,
469            1 => Suboptimal,
470            2 => Infeasible,
471            3 => Unbounded,
472            4 => Degenerate,
473            5 => NumericalFailure,
474            6 => UserAbort,
475            7 => Timeout,
476            9 => Presolved,
477            10 => ProcFail,
478            11 => ProcBreak,
479            12 => FeasibleFound,
480            13 => NoFeasibleFound,
481            status => panic!("unknown solve status {}", status)
482        }
483    }
484
485    /// Read out the values assigned to variables from the most recent `solve`.
486    ///
487    /// Returns `None` if `vars` does not have at least as many elements as the underlying model
488    /// has columns. Otherwise, returns `Some` with the slice truncated to the number of columns.
489    pub fn get_solution_variables<'a>(&self, vars: &'a mut [f64]) -> Option<&'a mut [f64]> {
490        let cols = self.num_cols();
491        if vars.len() < cols as usize {
492            None
493        } else {
494            unsafe { lp::get_variables(self.lprec, vars.as_mut_ptr()) };
495            Some(&mut vars[..cols as usize])
496        }
497    }
498
499    /// Construct a wrapper for a pre-existing `lprec`.
500    ///
501    /// This is unsafe as the pointer is not null-checked etc.
502    pub unsafe fn from_lprec(lprec: *mut lp::lprec) -> Problem {
503        Problem {
504            lprec: lprec
505        }
506    }
507
508    /// Get the `lprec` that this wraps.
509    ///
510    /// Don't `delete_lp` it, please.
511    pub fn to_lprec(&self) -> *mut lp::lprec {
512        self.lprec
513    }
514
515    pub fn num_cols(&self) -> libc::c_int {
516        unsafe { lp::get_Ncolumns(self.lprec) }
517    }
518
519    pub fn num_rows(&self) -> libc::c_int {
520        unsafe { lp::get_Nrows(self.lprec) }
521    }
522}
523
524impl Drop for Problem {
525    fn drop(&mut self) {
526        unsafe { lp::delete_lp(self.lprec) }
527    }
528}
529
530impl Clone for Problem {
531    fn clone(&self) -> Problem {
532        let ptr = unsafe { lp::copy_lp(self.lprec) };
533        if ptr.is_null() {
534            panic!("OOM when trying to copy_lp")
535        }
536        Problem { lprec: ptr }
537    }
538}
539
540unsafe impl Send for Problem { }
541
542#[cfg(test)]
543mod tests {
544    use Problem;
545    #[test]
546    fn smoke() {
547        let mut lp = Problem::new(0, 0).unwrap();
548        assert_eq!(lp.solve(), ::SolveStatus::NotRun);
549    }
550}
lpsolve/lib.rs

lpsolve/
lib.rs
