Home > matpower6.0 > miqps_glpk.m

miqps_glpk

PURPOSE ^

MIQPS_GLPK Mixed Integer Linear Program Solver based on GLPK - GNU Linear Programming Kit.

SYNOPSIS ^

function [x, f, eflag, output, lambda] = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)

DESCRIPTION ^

MIQPS_GLPK  Mixed Integer Linear Program Solver based on GLPK - GNU Linear Programming Kit.
   [X, F, EXITFLAG, OUTPUT, LAMBDA] = ...
       MIQPS_GLPK(H, C, A, L, U, XMIN, XMAX, X0, OPT)
   A wrapper function providing a MATPOWER standardized interface for using
   GLKP to solve the following LP (linear programming) problem:

       min C'*X
        X

   subject to

       L <= A*X <= U       (linear constraints)
       XMIN <= X <= XMAX   (variable bounds)

   Inputs (all optional except H, C, A and L):
       H : dummy matrix (possibly sparse) of quadratic cost coefficients
           for QP problems, which GLPK does not handle
       C : vector of linear cost coefficients
       A, L, U : define the optional linear constraints. Default
           values for the elements of L and U are -Inf and Inf,
           respectively.
       XMIN, XMAX : optional lower and upper bounds on the
           X variables, defaults are -Inf and Inf, respectively.
       X0 : optional starting value of optimization vector X (NOT USED)
       VTYPE : character string of length NX (number of elements in X),
               or 1 (value applies to all variables in x),
               allowed values are 'C' (continuous), 'B' (binary) or
               'I' (integer).
       OPT : optional options structure with the following fields,
           all of which are also optional (default values shown in
           parentheses)
           verbose (0) - controls level of progress output displayed
               0 = no progress output
               1 = some progress output
               2 = verbose progress output
           skip_prices (0) - flag that specifies whether or not to
               skip the price computation stage, in which the problem
               is re-solved for only the continuous variables, with all
               others being constrained to their solved values
           price_stage_warn_tol (1e-7) - tolerance on the objective fcn
               value and primal variable relative match required to avoid
               mis-match warning message
           glpk_opt - options struct for GLPK, value in
               verbose overrides these options
       PROBLEM : The inputs can alternatively be supplied in a single
           PROBLEM struct with fields corresponding to the input arguments
           described above: H, c, A, l, u, xmin, xmax, x0, vtype, opt

   Outputs:
       X : solution vector
       F : final objective function value
       EXITFLAG : exit flag, 1 - optimal, <= 0 - infeasible, unbounded or other
       OUTPUT : struct with errnum and status fields from GLPK output args
       LAMBDA : struct containing the Langrange and Kuhn-Tucker
           multipliers on the constraints, with fields:
           mu_l - lower (left-hand) limit on linear constraints
           mu_u - upper (right-hand) limit on linear constraints
           lower - lower bound on optimization variables
           upper - upper bound on optimization variables

   Note the calling syntax is almost identical to that of GLPK. The main
   difference is that the linear constraints are specified with A, L, U
   instead of A, B, Aeq, Beq.

   Calling syntax options:
       [x, f, exitflag, output, lambda] = ...
           miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)

       x = miqps_glpk(H, c, A, l, u)
       x = miqps_glpk(H, c, A, l, u, xmin, xmax)
       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0)
       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype)
       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)
       x = miqps_glpk(problem), where problem is a struct with fields:
                       H, c, A, l, u, xmin, xmax, x0, vtype, opt
                       all fields except 'c', 'A' and 'l' or 'u' are optional
       x = miqps_glpk(...)
       [x, f] = miqps_glpk(...)
       [x, f, exitflag] = miqps_glpk(...)
       [x, f, exitflag, output] = miqps_glpk(...)
       [x, f, exitflag, output, lambda] = miqps_glpk(...)


   Example: (problem from from http://www.jmu.edu/docs/sasdoc/sashtml/iml/chap8/sect12.htm)
       H = [   1003.1  4.3     6.3     5.9;
               4.3     2.2     2.1     3.9;
               6.3     2.1     3.5     4.8;
               5.9     3.9     4.8     10  ];
       c = zeros(4,1);
       A = [   1       1       1       1;
               0.17    0.11    0.10    0.18    ];
       l = [1; 0.10];
       u = [1; Inf];
       xmin = zeros(4,1);
       x0 = [1; 0; 0; 1];
       opt = struct('verbose', 2);
       [x, f, s, out, lambda] = miqps_glpk(H, c, A, l, u, xmin, [], x0, vtype, opt);

   See also GLPK.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [x, f, eflag, output, lambda] = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)
