Article View: sci.math.num-analysis
Article #885Re: question: how to show that a set of linear inequalities is consistent?
From: schoen
Date: Thu, 19 Nov 1992 10:50
Date: Thu, 19 Nov 1992 10:50
23 lines
1537 bytes
1537 bytes
jwg@sparcman.cray.com (John Gregory) writes: >|> >|> I have a large set of linear inequalities (with about a 20 unknowns) >|> and I am about to use linear programming to solve for them. >|> Is there an algorithm that will tell me that my set is consistent or >|> inconsistent? [...] >This question really is not as well-posed as you may think. If a group >of inequalities is inconsistent (infeasible), there may be many ways of >removing a few to give a feasible set. It's not likely you can point at >one or two and say "those are the culprits". Notice that the problem of finding a MINIMUM number of inequalities to remove in order to restore feasibility is NP-complete. -- | Fabio Schoen (assoc .prof. of Op.Res.) e-mail: | | Dipartimento di Scienze della Informazione schoen@ghost.dsi.unimi.it | | via Comelico 39/41 - I20135 Milano ITALY | | fax: +39 (2) 55006.276 or 373 Tel: +39 (2) 55006.319 |
Technical Details
Message-ID:
<1992Nov19.105023.13209@ghost.dsi.unimi.it>Path:
arc1-ca.pugleaf.net!sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!batcomputer!ghost.dsi.unimi.it!schoenReferences:
<batra.722077145@beagle> <1992Nov18.091337.23934@walter.cray.com>Show Full Headers
Complete Article Headers
Newsgroups: sci.math.num-analysis Path: arc1-ca.pugleaf.net!sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!batcomputer!ghost.dsi.unimi.it!schoen From: schoen@ghost.dsi.unimi.it Subject: Re: question: how to show that a set of linear inequalities is consistent? References: <batra.722077145@beagle> <1992Nov18.091337.23934@walter.cray.com> Organization: Computer Science Dep. - Milan University Date: Thu, 19 Nov 1992 10:50:23 GMT Message-ID: <1992Nov19.105023.13209@ghost.dsi.unimi.it> Lines: 18