Linprog Problem--Exiting: The constraints are overly stringent; no feasible point exists.

Hi, I am trying to solve minimum cost network problem for water supply system using linprog function. I wrote all code for this problem to use simplex algorithm and run, but I get the following statement as "Exiting: The constraints are overly stringent; no feasible point exists." I also tried interior-point algorithm. When I use this method, the optimization was terminated. However, the result does not satisfies the constraints. Can you help me, please?

Answer 1

[Matt J]

If your problem dimension is small enough, you can also try using LCON2VERT to find the vertices of your constrained region (assuming it is expected to be bounded). If the routine returns [], it will corroborate what linprog is telling you.

One other thing to be careful of, in addition to the points at Alan's documentation link, is not to use inequality constraints to express something that is really an equality constraint. For example the equality x=b can in theory be expressed using inequality constraints,

    x<=b
   -x<=-b

but if you do this, linprog will probably see your feasible set as empty due to machine precision issues. You should specify x=b using Aeq,beq inputs and not A,b inputs.

Answer 2

[Alan Weiss]

The documentation has some suggestions on steps to try to see if there is a feasible point for your problem.

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 3

[John D'Errico]

Alan suggests looking to see if a feasible point exists. However, I'd bet a good amount that no such point exists since that is what the termination message tells you.

So I'd strongly suggest that you look to see if the constraints are coded up properly. Then check your assumptions, and your model for the system that caused the constraints to be generated. Have you formulated the problem correctly?