Interest in adding a pre-solve step to reduce redundant constraints?

[ynadji]

First off, thanks for the library! Very cool stuff.

I'm curious if you have any interest in adding a pre-solve phase to handle redundant constraints? I came across this limitation trying to use linear-programming to solve an advent of code problem and had to add this LLM slop to make it work. I'll admit I'm no linalg pro, but I'm interested in learning and contributing. But before digging in, I figured it'd be prudent to ask first if this is something you would want to merge.

Let me know if you're interested, have any tips, or recommended reading so I can do it properly if you're interested!

[ntrocado]

I was also trying to solve the same hellish (for me) problem and found the same limitation.

I don't have much to add but in any case here's a minimal example:

(linear-programming:solution-variable
 (linear-programming:solve-problem
  (linear-programming:parse-linear-problem
   `(min (= w (+ a b c d)))
   `((= (+ a b) 7)
     (= (+ c d) 5)
     (= (+ a b c d) 12))))
 'w)

Fails with "Artificial variable still in basis and cannot be replaced".

And another llm slop patch.

[neil-lindquist]

Yes, it would be very good to be able to handle redundant constraints. Thanks for the suggestion.

I'm afraid I'm not much of a linear programming expert, so I can't offer any suggestions on good linear programming resources. I imagine there's existing literature on detecting redundant constraints and handling this type of issue.

Having not thought about the simplex method in quite a while, @ntrocado's idea of just swapping another arbitrary variable into the basis seems to me like it might be the best solution. If an artificial variable is 0, that means we can swap it out of the basis without changing the values of any variables. (And if all of the artificial variables are zero, then the computed values of the "real" variables satisfy the original constraints. So, we have a valid starting point and we can just add zero-variables to the basis until we have enough.)

The one downside I can currently see is that we have to compute on the extra constraint for both Simplex-solves. But, that's not a huge issue for a corner case like this (especially since I doubt this library has good performance anyways).

The problem I'm seeing with the Gaussian elimination approach is inequalities. For example, none of the following constraints are redundant but the constraint matrix would only be rank 2.

(<= (+ a b c d) 10)
(<= (+ a b)         8)
(<= (+ c d)         8)