Apparent contradiction in the behaviour of linprog

I have a problem which contains only inequalities, Ax <= b, where size(A) = [385, 320] (I don't know if that is a "big" problem for Matlab). I'm using the simplex algorithm. The last inequality (i.e., that corresponding to b(end) ) is giving me a hard time. For some values of b(end), the problem is feasible, but for others it isn't. Here comes the strange part: if I set b(end) = 0, I get a solution; now, if I set b(end) = 0.001, the problems turns out to be unfeasible. But that's nonsense, since the solution when b(end) = 0 is of course admisible when b(end) > 0 . The problem cannot become unfeasible by giving it more freedom.

With b(end)=0 the output is:

   output = 

         iterations: 307
          algorithm: 'simplex'
       cgiterations: []
            message: 'Optimization terminated.'
    constrviolation: 2.2204e-16
      firstorderopt: 6.6613e-16

with exitflag = 1.

Now, with b(end) = 0.001, the output is:

   output = 

         iterations: 0
          algorithm: 'simplex'
       cgiterations: []
            message: [1x80 char]
    constrviolation: 9.5459e-07
      firstorderopt: 1

with exitflag = -2 and message "Exiting: The constraints are overly stringent; no feasible starting point found.".

Again, it makes no sense. If the constraints weren't too stringent with b(end)=0, they can't be too stringent when b(end) is bigger.

Has anyone ever faced an issue like this one?

[Lucas Manuel Genzelis]

Please, if anyone has a theory that could explain this contradictory behaviour, I would highly appreciate it.

[Derya]

Hello Lukas,

The size of your problem seems to be reasonable; both linprog-interior-point and linprog-simplex can handle LPs of this size and much larger.

Regarding the relaxation of an inequality, I agree with you that theoretically this shouldn't make the problem "infeasible".

However, I suspect that this last constraint may be conflicting (or perhaps interacting with) other constraints in your problem resulting in numerical difficulties with the solver.

It would be nice to know how linprog-interior-point fails since its failure may indicate some linear dependency issues in the problems that it cannot handle.

Relaxing the tolerance TolFun from its default of 1e-6 (for simplex) may also help in finding solutions with different b(end) consistently provided that the conflict between constraints that I mentioned earlier is not the real issue.

Note that R2014b or later would have new and improved implementations to solve LPs.

Kind Regards,

Derya

Answer 1

[Alan Weiss]

I do not understand it, but perhaps there is a weakness in the simplex algorithm implementation. I suggest that you use the 'dual-simplex' algorithm if you have R2014b or later, or maybe try the 'active-set' algorithm. For the 'active-set' algorithm, you can solve the problem with b(end) = 0, and use that solution as an initial solution x0 to see what else might be going on.

Alan Weiss

MATLAB mathematical toolbox documentation

[Lucas Manuel Genzelis]

I'm using R2013a, so I can't try dual-simplex. Active-set works ok if I supply the solution for b(end)=0 (interior-point, on the other hand, almost never works).

Still, right now this is a matter of curiosity . Perhaps simplex uses some heuristic to determine the feasibility of the problem, and that heuristic is what is failing..

Answer 2

[Matt J]

interior-point, on the other hand, almost never works

My guess is that, regardless of whether b(end)=0 or b(end)=0.001, the region you have specified with your inequality constraints has no interior, or at least not within a safe tolerance for numerical precision errors. Therefore, any success you are observing, even for b(end)=0 is just a numeric fluke.

A simplified example is below, which tries (illegally) to express the region x1=0, -1<=x2<=b(end) using inequality constraint data only. With any b(end)>=-1, the constraints are feasible, but the feasible region also lacks a proper interior (one with non-zero volume in R^2).

    >> A,b

    A =

        -1     0
         0    -1
         1     0
         0     1

    b =

         0
         1
         0
         0