Is it possible that, given the same problem, fmincon finds a solution and intlinprog does not?

22 Feb 2023
1 Answer
Answer Accepted
Updated 23 Feb 2023
8 Views (30 days)

0 votes

I have a system of inequalities i need to solve and the first step is to understand if a simplified version of this problem, lacking some constraints that involve binary variables, exists. In order to do that i first tried using intlinprog as it was going to be the function to use with the added constraints. No feasible solution is found even after changing the LPPreprocess option to 'none'.
Out of curiosity I tried using fmincon with the exact same matrices and cost function and a feasible solution was found.
Why does this happen? Shouldn't both the functions find a feasible solution when they're fed the same problem data?

4 Comments
Show 2 older comments Hide 2 older comments

John D'Errico
John D'Errico on 22 Feb 2023
Edited: John D'Errico on 22 Feb 2023
fmincon and intlinprog do not solve the same problems. That is, fmincon CANNOT be used to solve a problem with integer variables.
But, assuming that you really do have a problem that can be solved using both tools, then the only way to answer you is if you show the specific problem. Give us code that we can test and verify.
Until then, anything is "possible".
Giosuè Basso
Giosuè Basso on 22 Feb 2023
Edited: Torsten on 22 Feb 2023
Ran in:
Ran in:
The problem I'm giving to both fmincon and intlinprog is just a system of inequalities, no binary variables involved, those are part of a second step.
Here are the matrices involved in the problem:
A =[-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0;
-1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0;
0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0;
0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0;
-1 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0;
0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 0;
0 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0;
0 0 0 0 0 0 0 0 -1 0 0 -1 0 0 0 0;
0 0 0 0 -1 0 0 0 0 -1 0 0 -1 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0;
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0;
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0;
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0;
0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0;
0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0;
1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0;
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0;
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0;
0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0;
0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0;
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0;
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1]
A = 40×16
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 0 0 -1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 0
B = [0;
0;
0;
-3;
0;
-3;
-3;
0;
0;
-3;
0;
-3;
0;
0;
1;
1;
4;
1;
1;
4;
1;
4;
1;
4;
2;
4;
2;
4;
4;
1;
1;
4;
1;
4;
2;
4;
1;
1;
1;
1]
B = 40×1
0 0 0 -3 0 -3 -3 0 0 -3
While the objective function is:
f = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1];
obj = @(x) f*x;
As x(15) and x(16) are additional variables to be minimised in order to make those constraint just < and not <=.
There are no equality constraints, and the solutions must be all >= 0, so the two functions end up being:
solution1 = fmincon(obj,zeros(size(A,2),1),A,B,[],[],zeros(size(A,2),1));
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.201197e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 9.258516e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.680627e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645406e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 4.826966e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645443e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.335809e-18.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645445e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.999469e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645446e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.104341e-19.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.196854e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 8.677267e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.322724e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.452529e-21.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 5.290895e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 6.579687e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645447e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.827224e-22.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 2.645447e-17.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Warning: Matrix is singular to working precision.
Converged to an infeasible point. fmincon stopped because the size of the current step is less than the value of the step size tolerance but constraints are not satisfied to within the value of the constraint tolerance. Consider enabling the interior point method feasibility mode.
solution2 = intlinprog(f',[],A,B,[],[],zeros(size(A,2),1));
No feasible solution found. No integer variables specified. Intlinprog stopped because no point satisfies the constraints.
I'm simply trying to see if A*x <= B has a solution.
I hope I've been exhaustive enough, thanks a lot for helping.
Walter Roberson
Walter Roberson on 22 Feb 2023
I would check whether the fmincon output is a true solution. fmincon uses tolerances to decide whether to terminate, and sometimes proposed parameters get within tolerance but are not true solutions.

Sign in to comment.

Sign in to answer this question.

 Accepted Answer

Matt J
Matt J on 22 Feb 2023
Edited: Matt J on 23 Feb 2023
Ran in:

1 vote

Ran in:
Your constraints are not feasible, as can be seen by looking at inequalities 4,15, and 23.
A=A([4,15,23],:); B=B([4,15,23],:);
[array2table(A), array2table(B)]
ans = 3×17 table
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 B __ __ __ __ __ __ __ __ __ ___ ___ ___ ___ ___ ___ ___ __ -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 -3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1
Equalities 15 and 23 say that x1<=1 and x4<=1, which in turn implies that x1+x4<=2. However, inequality 4 states that x1+x4>=3.
The answer to your question, in this situation, is yes. fmincon can find a solution when the constraint set is empty, but it is an infeasible solution, representing some point fmincon reached in its search for a feasible solution before it gave up. Conversely, intlinprog and linprog will not return an infeasible solution.

More Answers (0)

Categories

Find more on Solver Outputs and Iterative Display in Help Center and File Exchange

Products

Release

R2022b

Tags

Asked:

Giosuè Basso
Giosuè Basso
on 22 Feb 2023

Edited:

Matt J
Matt J
on 23 Feb 2023

Community Treasure Hunt

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

Start Hunting!