home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / numanal / 3352 < prev    next >
Encoding:
Text File  |  1992-11-19  |  1.5 KB  |  34 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!batcomputer!ghost.dsi.unimi.it!schoen
  3. From: schoen@ghost.dsi.unimi.it
  4. Subject: Re: question: how to show that a set of linear inequalities is consistent?
  5. References: <batra.722077145@beagle> <1992Nov18.091337.23934@walter.cray.com>
  6. Organization: Computer Science Dep. - Milan University
  7. Date: Thu, 19 Nov 1992 10:50:23 GMT
  8. Message-ID: <1992Nov19.105023.13209@ghost.dsi.unimi.it>
  9. Lines: 18
  10.  
  11. jwg@sparcman.cray.com (John Gregory) writes:
  12. >|> 
  13. >|> I have a large set of  linear inequalities (with about a 20 unknowns)
  14. >|> and I am about to use linear programming to solve for them.
  15.  
  16.  
  17. >|> Is there an algorithm that will tell me that my set is consistent or
  18. >|> inconsistent?  
  19.  
  20. [...]
  21. >This question really is not as well-posed as you may think.  If a group
  22. >of inequalities is inconsistent (infeasible), there may be many ways of
  23. >removing a few to give a feasible set.  It's not likely you can point at
  24. >one or two and say "those are the culprits". 
  25.  
  26. Notice that the problem of finding a MINIMUM number of inequalities to remove in
  27. order to restore feasibility is NP-complete.
  28.  
  29. -- 
  30. | Fabio Schoen (assoc .prof. of Op.Res.)        e-mail:                     |
  31. | Dipartimento di Scienze della Informazione    schoen@ghost.dsi.unimi.it   |
  32. | via Comelico 39/41 - I20135 Milano ITALY                                  |
  33. | fax: +39 (2) 55006.276 or 373                 Tel: +39 (2) 55006.319      |
  34.