To check if an inequality is redundant, set up another LP in which you try to maximise the violation of the given inequality, subject to the other inequalities. If the violation is zero, the given inequality is redundant.

Lucas,

There are various methods for identification of inactive constraints (also know as redundant constraints).

I highly recommend reviewing the following paper that compares 5 methods for such task.

https://www.hindawi.com/journals/mpe/2010/723402/

Hope this helps.

Mohamed

Hi, I agree with Mohamed. In any case, redundant constraints are not a problem for LP solvers. The "a priori" elimination of such constraints simply reduces the size of the problem and thus the CPU time of the resultion perhaps but simplex method automatically determines the solution even if redundant constraints are present.

Indeed. One does not have to worry about redundancy - it's automatically taken care of.

The determination of the constraint has to be determined from experience and reality. After having the considered constraints on the LPP, you need to go through optimization of the problem. That is the way to know either the constraint is needed or not?

Regards,

Thanks, for your answers.

I agree that the LP solver will find the solution even with redundant constraints. In this problem however, I am specifically interested in exactly the redundant constraints. These constraints represent a physical system and I am hoping by knowing the redundant constraints to get more information about the physical system itself.

The recommended paper from Mohamed describes what I was looking for.

You will also be able to identify, most of the time, which constraints are redundant, by looking at the shadow price - i.e., the dual values. A dual value of 0 may indicate that it is a redundant constraint.

Most LP solvers has a presolve phase that will remove easily detected redundant constraints.

I am co-author on paper about the topic.

yes according to Michael Patriksson , cast the problem into its dual form, solve and then 0 dual variables represent inactive constraints, then from this set, hopefully its small enough, you can find redundant constraints.

you will need to know your degrees of freedom, subtract your degrees of freedom from the number of inactive constraints and this would give you how much redundant constraints you have. there are some preprocessing methods in different integer optimization textbooks

Your question is not completely strict, so there are different possible answers:

"In this case constraint number 2) is not needed. The solution will be the same when inequality number 2) is omitted."

The problem is: "the solution will be the same"

An LP may have infinitely many optimal solutions - a face of dimension > 0

If your question means

a) that the one optimal vertex found will still be optimal?

In that case the question concerns constraints not active at the (one) solution point.

b) that the set of optimal solutions remains the same?

That question is quite harder to answer since you'll have to determine all alternative optimal

points in order to anwer it.

Both possible interpretations do include non-redundant constraints being non-binding for the optimal face!

Or is the real question

c) that the constraint set is the same when removing that constraint?

This is the question for (weakly) redundant constraints according to the terminology in the paper given above.

And I think that really was your question.

Zero duals are connected to interpretation a).

But be aware that a numerical solution may give zero duals for active constraints, see e.g. the tiny two-dimensional example attached with added slack variables. None of its constraints is redundant.

Best regards

To check if an inequality is redundant, set up another LP in which you try to maximise the violation of the given inequality, subject to the other inequalities. If the violation is zero, the given inequality is redundant.

We treat given constraint as a equation and calculate from this one of the variables, and put it to another constraints. In this way, we get a new set of constraints. If this set is empty, then given constraint is redundant. It is an equivalent problem.

analogously to Adam Letchford's proposal:

First: simple Presolving as described in the Andersen/Andersen paper using the variable bounds (if there are finite ones in your problem) is computationally cheap (just compute the value for the LHS by setting the variables to their lower/upper bound according to the sign of their coefficients) and may sort out some constraints as redundant - but that would normally not find all of them: In presolving this is applied together with the determination of new variable bounds iteratively as long as there are reductions.

Then solve an auxiliary LP for each of the remaining inequality constraints.

Set the objective coefficients to those of one of the constraints, disable that constraint and solve the LP:

- if the constraint was a LE maximize. In case the optimal value is less or equal to the rhs, the constraint is redundant

- analogously if the constraint was GE minimize. disabled constraint is redundant if the optimal value or greater or equal to the rhs.

It is easy to program that process using the interface of most LP solvers - and LP solving is fast.

For the original optimization problem, find the dual problem, Lagrangian, and Lagrange multipliers. If Lagrange multipliers (associated with constraints of the prime problem) do not exist for the dual problem using KKT conditions, then the constraints can be tightened. Moreover, the larger the magnitude of the lagrange multipliers, the greater the optimal cost changes when the constraint is perturbed by a fixed amount.

Either let a commercial solver (Gurobi ; SAS Optmodel or the like) do the job for you.

Or: You would want to combine the suggestions by Michael Patrikkson (first) and Adam N. Letchford (second).

If the first step does deliver hundreds or thousands of candidates you would need some programming to get the job done.

Hi , when I want understand your question by your example and solve it from Application Win QSB to find the optimal solution ,then i find the solution in ( Infeasiabl solution ).

please can you explain the problem ... thank's

Maybe you minimize the function. Optimization solvers usually minimize functions. If you minimize, then the problem is unbounded. By maximizing it you would get x1=1 and x2=0.5. Not sure if this is your problem?

what type of variables ? ( continuse or unrestrescted )

Akhtar: In LP the KKT conditions are always necessary and sufficient - thanks to (a) the problem's convexity, and (b) the CQ "all constraints are linear".