CODEWITHSUNDEEP
matlablinear-programming
A Doe
A Doe

Reputation: 301

Matlab linprog yields an unbounded result to a bounded model

clear
A=[-1 0 -1 0; 0 -1 0 -1; 1 1 0 0; 0 0 1 1];
b=[-50 -70 80 45];
f=[0.5; 0.6; 0.4; 0.55];
options = optimoptions('linprog','Algorithm','dual-simplex');
[x,fval,exitflag,output] = linprog(f,A,b,[],[],[],[],options);

Code shown above produces an unbounded result Problem is unbounded where Lindo and Excel Solver find the optimal objective function value which is 62.5

Upvotes: 1

Views: 2075

Answers (2)

sascha
sascha

Reputation: 33532

That's correct behaviour taken into account what matlab's linprog is doing.

The reason for this observation is the following:

  • linprog assumes variables are free ((-inf,inf) if no bound is given) like in your case

Your solution (observed with Lindo) is the one, where your solution-vector is constrained to be nonnegative.

This can be expressed through constraints or using bounds. The docs give the following example:

Example: To specify that all x-components are positive, lb = zeros(size(f))
    # personal opinion: this should be called "nonnegative"

I'm not a Matlab user but using my tools, i can verify that:

  • the problem without the nonnegativity-constraint / or bounds expressing the same is unbounded
  • the problem with the constraint / bounds has a solution of 62.5

Remark: Many mathematical-programming frameworks / solvers assume that the solution-vector is nonnegative by default, which is different from what linprog is doing. The former is a consequence of the underlying algorithmic theory.

Upvotes: 1

Mendi Barel
Mendi Barel

Reputation: 3677

When i run this:

clear
A=[-1 0 -1 0; 0 -1 0 -1; 1 1 0 0; 0 0 1 1];
b=[-50 -70 80 45];
f=[0.5; 0.6; 0.4; 0.55];
options = optimoptions('linprog','Algorithm','simplex','display','iter');
x0=[0 0 0 0]'
[x,fval,exitflag,output] = linprog(f,A,b,[],[],[],[],x0,options);

I get:

Phase 1: Compute initial basic feasible point.
      Iter            Infeasibility
       0                      120
       1                       70
       2                       40
       3                       -0

Phase 2: Minimize using simplex.
      Iter            Objective              Dual Infeasibility 
                        f'*x                   A'*y+z-w-f
       0                   63                    0.111803
       1                 62.5                        0.05
Exiting: The problem is unbounded; the constraints are not restrictive enough.

Same solution as you mentioned.

But nothing prevent from the solver increase x

Upvotes: 0

Related Questions