Input linear program using matrix format

[luli-git]

Hi,

I'm trying to find some solver to solver some large optimization problems. I have my constraints formatted as Ax=b. However, in the example you provided, variables and constraints are added one by one like below:

variables: vec![
            Variable {
                name: "x".to_string(),
                is_integer: true,
                lower_bound: -10.,
                upper_bound: -1.,
            },
            Variable {
                name: "y".to_string(),
                is_integer: true,
                lower_bound: 4.,
                upper_bound: 7.,
            },
        ],

which does not seem very efficient for problems with thousands of variables. Do you know how to format an optimization problem using sparse matrices and vectors without having to add the coefficients one by one?

Thank you for your help.

[lovasoa]

What do you mean adding the coefficients one by one ? Of course you have to add all of the variables, but you don't add all the zero coefficients in your matrix.

Can you provide an example and point out where the performance problem is ?

[lovasoa]

And what is your problem exactly ? Do you have inequalities, or just Ax=b ?

If you just have Ax=b, then you have nothing to optimize, you can just solve the linear system.

[luli-git]

Thank you for your quick reply! Our problem is to minimize the one norm of a vector x, under the constraint that Ax = 0. The variable x could have millions of entries and the constraint matrix A could have thousands of rows. We cannot just solve the linear system because this could be multiple valid solutions and we want to find the one with the smallest one norm.

In the example you provided, you added a constraint by specifying:

constraints: vec![Constraint {
            lhs: StrExpression("x - y".to_string()),
            operator: Ordering::Less,
            rhs: -4.5,
        }],

However, in our case, one of the constraints will be one row of A multiplied by x is equal to 0, or, equivalently, Ax = 0. We currently have matrix A as a sparse matrix and x as a vector. Do you have any suggestions on how we could input this type of constraint?

Thank you so much for your help!

[lovasoa]

Minimize the one norm of a vector x, under the constraint that Ax = 0

Am I mistaken or the solution to the problem you state is trivially x=0 ? If you have Ax = b with b != 0 the problem becomes more interesting.

Do you have any suggestions on how we could input this type of constraint?

You either implement the WriteToLpFileFormat on whatever you use to store your matrix lines, or you serialize them to string beforehand. Everything will need to be serialized to launch the solver binary anyway. If you don't want to serialize your input, you can use a solver library directly such as highs or cbc.