Feature request: Support SOS1 constraints

[jacobsvante]

Thanks for continuing the work on minip, I really think it is useful in some cases.

I was wondering if you might consider adding support for SOS1 or cardinality constraints? And adding that to good_lp? That would make this library even more useful!

I would do it myself if I knew more about how to implement LP stuff, but unfortunately this is not my area of expertise. So I'm throwing this one out there 😅

[Specy]

Hello! Sorry for the late reply, I hadn't seen the issue.

I'm not too much of an LP expert either, I made the fork mostly to add some things and fixed others, while leaving the community the possibility to contribute.

Just to make sure I understand the issue, what API would you like to see from the library if SOS1 constraints were added?

What do you expect the solver to do with this new method?

Looking around the web it seems like this constraint is used to enforce that at most one of the variables in the set has value 1, and all the others must be 0 (all binary variables)

I could see this improving branch and bound by branching on the individual variables and fixing the other variables to be 0, as to not recalculate each branch which would lead to invalid constraint. If you have a constraint with many variables, and the constraint is SOS1, then this would reduce the branches by a lot

[jacobsvante]

Hi Specy,

Sorry for the late reply here as well. Life in a nutshell.

That's a good description about how Special Ordered Sets work. Another alternative is implementing cardinality constraints, which is a more generalized form of SOS. See SCIP's documentation here: https://www.scipopt.org/doc/html/cons__cardinality_8c.php

Implementation wise one could use big-M to simulate SOS constraints. But apparently it's sub-optimal. Again, my skills in this area are limited 😅

[Specy]

Thank you for the clarifications!

I'm thinking we could add a preprocessing step when creating a solver that analyzes the constraints and extracts metadata about the constraints/variables so that they can be used when picking variables for branch and bound, at that point we'd need to have a sort of context inside of the recursive steps of branch and bound so that we remember past choices.

I'm just thinking through what we would need to do, It would be a pretty significant change, I don't currently have the time to work on it, hopefully someone can pick it up

[jacobsvante]

Sounds like that might be a good approach (although again, not my area). Crossing my fingers that someone with time comes along and adds this. I would consider adding a bounty for this, say $500.

[Specy]

Thank you for the offer! I've added a bounty label to make the issue more visible if anyone wants to pick it up!

[jacobsvante]

Thanks. If someone can implement a proper SOS1+SOS2 implementation in microlp + good_lp, I will give $500. Or cardinality constraints as implemented in SCIP as an alternative.

[jacobsvante]

@lovasoa Do you know someone who might be interested in implementing this?

[lovasoa]

It's hard to find a rust engineer familiar with linear programming, and ready to spend a few days coding for $500 😁

It may be a nice project for an university student in an optimization cursus...

But, as a side question, is there a reason you want to do this in microlp instead of a more established solver?

[jacobsvante]

Thanks for the response @lovasoa. Too bad that not more math wizards have come to the Rust ecosystem yet. I'm thinking that the strictness of Rust should appeal to them 😅

I'm running a piece of software in an environment where coin-cbc or scip is not readily available. Using pure rust libraries is completely pain free as I can just deploy the (cross platform) compiled binary.

Plus from my experience microlp (or minilp) has been equally fast to coin-cbc and scip, for the optimization problems we're solving.

[Specy]

I've posted the issue on the rust discord server, I might post It on Reddit too.

Since this is mostly a performance improvement, could you provide an example of where Cardinality constraints are used in your use case so it can be used to test the effectiveness of the changes? (even in good_lp)

Also this is probably not the only thing that can be improved to speed up the integer solver, I'm thinking the cloning of the solver in the branch and bound (to keep the prior context) could be improved to only save the necessary things needed to recover the prior state, but that's for another issue.

[jacobsvante]

Thanks Specy.

I will try to find the time to create an example. But really, we mainly use SOS1 constraints to avoid hard to read big-m code in our codebase.