% % This file (example.m) serves the dual purposes of explaining how to construct % a Matlab 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 Matlab % to solve "any" LP, IP, or MIP that you construct. % % Matlab can take a plain text file like this one and execute the commands % line-by-line as if you were typing them at the Matlab prompt. Your program % files (like this one) must have the extension ".m" and not ".txt" or ".m.txt" % or anthing else. % % To get Matlab to run this file % (a) place this file in your Matlab projects directory (or a subdirectory) % (b) start Matlab % (c) type "exampleMatlab" (no quotes and no ".m") and hit return % % Each line in this file that begins with "%" is a comment line -- it is % ignored by Matlab. All other lines Matlab will attempt to execute. % % Matlab uses the function intlinprog to solve all LP/IP/MIP problems. For detailed % help with this function, type "help intlinprog" at the Matlab 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]=intlinprog(c,idx,A,b,Ae,be,lb,ub) % % 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 assuming that % the problem is a *minimization* problem. We must solve the related % objective min -z = -w + 2x - y. Thus, 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 Matlab from displaying the information to the screen. % % idx is a list of variable indices that are restricted to be integer % valued. In this problem, the second (x) and third (y) variables are % integer valued, while the first is real valued. idx=[2 3]; % 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]; % Similarly to A and b, Ae and be are matrices associated with any equality % constraints. In our example problem we have no equality constraints so % we can specify Ae=[] and be=[], which tells Matlab that there are no % such constraints. Ae=[]; be=[]; % 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 % % We have defined all of our input variables, so all that remains is to call % the intlinprog function itself, like this: [xstar,zstar]=intlinprog(c,idx,A,b,Ae,be,lb,ub); % Once Matlab 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, z* % % 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.