Try our new documentation site (beta).

Filter Content By
Version

### linprog.m

function [x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
%
%LINPROG A linear programming example using the Gurobi MATLAB interface
%
%   This example is based on the linprog interface defined in the
%   MATLAB Optimization Toolbox. The Optimization Toolbox
%   is a registered trademark of The Math Works, Inc.
%
%   x = LINPROG(f,A,b) solves the linear programming problem:
%
%     minimize     f'*x
%     subject to    A*x <= b.
%
%   For large problems, you can pass A as a sparse matrix and b as a
%   sparse vector.
%
%   x = LINPROG(f,A,b,Aeq,beq) solves the problem:
%
%     minimize     f'*x
%     subject to    A*x <= b,
%                 Aeq*x == beq.
%
%   For large problems, you can pass Aeq as a sparse matrix and beq as a
%   sparse vector. You can set A=[] and b=[] if no inequalities exist.
%
%   x = LINPROG(f,A,b,Aeq,beq,lb,ub) solves the problem:
%
%     minimize     f'*x
%     subject to    A*x <= b,
%                 Aeq*x == beq,
%           lb <=     x <= ub.
%
%   You can set lb(j) = -inf, if x(j) has no lower bound, and ub(j) = inf,
%   if x(j) has no upper bound. You can set Aeq=[] and beq=[] if no
%   equalities exist.
%
%   x = LINPROG(f,A,b,Aeq,beq,lb,ub,OPTIONS) solves the problem above
%   given the specified OPTIONS. Only a subset of possible options have
%   any effect:
%
%     OPTIONS.Display  'off' or 'none' disables output,
%     OPTIONS.MaxTime  time limit in seconds.
%
%   You can set lb=[] or ub=[] if no bounds exist.
%
%   x = LINPROG(PROBLEM) solves PROBLEM, which is a structure that must
%   have solver name 'linprog' in PROBLEM.solver. You can also specify
%   any of the input arguments above using fields PROBLEM.f, PROBLEM.A, ...
%
%   [x,fval] = LINPROG(f,A,b) returns the objective value at the solution.
%   That is, fval = f'*x.
%
%   [x,fval,exitflag] = LINPROG(f,A,b) returns an exitflag containing the
%   status of the optimization. The values for exitflag and the
%   corresponding status codes are:
%
%      1  converged to a solution (OPTIMAL),
%      0  maximum number of iterations reached (ITERATION_LIMIT),
%     -2  no feasible point found (INFEASIBLE, NUMERIC, ...),
%     -3  problem is unbounded (UNBOUNDED).
%
%   [x,fval,exitflag,OUTPUT] = LINPROG(f,A,b) returns information about
%   the optimization. OUTPUT is a structure with the following fields:
%
%     OUTPUT.message          Gurobi status code
%     OUTPUT.constrviolation  maximum violation for constraints and bounds
%
%   [x,fval,exitflag,OUTPUT,LAMBDA] = LINPROG(f,A,b) returns the
%   Lagrangian multipliers at the solution. LAMBDA is a structure with
%   the following fields:
%
%     LAMBDA.lower    multipliers corresponding to x >= lb
%     LAMBDA.upper    multipliers corresponding to x <= ub
%     LAMBDA.ineqlin  multipliers corresponding to A*x <= b
%     LAMBDA.eqlin    multipliers corresponding to Aeq*x == beq
%

% Initialize missing arguments
if nargin == 1
if isa(f,'struct') && isfield(f,'solver') && strcmpi(f.solver,'linprog')
[f,A,b,Aeq,beq,lb,ub,x0,options] = probstruct2args(f);
else
error('PROBLEM should be a structure with valid fields');
end
elseif nargin < 3 || nargin > 9
error('LINPROG: the number of input arguments is wrong');
elseif nargin < 9
options = struct();
if nargin == 8
if isa(x0,'struct') || isa(x0,'optim.options.SolverOptions')
options = x0; % x0 was omitted and options were passed instead
x0 = [];
end
else
x0 = [];
if nargin < 7
ub = [];
if nargin < 6
lb = [];
if nargin < 5
beq = [];
if nargin < 4
Aeq = [];
end
end
end
end
end
end

% Warn user if x0 argument is ignored
if ~isempty(x0)
warning('LINPROG will ignore non-empty starting point X0');
end

% Build Gurobi model
model.obj = f;
model.A = [sparse(A); sparse(Aeq)]; % A must be sparse
model.sense = [repmat('<',size(A,1),1); repmat('=',size(Aeq,1),1)];
model.rhs = full([b(:); beq(:)]); % rhs must be dense
if ~isempty(lb)
model.lb = lb;
else
model.lb = -inf(size(model.A,2),1); % default lb for MATLAB is -inf
end
if ~isempty(ub)
model.ub = ub;
end

% Extract relevant Gurobi parameters from (subset of) options
params = struct();

if isfield(options,'Display') || isa(options,'optim.options.SolverOptions')
if any(strcmp(options.Display,{'off','none'}))
params.OutputFlag = 0;
end
end

if isfield(options,'MaxTime') || isa(options,'optim.options.SolverOptions')
params.TimeLimit = options.MaxTime;
end

% Solve model with Gurobi
result = gurobi(model,params);

% Resolve model if status is INF_OR_UNBD
if strcmp(result.status,'INF_OR_UNBD')
params.DualReductions = 0;
warning('Infeasible or unbounded, resolve without dual reductions to determine...');
result = gurobi(model,params);
end

% Collect results
x = [];
output.message = result.status;
output.constrviolation = [];

if isfield(result,'x')
x = result.x;
if nargout > 3
slack = model.A*x-model.rhs;
violA = slack(1:size(A,1));
violAeq = norm(slack((size(A,1)+1):end),inf);
viollb = model.lb(:)-x;
violub = 0;
if isfield(model,'ub')
violub = x-model.ub(:);
end
output.constrviolation = max([0; violA; violAeq; viollb; violub]);
end
end

fval = [];

if isfield(result,'objval')
fval = result.objval;
end

if strcmp(result.status,'OPTIMAL')
exitflag = 1; % converged to a solution
elseif strcmp(result.status,'UNBOUNDED')
exitflag = -3; % problem is unbounded
elseif strcmp(result.status,'ITERATION_LIMIT')
exitflag = 0; % maximum number of iterations reached
else
exitflag = -2; % no feasible point found
end

lambda.lower = [];
lambda.upper = [];
lambda.ineqlin = [];
lambda.eqlin = [];

if nargout > 4
if isfield(result,'rc')
lambda.lower = max(0,result.rc);
lambda.upper = -min(0,result.rc);
end
if isfield(result,'pi')
if ~isempty(A)
lambda.ineqlin = -result.pi(1:size(A,1));
end
if ~isempty(Aeq)
lambda.eqlin = -result.pi((size(A,1)+1):end);
end
end
end

if isempty(lambda.lower) && isempty(lambda.upper) && ...
isempty(lambda.ineqlin) && isempty(lambda.eqlin)
lambda = [];
end

% Local Functions =========================================================

function [f,A,b,Aeq,beq,lb,ub,x0,options] = probstruct2args(s)
%PROBSTRUCT2ARGS Get problem structure fields ([] is returned when missing)

f = getstructfield(s,'f');
A = getstructfield(s,'Aineq');
b = getstructfield(s,'bineq');
Aeq = getstructfield(s,'Aeq');
beq = getstructfield(s,'beq');
lb = getstructfield(s,'lb');
ub = getstructfield(s,'ub');
x0 = getstructfield(s,'x0');
options = getstructfield(s,'options');

function f = getstructfield(s,field)
%GETSTRUCTFIELD Get structure field ([] is returned when missing)

if isfield(s,field)
f = getfield(s,field);
else
f = [];
end


Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
##### Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.