0002 %MIQPS_GLPK  Mixed Integer Linear Program Solver based on GLPK - GNU Linear Programming Kit.
0003 %   [X, F, EXITFLAG, OUTPUT, LAMBDA] = ...
0004 %       MIQPS_GLPK(H, C, A, L, U, XMIN, XMAX, X0, OPT)
0005 %   A wrapper function providing a MATPOWER standardized interface for using
0006 %   GLKP to solve the following LP (linear programming) problem:
0007 %
0008 %       min C'*X
0009 %        X
0010 %
0011 %   subject to
0012 %
0013 %       L <= A*X <= U       (linear constraints)
0014 %       XMIN <= X <= XMAX   (variable bounds)
0015 %
0016 %   Inputs (all optional except H, C, A and L):
0017 %       H : dummy matrix (possibly sparse) of quadratic cost coefficients
0018 %           for QP problems, which GLPK does not handle
0019 %       C : vector of linear cost coefficients
0020 %       A, L, U : define the optional linear constraints. Default
0021 %           values for the elements of L and U are -Inf and Inf,
0022 %           respectively.
0023 %       XMIN, XMAX : optional lower and upper bounds on the
0024 %           X variables, defaults are -Inf and Inf, respectively.
0025 %       X0 : optional starting value of optimization vector X (NOT USED)
0026 %       VTYPE : character string of length NX (number of elements in X),
0027 %               or 1 (value applies to all variables in x),
0028 %               allowed values are 'C' (continuous), 'B' (binary) or
0029 %               'I' (integer).
0030 %       OPT : optional options structure with the following fields,
0031 %           all of which are also optional (default values shown in
0032 %           parentheses)
0033 %           verbose (0) - controls level of progress output displayed
0034 %               0 = no progress output
0035 %               1 = some progress output
0036 %               2 = verbose progress output
0037 %           skip_prices (0) - flag that specifies whether or not to
0038 %               skip the price computation stage, in which the problem
0039 %               is re-solved for only the continuous variables, with all
0040 %               others being constrained to their solved values
0041 %           price_stage_warn_tol (1e-7) - tolerance on the objective fcn
0042 %               value and primal variable relative match required to avoid
0043 %               mis-match warning message
0044 %           glpk_opt - options struct for GLPK, value in
0045 %               verbose overrides these options
0046 %       PROBLEM : The inputs can alternatively be supplied in a single
0047 %           PROBLEM struct with fields corresponding to the input arguments
0048 %           described above: H, c, A, l, u, xmin, xmax, x0, vtype, opt
0049 %
0050 %   Outputs:
0051 %       X : solution vector
0052 %       F : final objective function value
0053 %       EXITFLAG : exit flag, 1 - optimal, <= 0 - infeasible, unbounded or other
0054 %       OUTPUT : struct with errnum and status fields from GLPK output args
0055 %       LAMBDA : struct containing the Langrange and Kuhn-Tucker
0056 %           multipliers on the constraints, with fields:
0057 %           mu_l - lower (left-hand) limit on linear constraints
0058 %           mu_u - upper (right-hand) limit on linear constraints
0059 %           lower - lower bound on optimization variables
0060 %           upper - upper bound on optimization variables
0061 %
0062 %   Note the calling syntax is almost identical to that of GLPK. The main
0063 %   difference is that the linear constraints are specified with A, L, U
0064 %   instead of A, B, Aeq, Beq.
0065 %
0066 %   Calling syntax options:
0067 %       [x, f, exitflag, output, lambda] = ...
0068 %           miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)
0069 %
0070 %       x = miqps_glpk(H, c, A, l, u)
0071 %       x = miqps_glpk(H, c, A, l, u, xmin, xmax)
0072 %       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0)
0073 %       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype)
0074 %       x = miqps_glpk(H, c, A, l, u, xmin, xmax, x0, vtype, opt)
0075 %       x = miqps_glpk(problem), where problem is a struct with fields:
0076 %                       H, c, A, l, u, xmin, xmax, x0, vtype, opt
0077 %                       all fields except 'c', 'A' and 'l' or 'u' are optional
0078 %       x = miqps_glpk(...)
0079 %       [x, f] = miqps_glpk(...)
0080 %       [x, f, exitflag] = miqps_glpk(...)
0081 %       [x, f, exitflag, output] = miqps_glpk(...)
0082 %       [x, f, exitflag, output, lambda] = miqps_glpk(...)
0083 %
0084 %
0085 %   Example: (problem from from http://www.jmu.edu/docs/sasdoc/sashtml/iml/chap8/sect12.htm)
0086 %       H = [   1003.1  4.3     6.3     5.9;
0087 %               4.3     2.2     2.1     3.9;
0088 %               6.3     2.1     3.5     4.8;
0089 %               5.9     3.9     4.8     10  ];
0090 %       c = zeros(4,1);
0091 %       A = [   1       1       1       1;
0092 %               0.17    0.11    0.10    0.18    ];
0093 %       l = [1; 0.10];
0094 %       u = [1; Inf];
0095 %       xmin = zeros(4,1);
0096 %       x0 = [1; 0; 0; 1];
0097 %       opt = struct('verbose', 2);
0098 %       [x, f, s, out, lambda] = miqps_glpk(H, c, A, l, u, xmin, [], x0, vtype, opt);
0099 %
0100 %   See also GLPK.
0101 
0102 %   MATPOWER
0103 %   Copyright (c) 2010-2016, Power Systems Engineering Research Center (PSERC)
0104 %   by Ray Zimmerman, PSERC Cornell
0105 %
0106 %   This file is part of MATPOWER.
0107 %   Covered by the 3-clause BSD License (see LICENSE file for details).
0108 %   See http://www.pserc.cornell.edu/matpower/ for more info.
0109 
0110 %% check for Optimization Toolbox
0111 % if ~have_fcn('quadprog')
0112 %     error('miqps_glpk: requires the MEX interface to GLPK');
0113 % end
0114 
0115 %%----- input argument handling  -----
0116 %% gather inputs
0117 if nargin == 1 && isstruct(H)       %% problem struct
0118     p = H;
0119     if isfield(p, 'opt'),   opt = p.opt;    else,   opt = [];   end
0120     if isfield(p, 'vtype'), vtype = p.vtype;else,   vtype = []; end
0121     if isfield(p, 'x0'),    x0 = p.x0;      else,   x0 = [];    end
0122     if isfield(p, 'xmax'),  xmax = p.xmax;  else,   xmax = [];  end
0123     if isfield(p, 'xmin'),  xmin = p.xmin;  else,   xmin = [];  end
0124     if isfield(p, 'u'),     u = p.u;        else,   u = [];     end
0125     if isfield(p, 'l'),     l = p.l;        else,   l = [];     end
0126     if isfield(p, 'A'),     A = p.A;        else,   A = [];     end
0127     if isfield(p, 'c'),     c = p.c;        else,   c = [];     end
0128     if isfield(p, 'H'),     H = p.H;        else,   H = [];     end
0129 else                                %% individual args
0130     if nargin < 10
0131         opt = [];
0132         if nargin < 9
0133             vtype = [];
0134             if nargin < 8
0135                 x0 = [];
0136                 if nargin < 7
0137                     xmax = [];
0138                     if nargin < 6
0139                         xmin = [];
0140                     end
0141                 end
0142             end
0143         end
0144     end
0145 end
0146 
0147 %% define nx, set default values for missing optional inputs
0148 if isempty(H) || ~any(any(H))
0149     if isempty(A) && isempty(xmin) && isempty(xmax)
0150         error('miqps_glpk: LP problem must include constraints or variable bounds');
0151     else
0152         if ~isempty(A)
0153             nx = size(A, 2);
0154         elseif ~isempty(xmin)
0155             nx = length(xmin);
0156         else    % if ~isempty(xmax)
0157             nx = length(xmax);
0158         end
0159     end
0160 else
0161     error('miqps_glpk: GLPK handles only LP problems, not QP problems');
0162     nx = size(H, 1);
0163 end
0164 if isempty(c)
0165     c = zeros(nx, 1);
0166 end
0167 if isempty(A) || (~isempty(A) && (isempty(l) || all(l == -Inf)) && ...
0168                                  (isempty(u) || all(u == Inf)))
0169     A = sparse(0,nx);           %% no limits => no linear constraints
0170 end
0171 nA = size(A, 1);                %% number of original linear constraints
0172 if isempty(u)                   %% By default, linear inequalities are ...
0173     u = Inf(nA, 1);             %% ... unbounded above and ...
0174 end
0175 if isempty(l)
0176     l = -Inf(nA, 1);            %% ... unbounded below.
0177 end
0178 if isempty(xmin)                %% By default, optimization variables are ...
0179     xmin = -Inf(nx, 1);         %% ... unbounded below and ...
0180 end
0181 if isempty(xmax)
0182     xmax = Inf(nx, 1);          %% ... unbounded above.
0183 end
0184 if isempty(x0)
0185     x0 = zeros(nx, 1);
0186 end
0187 
0188 %% default options
0189 if ~isempty(opt) && isfield(opt, 'verbose') && ~isempty(opt.verbose)
0190     verbose = opt.verbose;
0191 else
0192     verbose = 0;
0193 end
0194 
0195 %% split up linear constraints
0196 ieq = find( abs(u-l) <= eps );          %% equality
0197 igt = find( u >=  1e10 & l > -1e10 );   %% greater than, unbounded above
0198 ilt = find( l <= -1e10 & u <  1e10 );   %% less than, unbounded below
0199 ibx = find( (abs(u-l) > eps) & (u < 1e10) & (l > -1e10) );
0200 AA = [ A(ieq, :); A(ilt, :); -A(igt, :); A(ibx, :); -A(ibx, :) ];
0201 bb = [ u(ieq);    u(ilt);    -l(igt);    u(ibx);    -l(ibx)];
0202 
0203 %% grab some dimensions
0204 nlt = length(ilt);      %% number of upper bounded linear inequalities
0205 ngt = length(igt);      %% number of lower bounded linear inequalities
0206 nbx = length(ibx);      %% number of doubly bounded linear inequalities
0207 neq = length(ieq);      %% number of equalities
0208 nie = nlt+ngt+2*nbx;    %% number of inequalities
0209 
0210 ctype = [repmat('S', neq, 1); repmat('U', nlt+ngt+2*nbx, 1)];
0211 
0212 if isempty(vtype) || isempty(find(vtype == 'B' | vtype == 'I'))
0213     mi = 0;
0214     vtype = repmat('C', nx, 1);
0215 else
0216     mi = 1;
0217     %% expand vtype to nx elements if necessary
0218     if length(vtype) == 1 && nx > 1
0219         vtype = char(vtype * ones(nx, 1));
0220     elseif size(vtype, 2) > 1   %% make sure it's a col vector
0221         vtype = vtype';
0222     end
0223 end
0224 %% convert 'B' variables to 'I' and clip bounds to [0, 1]
0225 k = find(vtype == 'B');
0226 if ~isempty(k)
0227     kk = find(xmax(k) > 1);
0228     xmax(k(kk)) = 1;
0229     kk = find(xmin(k) < 0);
0230     xmin(k(kk)) = 0;
0231     vtype(k) = 'I';
0232 end
0233 
0234 %% set options struct for GLPK
0235 if ~isempty(opt) && isfield(opt, 'glpk_opt') && ~isempty(opt.glpk_opt)
0236     glpk_opt = glpk_options(opt.glpk_opt);
0237 else
0238     glpk_opt = glpk_options;
0239 end
0240 glpk_opt.msglev = verbose;
0241 
0242 %% call the solver
0243 [x, f, errnum, extra] = ...
0244     glpk(c, AA, bb, xmin, xmax, ctype, vtype, 1, glpk_opt);
0245 
0246 %% set exit flag
0247 if isfield(extra, 'status')             %% status found in extra.status
0248     output.errnum = errnum;
0249     output.status = extra.status;
0250     eflag = -errnum;
0251     if eflag == 0 && extra.status == 5
0252         eflag = 1;
0253     end
0254 else                                    %% status found in errnum
0255     output.errnum = [];
0256     output.status = errnum;
0257     if have_fcn('octave')
0258         if errnum == 180 || errnum == 151 || errnum == 171
0259             eflag = 1;
0260         else
0261             eflag = 0;
0262         end
0263     else
0264         if errnum == 5
0265             eflag = 1;
0266         else
0267             eflag = 0;
0268         end
0269     end
0270 end
0271 
0272 %% repackage lambdas
0273 if isempty(extra) || ~isfield(extra, 'lambda') || isempty(extra.lambda)
0274     lambda = struct( ...
0275         'mu_l', zeros(nA, 1), ...
0276         'mu_u', zeros(nA, 1), ...
0277         'lower', zeros(nx, 1), ...
0278         'upper', zeros(nx, 1) ...
0279     );
0280 else
0281     lam.eqlin = extra.lambda(1:neq);
0282     lam.ineqlin = extra.lambda(neq+(1:nie));
0283     lam.lower = extra.redcosts;
0284     lam.upper = -extra.redcosts;
0285     lam.lower(lam.lower < 0) = 0;
0286     lam.upper(lam.upper < 0) = 0;
0287     kl = find(lam.eqlin > 0);   %% lower bound binding
0288     ku = find(lam.eqlin < 0);   %% upper bound binding
0289 
0290     mu_l = zeros(nA, 1);
0291     mu_l(ieq(kl)) = lam.eqlin(kl);
0292     mu_l(igt) = -lam.ineqlin(nlt+(1:ngt));
0293     mu_l(ibx) = -lam.ineqlin(nlt+ngt+nbx+(1:nbx));
0294 
0295     mu_u = zeros(nA, 1);
0296     mu_u(ieq(ku)) = -lam.eqlin(ku);
0297     mu_u(ilt) = -lam.ineqlin(1:nlt);
0298     mu_u(ibx) = -lam.ineqlin(nlt+ngt+(1:nbx));
0299 
0300     lambda = struct( ...
0301         'mu_l', mu_l, ...
0302         'mu_u', mu_u, ...
0303         'lower', lam.lower(1:nx), ...
0304         'upper', lam.upper(1:nx) ...
0305     );
0306 end
0307 
0308 if mi && eflag == 1 && (~isfield(opt, 'skip_prices') || ~opt.skip_prices)
0309     if verbose
0310         fprintf('--- Integer stage complete, starting price computation stage ---\n');
0311     end
0312     if isfield(opt, 'price_stage_warn_tol') && ~isempty(opt.price_stage_warn_tol)
0313         tol = opt.price_stage_warn_tol;
0314     else
0315         tol = 1e-7;
0316     end
0317     k = find(vtype == 'I' | vtype == 'B');
0318     x(k) = round(x(k));
0319     xmin(k) = x(k);
0320     xmax(k) = x(k);
0321     x0 = x;
0322     opt.glpk_opt.lpsolver = 1;      %% simplex
0323     opt.glpk_opt.dual = 0;          %% primal simplex
0324     if have_fcn('octave') && have_fcn('octave', 'vnum') >= 3.007
0325         opt.glpk_opt.dual = 1;      %% primal simplex
0326     end
0327     
0328     [x_, f_, eflag_, output_, lambda] = qps_glpk(H, c, A, l, u, xmin, xmax, x0, opt);
0329     if eflag ~= eflag_
0330         error('miqps_glpk: EXITFLAG from price computation stage = %d', eflag_);
0331     end
0332     if abs(f - f_)/max(abs(f), 1) > tol
0333         warning('miqps_glpk: relative mismatch in objective function value from price computation stage = %g', abs(f - f_)/max(abs(f), 1));
0334     end
0335     xn = x;
0336     xn(abs(xn)<1) = 1;
0337     [mx, k] = max(abs(x - x_) ./ xn);
0338     if mx > tol
0339         warning('miqps_glpk: max relative mismatch in x from price computation stage = %g (%g)', mx, x(k));
0340     end
0341     output.price_stage = output_;
0342 end

Generated on Fri 16-Dec-2016 12:45:37 by m2html © 2005