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

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?

[John D'Errico]

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]

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]

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.

[Torsten]

I don't see that fmincon succeeds (see above).

Answer 1

[Matt J]

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.