The solver will panic if a goal or constraint reduces to a constant expression

[zeta12ti]

UPDATE: it seems the actual problem is literal expressions. Empty sums work fine, but they return a literal zero.

If a problem has an LpExpression::literal and no variables in a constraint or objective, trying to solve it will cause a panic.

Here's a reproduction:

// lp_modeler 0.5.0
use lp_modeler::dsl::*;
use lp_modeler::solvers::{CbcSolver, SolverTrait};

fn main() {
    let mut problem = LpProblem::new("problem", LpObjective::Maximize);

    problem += LpExpression::literal(0.0);

    let solver = CbcSolver::new();
    let _ = solver.run(&problem); // Here's where the panic happens
}

The backtrace is

thread 'main' panicked at 'Requested index out of bound of LpExpression vector. This should not happen.', /home/user/cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/dsl/variables.rs:368:21
stack backtrace:
   0: std::panicking::begin_panic
             at /home/user/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:519:12
   1: lp_modeler::dsl::variables::LpExpression::expr_clone_at
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/dsl/variables.rs:368:21
   2: lp_modeler::dsl::variables::LpExpression::simplify
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/dsl/variables.rs:567:23
   3: <lp_modeler::dsl::variables::LpExpression as lp_modeler::format::lp_format::LpFileFormat>::to_lp_file_format
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/format/lp_format.rs:158:25
   4: lp_modeler::format::lp_format::objective_lp_file_block
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/format/lp_format.rs:61:44
   5: <lp_modeler::dsl::problem::LpProblem as lp_modeler::format::lp_format::LpFileFormat>::to_lp_file_format
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/format/lp_format.rs:25:27
   6: lp_modeler::format::lp_format::LpFileFormat::write_lp
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/format/lp_format.rs:12:22
   7: <lp_modeler::solvers::cbc::CbcSolver as lp_modeler::solvers::SolverTrait>::run
             at /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/lp-modeler-0.5.0/src/solvers/cbc.rs:138:9
   8: tmp::main
             at ./src/main.rs:13:13
   9: core::ops::function::FnOnce::call_once
             at /home/user/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Even if the problem is otherwise perfectly valid, adding such a constraint causes a panic.

// lp_modeler 0.5.0
use lp_modeler::dsl::*;
use lp_modeler::solvers::{CbcSolver, SolverTrait};

fn main() {
    // adapted from the README example
    let a = &LpInteger::new("a");
    let b = &LpInteger::new("b");
    let c = &LpInteger::new("c");
    let mut problem = LpProblem::new("One Problem", LpObjective::Maximize);
    problem += 10.0 * a + 20.0 * b;
    problem += (500 * a + 1200 * b + 1500 * c).le(10000);
    problem += a.le(b);

    // The problematic constraint
    problem += LpExpression::literal(0.0).equal(0);

    let solver = CbcSolver::new();
    let _ = solver.run(&problem); // panic right here
}

[zeta12ti]

I don't know enough about the project to say for sure, but I think the problem traces to LpExpression::split_off_constant. When called on a literal, it overwrites the expression with LpExpression::new(). Subsequently trying to simplify that expression will panic.

This sequence happens in my first example because adding the objective has

let mut simple_expr = expr_arena.clone();
let _ = simple_expr.simplify().split_off_constant();
self.obj_expr_arena = Some(simple_expr);

After the first line, simple_expr is a literal 0.0. Simplifying and splitting off the constant makes simple_expr equal to

LpExpression {
    root: 0,
    arena: [],
},

(equivalent to LpExpression::new()). Finally, this degenerate expression is assigned to self.obj_expr_arena, overwriting the literal expression we started with.

Later, when running the solver, the expression is formatted, which calls simplify again. This time, simplify panics.

I bet something similar happens in my second example with the literal constraint.

---

I don't know if this would break anything, but it seems that replacing the line self.clone_from(&LpExpression::new()) in split_off_constant with self.clone_from(&LpExpression::literal(0.0)) would fix this. Changing that line and running the tests doesn't seem to break anything.

[githubaccount888]

+1. I don't know enough to comment on the proposed fix, but I believe we are stuck on what appears to be the same issue, where perfectly valid problems cause panics inside the LP Modeler simplification code. I've observed many cases where small (seemingly insignificant) tweaks to the problem can either cause or alleviate the panic.

[githubaccount888]

[Update] I was finally able to reduce my issue down to a small test case. It is basically the same as the one @zeta12ti proposed. The one caveat I will say is that I don't think it's as broad as any "literal expression" -- I think it's only related to literal 0.0.

