Why does the LINPROG function in the Optimization Toolbox exit saying that the problem is infeasible when there definitely is a feasible solution?
5 views (last 30 days)
Show older comments
MathWorks Support Team
on 18 Oct 2013
Edited: MathWorks Support Team
on 12 May 2021
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
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.
0 Comments
More Answers (0)
See Also
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!