Linear Programming: how to identify conflicting equations

[cjs94]

I'm reading about the Simplex method to solve a Linear Program. If a program is rejected as being infeasible, is there a method to identify which equations are causing it to be infeasible and a technique for reducing the program in an optimal way? (I'm not sure what 'optimal' is exactly, but my guess would be removing the fewest equations.)

My understanding is that each equation can have an artificial variable a_n and that the test for feasibility is that all a_n must be zero. If so, that leads to some questions:

1. It would seem obvious then that all I have to do is identify and remove all equations where a_n > 0. Is that fair?
2. Is is possible for one or more conflicting equations to end up with a_n = 0?
3. Is it possible that an equation, while not causing a direct conflict, constrains two other equations such that they conflict? In that case, removing the first, single equation would be a better solution.

Thanks,
Chris

 

[FactChecker]

There may be a lot of combinations of equations whose removal would make the problem feasible. Just because one running of the Symplex method has a particular set of a_n > 0 does not mean that the set is unique. If you are looking for any reduced set that would be feasible, removing those a_n > 0 constraints should do it. But that is very arbitrary and may not be satisfying.

 

[scottdave]

There may be some packages with R & Python, which could visualize what is happening between the equations. I am learning about optimization methods, myself. Something to think about - if this is based on a real world situation, then which constraints Can be changed in a reasonable way?

I came across this video, describing using pulp in Python, with optimizing some everyday decisions such as a book reading list or vacation options. Pretty interesting. I downloaded her notebooks from GitHub and ran some for myself. I use Azure Notebooks.