Why does the LINPROG function in the Optimization Toolbox exit saying that the problem is infeasible when there definitely is a feasible solution?

2 views (last 30 days)
When the large-scale method is used on a problem with a feasible solution, the following error is generated:
ERROR: Exiting: One or more of the residuals, duality gap, or total relative error has stalled:
the primal appears to be infeasible (and the dual unbounded).
(The dual residual < TolFun=1.00e-008.)
The simplex method will solve the problem but is very slow.

Accepted Answer

MathWorks Support Team
MathWorks Support Team on 12 May 2021
Edited: MathWorks Support Team on 12 May 2021
This behavior can occur when the matrix 'Aeq' has linearly dependent constraint rows and the LINPROG solvers do not detect these rows which can cause the algorithms to take an excessively long time to converge or fail to converge at all.
Please refer to the following link for details about linearly dependent vectors:
As a workaround, you can use the active-set algorithm to obtain the indices of the dependent rows. Then you can remove the dependent rows manually to create new matrices 'rAeq' and 'rbeq', which can be solved by LINPROG. To use the active-set Algorithm, set the 'LargeScale' option to 'off' and 'Simplex' to 'off'(default) using the OPTIMSET function.

More Answers (0)

Categories

Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!