Basic Linear Optimization with Gnu Octave

https://docs.google.com/document/d/1yygJfTgz3kGGHs0Q9v2wBRBz9OrHAcSLVYIFTG-n3rs/edit?usp=sharing

LinkedIn's editor is not brilliant. Please use the link above for a Google Docs version of this note.

Basic Linear Optimization with Octave

Kwan Lowe

Octave is a handy, high-level language for solving linear and non-linear problems numerically. This note explains how to use Octave to do basic linear optimizations. This is not really a tutorial because the inputs to the glpk() optimization function are self-explanatory but I wanted to show how easy it was.

First, please check out the sample optimization problem here:

https://www.youtube.com/watch?v=2ACJ9ewUC6U

To recap, this is a cost minimization problem with some constraints.

A rancher is mixing two types of food, Brand X and Brand Y. If each serving is required to have 60g of protein and 30g of fat, where Brand X has 15g of protein and 10g of fat and costs 80￠ per unit, and Brand Y contains 20g of protein and 5g of fat and costs 50￠ per unit, how much of each type should be used to minimize the cost to the rancher.

This generates the following equations:

x = Number of units of Brand X

y = Number of units of Brand Y

Cost function:

c = 0.8x + 0.5y

Constraints:

x >= 0

y >= 0

15x + 20y >= 60  (protein)

10x + 5y >= 30  (fat)

We will use the glpk() function in octave which requires the following inputs:

c  

A column array containing the objective function coefficients.

A  

A matrix containing the constraints coefficients.

b

A column array containing the right-hand side value for each constraint in the constraint matrix.

lb

An array containing the lower bound on each of the variables. If lb is not supplied, the default lower bound for the variables is zero.

ub

An array containing the upper bound on each of the variables. If ub is not supplied, the default upper bound is assumed to be infinite.

ctype

An array of characters containing the sense of each constraint in the constraint matrix.

sense

If sense is 1, the problem is a minimization. If sense is -1, the problem is a maximization.

param

Some other options.. Consult the manpage for the details.

We plug each equation into octave by creating matrices of all the inputs. Note that the examples use the single quote character after the matrix definition as a transpose operator. This converts a row vector into a column vector (it's just a little easier to write, apparently).

Our minimization function:

c = 0.8x + 0.5y

[octave]    c = [.8, .5]';

15x + 20y >= 60

10x + 5y >= 30

[octave]    A = [15, 20; 10, 5];

[octave]    b = [60, 30]';

Our constraints:

[octave] lb = [0, 0]';

[octave] ub = [];

The ctype specifies that the constraints are Lower bounds
[octave] ctype = "LL";

The vartype indicates that these are continuous variables (i.e., non-integer):

[octave] vartype = "CC";

The sense tells whether to run a minimization (1) or maximization (-1) problem:

[octave] s = 1;

The param structure sets some miscellaneous options. See the manpage for the full list:

[octave] param.msglev = 1;
[octave] param.itlim = 100;

Now just run the glpk() function against the inputs:

[octave] [xmin, fmin, status, extra] = ...
[octave] glpk (c, A, b, lb, ub, ctype, vartype, s, param);

Once it runs, the outputs are:

[octave]

octave:5> xmin
xmin =

  2.4000
  1.2000
octave:6> fmin
fmin =  2.5200

These are the solutions to the optimization problem. I.e., to minimize the cost to the rancher, 2.4 units of Brand X combined with 1.2 units of Brand Y will cost the least (2.52$) while meeting the constraints.