Having problem with linprog

I have used linprog to solve a large and complex linear programming model. I have also solved the same problem with lingo (a linear programming software).I haven’t gotten the same result from matlab and lingo .I am sure that lingo gave me a better and more optimized result.Although the results from linprog satisfies all the constraints ,it is not optimized results. I thought that the reason may be related to the algorithm that linprog used to solve the problem. In order to have a pure simplex method I have turned off the large scale and turned on the simplex through options. But I got the below warning: Exiting: The constraints are overly stringent; no feasible starting point found And the final result is really far from the first result. Could you suggest me any option to solve the model with linprog or any other commands which give me the optimum result?

Answer 1

[Vidhi Agarwal]

Hi @Leila,

Below are some troubleshooting steps that you can try to resolve the issue:

• Ensure the LP problem passed to linprog is in the correct form:

[x, fval, exitflag, output] = linprog(f, A, b, Aeq, beq, lb, ub, options);

• Instead of the default interior-point or the older simplex, use the modern dual-simplex algorithm, which is usually more robust and efficient for LPs.

options = optimoptions('linprog', 'Algorithm', 'dual-simplex', 'Display', 'iter');
[x, fval, exitflag, output] = linprog(f, A, b, Aeq, beq, lb, ub, options);

• The error usually means that variables A, b, Aeq, beq, lb, ub define a system with no feasible region for that algorithm. Try solving first with "interior-point", which can sometimes find a feasible point more easily:

options = optimoptions('linprog', 'Algorithm', 'interior-point');

• If "interior-point" works and gives a feasible solution then try using that as a starting point for dual-simplex using the "InitialPoint" option.

options = optimoptions('linprog', 'Algorithm', 'dual-simplex', 'Display', 'iter');
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub, x0, options);  % x0 from interior-point

For better understanding of "linprog" refer to the documentation: https://www.mathworks.com/help/optim/ug/linprog.html

Hope that helps!