Clarification/Follow-up by Chip_Eastham on 01/10/05 5:39 am:
A problem is feasible if there is a point that satisfies all the constraints. So do you perhaps mean how to find a minimal subset of constraints that makes a problem infeasible, or a maximal subset to make the problem feasible? Because you could get rid of all constraints, and the empty set of constraints would be feasible.

regards, chip

Clarification/Follow-up by kumar on 01/10/05 4:29 pm:
Sorry for not being clear!
I meant how do we identify the minimal set of constraints to be 'removed' so that the problem becomes feasible - commonly called the 'maximal feasible subsystem' problem.

Also, another clarification is that what I am looking for is a way to automate this using any of the LP solvers since the problem is too big for manual inspection of feasibility

Thanks,
kumar

Clarification/Follow-up by Chip_Eastham on 01/11/05 3:01 pm:
Hi, kumar:

Thanks for the prompt clarification.

It might be useful to "mentally" inspect the problem for some structure. Linear programming problems can be in "standard form" or not.

It is a general function of LP solvers to take problems in non-standard form and put them in standard form on the way to finding out if the problem is feasible or not. However in the process new variables and new constraints are introduced.

So, to answer your question it will be helpful to know if the problem is already in standard form (e.g. all variables satisfy nonnegativity constraints), and also to have an idea what you mean by the "problem is too big". How many variables and how many constraints are there?

As a general proposition there is nothing more that can be done to answer questions like this except to test subsets of constraints of various sizes with the obvious axioms in mind. If there exists one feasible subset of constraints of size k, then the maximum feasible subset must be at least that big (though it might not properly contain that subset). If a certain subset is not feasible, one cannot rule out that a feasible subset of equal or larger size may exist, unless all those have been exhaustively considered. However a superset of an infeasible set of constraints will of course again be infeasible.

I suppose the exploration of such a combinatorial space of constraint sets could be automated; an implementation in Prolog or some other language that has "backtracking" might be my personal choice.

regards, chip