I work on some water resource modelling software. Basically, water companies model their grid: reservoirs, rivers, pipes etc. and then it uses linear programming to minimise cost while maximising the water that reaches demand (we call this the resource state). You don't need to understand this in detail to understand my issue but it might provide some useful context.
I'm trying to find a way to detect when multiple optimal solutions exist. This is an issue because it means the model can return different solutions from the same inputs, leading to the client thinking the software is broken.
I've been doing some research and found that you can look for a constraint function's coefficients being matching factors of the coefficients of the objective function. E.g. constraint 4X + 6Y < Z will produce a parallel line to objective function Maximise 2X + 3Y because 4/2 = 2 and 6/3 = 2. OK, this seems like a simple solution to my problem. But I can see two possible issues:-
1. How do I know that a particular constraint function actually bounds the solution space? E.g. :-
Lets assume that the objective function was parallel to line C. That would incorrectly indicate multiple solutions (a single solution exists at the convergence of A and B). How do I detect and avoid that false positive.
2. How do I detect that the constraint in question is on the "right" side of the possible solution space? E.g. :-
Let's assume that the objective function is parallel to line A. That would incorrectly indicate a multiple solution if I'm trying to maximise X and Y (the single solution here actually exists at the convergence of B and D). How do I detect and avoid that one
Reply With Quote