Diagnose infeasibility of linear programming

Greetings,

I use linprog function with different method to solve a linear programming problem. But I got exitflag=-2, which means that there is no feasible solution. It seems the current problem may have conflicts in real world. I need to check which constraints can be relaxed to well-define the problem.

However, I have more thant 100 constraints in this linear programming problem. I don't know how can I diagnose the infeasibility. Can anyone give me some hints on how to diagnose the infeasibility of constraints?

By the way, I also use cplexlp function which is linear programming function of Cplex by IBM. It seems there are some ways to diagnose the infeasibility in Cplex. But I just started to use cplex and don't have idea where to start to diagnose.

Thank you very much! :)

Answer 1

[Bruno Luong]

"I need to check which constraints can be relaxed to well-define the problem."

It likes asking: when a glass of water spills out which of the water molecule is a culpite. The answer is all of them.

For example if you take as simple case in R^2:

z=exp(2i*pi*[0:2]/3);
A=[real(z); imag(z)]'
b=[-1; -1; -1]

Values

A =

    1.0000         0
   -0.5000    0.8660
   -0.5000   -0.8660

>> b

b =

    -1
    -1
    -1

you'll get no feasible point x such that three constraints

    A*x <= b

are satisisfied.

But if you remove any row of A, at let the number of constraints is 2, then it becomes well defined. Which one is a bad one? Answer: all of them.

[Devin]

Sorry, I think I did not clearly explain my question.

The infeasible model can be converted to a feasible model if some constraints are modified. This process is defined as relaxation (This is a hyperlink about relaxation in cplex by IBM).

Accurately speaking, I am looking for the method of sufficient minimal change of constraints.

Using your example, the deepth of water that a bucket can hold is dependent of the shortest part of this bucket. If I would like to increase the deepth of water that the bucket can hold, I just need to elongate the shortest part, somehow relaxing the constraints to contain more water (more feasible solutions).

Thank you