%
% This file (example.m) serves the dual purposes of explaining how to construct
% an Octave program for solving LPs/IPs and it is also an example program
% itself. Read this entire file carefully and you will know how to ask Octave
% to solve "any" LP, IP, or MIP that you construct.
%
% Octave can take a plain text file like this one and execute the commands
% line-by-line as if you were typing them at the Octave prompt. Your program
% files (like this one) must have the extension ".m" and not ".txt" or ".m.txt"
% or anthing else.
%
% To get Octave to run this file, either use octave-online.net or
% (a) place this file in your Octave projects directory (or a subdirectory)
% (b) start Octave
% (c) type "example" (no quotes and no ".m") and hit return
%
% Each line in this file that begins with "%" is a comment line -- it is
% ignored by Octave. All other lines Octave will attempt to execute.
%
% Octave uses the function glpk to solve all LP/IP/MIP problems. For detailed
% help with this function, type "help glpk" at the Octave prompt. You will get
% an explanation of how to properly call the function, the meaning of each
% possible function input variable, and the meaning of each possible output
% variable. The function looks like this:
%
% [xstar,zstar,st,ex]=glpk(c,A,b,lb,ub,ctype,vtype,sense)
%
% The function inputs are to the right enclosed in (). The function outputs
% are to the left enclosed in []. Our job is to define all of the inputs,
% call the function, then observe the outputs. The remainder of this file
% explains how to do this. For this example, we will solve the LP:
%
% max z = w - 2x + y
% s.t. 2w - x + 2y <= 15
% w + x - 3y <= 6
% w,x,y >=0
% w in R
% x,y in Z
%
% First, define each input variable.
%
% c is the column vector of objective function coefficients
c = [1;-2;1];
% Square brackets are used to identify vectors and matrices. Matrices are
% constructed row by row with entries separated by spaces or commas. New
% rows are indicated by semicolons. So the above line specifies that the
% variable c is a column vector of three entries. The semicolon at the end of
% the line prevents Octave from displaying the information to the screen.
%
% A is the matrix of left-hand-side constraint coefficients
A = [ 2 -1 2 ; 1 1 -3];
% b is the column vector of right-hand-side constraint coefficients
b = [15 ; 6];
% lb and ub are lower bound and upper bound constraints on the decision
% variables. This is where we can introduce sign constraints or other more
% general bounds. What we are specifying is that lb <= x <= ub. For the
% example problem we only have 0 <= w,x,y. Thus,
lb = [0;0;0];
ub = [inf;inf;inf];
% Notice that inf (infinity) is a perfectly reasonable variable value. You
% may also use the shorthand:
%
% lb = []; means use a vector of zeros of the correct size
% ub = []; means use a vector of inf's of the correct size
%
% ctype is a variable that declares the type of each of our constraints.
% This variable allows us to use mixed constraint types. For example,
% consider a problem with the following three constraints:
%
% g(x) <= 5
% h(x) >= 4
% j(x) = 3
%
% The A matrix consists of the coefficients in the functions g,h and j. The
% b vector is [5;4;3]. But the constraints are of mixed type. The first is
% an upper bound, the second a lower bound and the last an equality. Octave
% needs this information. We provide this information as a character string
% with the possible entries 'U' (upper bound), 'L' (lower bound) and 'S'
% (equality). For our example, our two constraints are both upper bounds so
% we have the following:
ctype = "UU";
% You may use the traditional double quote mark " or the single vertical
% quote mark ' but not `
%
% Next, we declare the decision variable types. Similarly to the ctype
% variable, we must tell Octave whether each variable is intended to be real
% (that is, continuous) 'C' or integer 'I'. In our example problem the first
% variable is integer, the last two are real (continuous), thus
vtype = "ICC";
% Notice that for ctype and vtype you must use capital letters.
%
% Next, we must tell Octave whether the problem is a max or a min problem.
% We do this with the variable "sense". If we have a min problem then sense=1.
% If we have a max problem then sense=-1. The example problem is a max problem
% thus,
sense = -1;
% We have defined all of our input variables, so all that remains is to call
% the glpk function itself, like this:
[xstar,zstar]=glpk(c,A,b,lb,ub,ctype,vtype,sense);
% Once Octave reaches this line (right here) in executing this file, the
% optimization problem is solved. All that remains is for us to observe the
% output variables.
%
% xstar is the vector of optimal decision variables, x*
% zstar is the scalar optimal objective function value
%
% An alternative to viewing the output is to use the provided function mip.m
% with the very similar call (take out the '%' comment indicator):
% [xstar,zstar]=mip(c,A,b,lb,ub,ctype,vtype,sense,1);
% This function requires that the function ShowResults.m is also in your file
% system.