Simplify overflows the stack

[remysucre]

I have a very long objective function (sum of 1000+ terms) which causes simplify(expr: &LpExpression) -> LpExpression to overflow the stack when adding the objective function to the problem. Similarly solver.run also triggers the overflow. I understand this might not be the standard use case, and there might not be an easy fix. But I'd like to know what the purpose of simplify is, and if there's a way I can manually get my function into its "normal form" so that I can remove the call to simplify.

[zappolowski]

This is caused by simplify not being tail recursive. As a quick workaround you could try is to increase (or even remove) the stack size limit (ulimit).

[remysucre]

Example for replication:

use lp_modeler::dsl::*;

fn main() {
    let mut problem = LpProblem::new("overflow", LpObjective::Minimize);
    let obj_vec: Vec<LpExpression> = {
        (1..2000).map(|n| {
            let v = "v".to_owned() + &n.to_string();
            let bin = LpBinary::new(&v);
            3 * bin
        }).collect()
    };
    problem += obj_vec.sum();
}

[remysucre]

@zappolowski worked like a charm, thanks! For reference, I also needed to set RUST_MIN_STACK in addition to running ulimit.

[jcavat]

Effectively, the call is not tailrec. Even if it was, rust compiler don't optimize it. Right now, one of the problems is we need sometime to replay the simplify call. Sometimes, some expressions are not simplify enough. This is an ugly workaround, I admit.

An improvement I have in mind is to apply the technic we use for the same library for Scala https://github.com/jcavat/scalinea where we fix the problem using different System/Domain :

The DSL (visible API layer) is an AST like ruls-lp-modeler under the form :

Add( Mult(Mult(x,x), 3), 5 )

     Add
     / \
  Mult  5
  /  \
Mult  2
/ \
x x

and a Clause System (hidden layer) that keep a more flatten representation always keeping a list of terms.

In such a layer, Vars is a Map<Symbol, Exponent> and Terms (list of terms) is a Map<Vars, Constant>

The above AST would be transformed to :

Terms( 
    Vars(x -> 2) -> 3, 
    Vars() -> 5
)

It simplifies the operations. Multiplication and addition are just operations on Map.

You can take a look here to have an idea : Expr (DSL) and Terms/Vars (Clauses System)

Don't hesitate to give your opinion about possible refactoring under the same form.

[zappolowski]

Interestingly, that looks quite similar to what I started to implement yesterday

#[derive(Clone, Debug)]
enum Kind {
    Binary,
    Integer(Option<i32>, Option<i32>),
    Continuous(Option<f32>, Option<f32>),
}

#[derive(Clone, Debug)]
pub struct Variable {
    name: String,
    kind: Kind,
}

#[derive(Debug)]
pub struct Expression {
    variables: HashMap<String, (Variable, f64)>,
    constant: f64,
}

as I also ran into stack issues.

It's currently in a really rough state as I've implemented all the numeric operations manually (d'oh ... probably will take a look into impl_ops).

If this looks good to you, I'd try to wrap it up and crate a MR.

Maybe some of more my thoughts for discussion:

• get rid of possibility to create non-linear equations (not 100% sure whether this is desired, but I thought this crate is for modelling LP problems :wink: )
• simplify simplify (using the map, it simplifies itself on adding a new term) ... probably completely getting rid of it

• make it easy to evaluate the objective function (I currently use

  trait LpProblem {
    ...
  
    pub fn eval(&self, values: &HashMap<String, f32>) -> Option<f32> {
        self.obj_expr
            .as_ref()
            .map(|expr| expr.eval(values) + self.offset)
            .or(Some(0f32))
    }
  }
  
  trait LpExpression {
    ...
  
    pub(crate) fn eval(&self, values: &HashMap<String, f32>) -> f32 {
        match self {
            AddExpr(left, right) => left.eval(values) + right.eval(values),
  
            ConsBin(LpBinary { name })
            | ConsCont(LpContinuous { name, .. })
            | ConsInt(LpInteger { name, .. }) => *values.get(name).unwrap_or(&0f32),
  
            MulExpr(left, right) => left.eval(values) * right.eval(values),
  
            SubExpr(left, right) => left.eval(values) - right.eval(values),
  
            LitVal(n) => *n,
        }
    }
  }

  which is also having the stack issue ... I didn't parse the objective from the log, put just really evaluate the expression as this is general for all solvers :grinning:

[jcavat]

Yes, non-linear equations should simplify. I imagined no degree limit for quadratic solver (such as Gurobi) or even different kind of solver if we use different format (Matrix export in addition to lp_format). Overriding operators would force to check degree at runtime. I totally agree with the objective function evaluation. In my opinion it should be return by the run function :

let (solver_status, values, objective) = solver::run(&prob).unwrap();

I created an issue for this : #38

[remysucre]

Getting back to this, now even when simplify doesn't overflow the stack it simply takes too long. So lmk how I can help with this :)

[jcavat]

With pleasure ! Maybe we should use list of terms instead of a recursive Tree expr.

[jcavat]

It should be fixed by #48, #67 and #68