It would be great if the library could properly handle these cases - obviously it's possible to work around in client code but that starts to defeat the purpose of a library like this.

This works fine:

        let mut problem = LpProblem::new("Test", LpObjective::Maximize);
        let x1 = LpContinuous::new("x1_0_X").lower_bound(0_f32).upper_bound(1000000.0);
        let x2 = LpContinuous::new("x2_0_X").lower_bound(0_f32).upper_bound(1000000.0);
        problem += -1.0 * (&x1) + 1.0 * (&x2);
        problem += (1.0*(&x1-&x2)).ge(0.0);
        CbcSolver::new().run(&problem).unwrap();

This panics:

        let mut problem = LpProblem::new("Test", LpObjective::Maximize);
        let x1 = LpContinuous::new("x1_0_X").lower_bound(0_f32).upper_bound(1000000.0);
        let x2 = LpContinuous::new("x2_0_X").lower_bound(0_f32).upper_bound(1000000.0);
        problem += -1.0 * (&x1) + 1.0 * (&x2);
        problem += (0.0*(&x1-&x2)).ge(0.0);
        CbcSolver::new().run(&problem).unwrap();

[zeta12ti]

The one caveat I will say is that I don't think it's as broad as any "literal expression" -- I think it's only related to literal 0.0.

To be precise, there's a panic when the simplified constraint or goal doesn't contain any variables. For 0.0*(&x1 - &x2), the expression is reduced to a literal 0.0, so the solver will panic.

But it works for other literals too, not just 0.0. For example,

let mut problem = LpProblem::new("Test", LpObjective::Maximize);
let x1 = LpContinuous::new("x1_0_X").lower_bound(0_f32).upper_bound(1000000.0);
let x2 = LpContinuous::new("x2_0_X").lower_bound(0_f32).upper_bound(1000000.0);
problem += -1.0 * (&x1) + 1.0 * (&x2);
problem += LpExpression::literal(1.1).ge(1.1); // note the change
CbcSolver::new().run(&problem).unwrap();

panics just the same.

[carrascomj]

What should the behaviour be? A literal is not a valid constraint, do you suggest for interpreting that as a NoOp and ignoring them? I believe it would be very cool if the compiler complained about trying to add a literal as a constrain, but for expressions generated at runtime (after simplifying another Expression) that is not possible (I think) so the user should take care of those.

[zeta12ti]

What should the behaviour be?

I made my suggestion in the second comment: when splitting off a constant, don't replace constant expressions with an invalid expression, but rather with zero.

A literal is not a valid constraint

What do you mean by that? Are you saying that Maximize [1, 1]x subject to Ax ≤ [1, 1, 1]^T, where A is the matrix [[2, 1][3, 1][0, 0]] isn't a valid linear programming problem? It's even feasible and has a unique solution. What's wrong with it? Eliminating trivial constraints is one of the major things that LP solvers are built to do.

do you suggest for interpreting that as a NoOp and ignoring them?

That would work (I think), but it's not necessary. For goals, that probably shouldn't be done. Either a constant goal should be provided to the solver (and then the solver (edit: by which I mean e.g. CBC Solver) is free to complain if it thinks that's a problem), or the library should explicitly return an error that can be caught and recovered from.

for expressions generated at runtime (after simplifying another Expression) that is not possible (I think) so the user should take care of those.

The library doesn't (currently) give any way to check if an expression simplifies to a constant. simplify is a private method and 0.5.0 made LpExpression more opaque anyway (it was an enum before, so you could check if an expression was an LpExpression::Literal). So right now it's not possible for the user to do that without reimplementing simplify.

---

If this isn't fixed, the library should give a better error message than thread 'main' panicked at 'Requested index out of bound of LpExpression vector. This should not happen.'. That alone makes this sound like a library bug.

[githubaccount888]

My opinion is the library should be able to seamlessly handle these cases. Mathematically, there is nothing special or magic about a coefficient of "0.0". The full context of my example above is that coefficients are actually being fed to the problem from an external source (database), not hard-coded inline in the source code... so what we observed in practice were sporadic library panics on some problems, which required quite a bit of debugging time to narrow down the issue.

I have since gone through my code and put a bunch of "if coef.abs() > 0" statements to avoid adding these problematic constraints. This isn't a general solution but worked around the issue for me.

I agree with @zeta12ti -- if this isn't going to be fixed, a clear and precise error message about the issue would be a good idea, and I'd also suggest adding ample warnings in the documentation as well.