How to remove constraints in LP solver?

[SeongwooLimKR]

When I want to solve LP with the following constrains,

Constraint 0: x + 2y <= 12,
Constraint 1: x + 2y <= 14.

Then the constraint 1 is redundant, because of the constraint 0.

How to find the redundant constraints from the original (all) constraints?

e.g. (Python environment)

x = solver.NumVar(0, solver.infinity(), "x")
y = solver.NumVar(0, solver.infinity(), "y")

# Constraint 0: x + 2y <= 12,
solver.Add(x + 2 * y <= 12.0)
# Constraint 1: x + 2y <= 14,
solver.Add(x + 2 * y <= 14.0)

# Find and Remove constraint 1
solver.FUNC_TO_FIND_AND_REMOVE_REDUNDANT

(Updated)
After searching more in Google, I find that we can decide whether the constraint is redundant or not by another LP.
e.g.)
maximize x + 2y
subject to x + 2y <= 12
The above LP return 12 which is less than 14. Therefore the "x + 2y <= 14" constraint is redundant.
Now, I wonder if I should implement it or if it's already implemented as module or function.

[lperron]

why do you want to remove it ?

[SeongwooLimKR]

I want to iteratively add constraints and check the feasibility of constraints.
If we can remove the redundant constraints, the feasibility check become more efficient in my thought.

[lperron]

do you want the solver to decide which constraint to remove, or do you want to specify which constraint to remove ?

[SeongwooLimKR]

I want to specify which constraint to remove.
After removing redundant constraints, I will run LP solver with the smaller number of constrains.

[lperron]

constraint c0 = solver.Add(x + 2 * y <= 12.0)

# Later
c0.Clear()

[SeongwooLimKR]

My question is ambiguous due to the lack of my English skill. I'm sorry to bother you.
What I exactly want is finding the redundant constrains rather than remove the constraints.
If we can find the redundant constrains, then we can remove the constraints by c0.Clear().

After searching more in Google, I find that we can decide whether the constraint is redundant or not by another LP.
e.g.)
maximize x + 2y
subject to x + 2y <= 12
The above LP return 12 which is less than 14. Therefore the "x + 2y <= 14" constraint is redundant.
Now, I wonder if I should implement it or if it's already implemented as module or function.

[lperron]

Removing redundant constraints in an LP is a complex task. There are heuristics that run during presolve. But it is expensive, prone to numerical errors. I suggest to look for references in the presolve literature. Le jeu. 21 sept. 2023, 06:13, Seongwoo Lim ***@***.***> a écrit :

…

My question is ambiguous due to the lack of my English skill. What I exactly want is finding the redundant constrains rather than remove the constraints. If we can find the redundant constrains, then we can remove the constraints by c0.Clear(). After searching more in Google, I find that we can decide whether the constraint is redundant or not by another LP. e.g.) maximize x + 2y object to x + 2y <= 12 The above LP return 12 which is less than 14. Therefore the "x + 2y <= 14" constraint is redundant. Now, I wonder if I should implement it or if it's already implemented as module or function. — Reply to this email directly, view it on GitHub <#3926 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3IEE3MWTM4DJC2G2G3X3O5IHANCNFSM6AAAAAA47OQJ6Q> . You are receiving this because you commented.Message ID: ***@***.***>

[SeongwooLimKR]

Thanks for your kind response!