[Help-glpk] infeasibility

[Yongduek Seo]

Dear,

After reading the FAQ about finding constraints causing  
infeasibility, I have some questions:

1. Given a bunch of constraints, can I find exactly which of them are  
causing the infeasibility?
     Since there are lots of  constraints, dropping one by one is not  
appropriate to me.
     I want to find minimum number of infeasible constraints without  
abandoning any feasible constraints.

2.  It seems  from the FAQ (below) that there is a method when the  
problem has a feasible dual.

     2.1. How can I know that the problem has a feasible dual?
     2.2. Could you explain the meaning of it?
     2.3. When does such a solution exist in general?

Thank you in advance.
best.
SEO.
------------------------------------------------------------------------ 
------------------------------------------------------
   Q. How do I determine which constraints are causing infeasibility?

   A straightforward way to find such a set of constraints is to drop
   constraints one at a time. If dropping a constraint results in a
   solvable problem, pick it up and go on to the next constraint. After
   applying phase 1 to an infeasible problem, all basic satisfied
   constraints may be dropped.

   If the problem has a feasible dual, then running the dual simplex
   method is a more direct approach. After the last pivot, the nonbasic
   constraints and one of the violated constraints will constitute a
   minimal set. The GLPK simplex table routines will allow you to pick a
   correct constraint from the violated ones.

   Note that the GLPK pre-solver needs to be turned off for the  
preceding
   technique to work, otherwise GLPK does not keep the basis of an
   infeasible solution.

   Also a more detailed methodology has been posted on the mail list
   archive at
   <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>.