|
5233
|
1 ## Copyright (C) 2005 Nicolo' Giorgetti |
|
|
2 ## |
|
|
3 ## This file is part of Octave. |
|
|
4 ## |
|
|
5 ## Octave is free software; you can redistribute it and/or modify it |
|
|
6 ## under the terms of the GNU General Public License as published by |
|
|
7 ## the Free Software Foundation; either version 2, or (at your option) |
|
|
8 ## any later version. |
|
|
9 ## |
|
|
10 ## Octave is distributed in the hope that it will be useful, but |
|
|
11 ## WITHOUT ANY WARRANTY; without even the implied warranty of |
|
|
12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
|
13 ## General Public License for more details. |
|
|
14 ## |
|
|
15 ## You should have received a copy of the GNU General Public License |
|
|
16 ## along with Octave; see the file COPYING. If not, write to the Free |
|
|
17 ## Software Foundation, 59 Temple Place - Suite 330, Boston, MA |
|
|
18 ## 02111-1307, USA. |
|
|
19 |
|
5232
|
20 ## GLPK - An Octave Interface for the GNU GLPK library |
|
|
21 ## |
|
5237
|
22 ## This routine calls the glpk library to solve an LP/MIP problem. By |
|
|
23 ## default, glpk solves the following standard LP: |
|
|
24 ## |
|
|
25 ## min C'*x |
|
|
26 ## |
|
|
27 ## subject to |
|
|
28 ## |
|
|
29 ## A*x = b |
|
|
30 ## x >= 0 |
|
5232
|
31 ## |
|
5237
|
32 ## but may also solve problems of the form |
|
|
33 ## |
|
|
34 ## [min|max] C'x |
|
|
35 ## |
|
|
36 ## subject to |
|
|
37 ## |
|
|
38 ## Ax ["="|"<="|">="] b |
|
|
39 ## {x <= UB} |
|
|
40 ## {x >= LB} |
|
5232
|
41 ## |
|
|
42 ## The calling syntax is: |
|
5237
|
43 ## [XOPT,FOPT,STATUS,EXTRA]=glpk(C,A,B,LB,UB,CTYPE,VARTYPE,SENSE,PARAM) |
|
5232
|
44 ## |
|
|
45 ## For a quick reference to the syntax just type glpk at command prompt. |
|
|
46 ## |
|
|
47 ## The minimum number of input arguments is 4 (SENSE,C,A,B). In this case we |
|
|
48 ## assume all the constraints are '<=' and all the variables are continuous. |
|
|
49 ## |
|
|
50 ## --- INPUTS --- |
|
|
51 ## |
|
|
52 ## C: A column array containing the objective function |
|
|
53 ## coefficients. |
|
|
54 ## |
|
|
55 ## A: A matrix containing the constraints coefficients. |
|
|
56 ## |
|
|
57 ## B: A column array containing the right-hand side value for |
|
|
58 ## each constraint in the constraint matrix. |
|
|
59 ## |
|
5237
|
60 ## LB: An array of at least length numcols containing the lower |
|
|
61 ## bound on each of the variables. |
|
|
62 ## |
|
|
63 ## UB: An array of at least length numcols containing the upper |
|
|
64 ## bound on each of the variables. |
|
|
65 ## |
|
5232
|
66 ## CTYPE: A column array containing the sense of each constraint |
|
|
67 ## in the constraint matrix. |
|
|
68 ## CTYPE(i) = 'F' Free (unbounded) variable |
|
|
69 ## CTYPE(i) = 'U' "<=" Variable with upper bound |
|
|
70 ## CTYPE(i) = 'S' "=" Fixed Variable |
|
|
71 ## CTYPE(i) = 'L' ">=" Variable with lower bound |
|
|
72 ## CTYPE(i) = 'D' Double-bounded variable |
|
|
73 ## (This is case sensitive). |
|
|
74 ## |
|
|
75 ## VARTYPE: A column array containing the types of the variables. |
|
|
76 ## VARTYPE(i) = 'C' continuous variable |
|
|
77 ## VARTYPE(i) = 'I' Integer variable |
|
|
78 ## (This is case sensitive). |
|
|
79 ## |
|
5237
|
80 ## SENSE: indicates whether the problem is a minimization |
|
|
81 ## or maximization problem. |
|
|
82 ## SENSE = 1 minimize |
|
|
83 ## SENSE = -1 maximize. |
|
|
84 ## |
|
5232
|
85 ## PARAM: A structure containing some parameters used to define |
|
|
86 ## the behavior of solver. For more details type |
|
|
87 ## HELP GLPKPARAMS. |
|
|
88 ## |
|
|
89 ## --- OUTPUTS --- |
|
|
90 ## |
|
|
91 ## XOPT: The optimizer. |
|
|
92 ## |
|
|
93 ## FOPT: The optimum. |
|
|
94 ## |
|
|
95 ## STATUS: Status of the optimization. |
|
5233
|
96 ## |
|
5232
|
97 ## - Simplex Method - |
|
5233
|
98 ## Value Code |
|
|
99 ## 180 LPX_OPT solution is optimal |
|
5232
|
100 ## 181 LPX_FEAS solution is feasible |
|
|
101 ## 182 LPX_INFEAS solution is infeasible |
|
|
102 ## 183 LPX_NOFEAS problem has no feasible solution |
|
|
103 ## 184 LPX_UNBND problem has no unbounded solution |
|
|
104 ## 185 LPX_UNDEF solution status is undefined |
|
|
105 ## |
|
|
106 ## - Interior Point Method - |
|
|
107 ## Value Code |
|
|
108 ## 150 LPX_T_UNDEF the interior point method is undefined |
|
|
109 ## 151 LPX_T_OPT the interior point method is optimal |
|
|
110 ## * Note that additional status codes may appear in |
|
|
111 ## the future versions of this routine * |
|
5233
|
112 ## |
|
5232
|
113 ## - Mixed Integer Method - |
|
|
114 ## Value Code |
|
|
115 ## 170 LPX_I_UNDEF the status is undefined |
|
|
116 ## 171 LPX_I_OPT the solution is integer optimal |
|
|
117 ## 172 LPX_I_FEAS solution integer feasible but |
|
|
118 ## its optimality has not been proven |
|
|
119 ## 173 LPX_I_NOFEAS no integer feasible solution |
|
5233
|
120 ## |
|
5232
|
121 ## EXTRA: A data structure containing the following fields: |
|
|
122 ## LAMBDA Dual variables |
|
|
123 ## REDCOSTS Reduced Costs |
|
|
124 ## TIME Time (in seconds) used for solving LP/MIP problem in seconds. |
|
|
125 ## MEM Memory (in bytes) used for solving LP/MIP problem. |
|
|
126 ## |
|
|
127 ## |
|
5233
|
128 ## In case of error the glpk returns one of the |
|
5232
|
129 ## following codes (these codes are in STATUS). For more informations on |
|
|
130 ## the causes of these codes refer to the GLPK reference manual. |
|
|
131 ## |
|
|
132 ## Value Code |
|
|
133 ## 204 LPX_E_FAULT unable to start the search |
|
|
134 ## 205 LPX_E_OBJLL objective function lower limit reached |
|
|
135 ## 206 LPX_E_OBJUL objective function upper limit reached |
|
|
136 ## 207 LPX_E_ITLIM iterations limit exhausted |
|
|
137 ## 208 LPX_E_TMLIM time limit exhausted |
|
|
138 ## 209 LPX_E_NOFEAS no feasible solution |
|
|
139 ## 210 LPX_E_INSTAB numerical instability |
|
|
140 ## 211 LPX_E_SING problems with basis matrix |
|
|
141 ## 212 LPX_E_NOCONV no convergence (interior) |
|
|
142 ## 213 LPX_E_NOPFS no primal feas. sol. (LP presolver) |
|
|
143 ## 214 LPX_E_NODFS no dual feas. sol. (LP presolver) |
|
|
144 |
|
5233
|
145 ## Author: Nicolo' Giorgetti <giorgetti@dii.unisi.it> |
|
|
146 ## Adapted-by: jwe |
|
5232
|
147 |
|
5237
|
148 function [xopt, fmin, status, extra] = glpk (c, a, b, lb, ub, ctype, vartype, sense, param) |
|
5232
|
149 |
|
5233
|
150 ## If there is no input output the version and syntax |
|
5237
|
151 if (nargin < 3 || nargin > 9) |
|
|
152 usage ("[xopt, fopt, status, extra] = glpk (c, a, b, lb, ub, ctype, vartype, sense, param)"); |
|
5233
|
153 return; |
|
|
154 endif |
|
5232
|
155 |
|
5233
|
156 if (all (size (c) > 1) || iscomplex (c) || ischar (c)) |
|
|
157 error ("C must be a real vector"); |
|
|
158 return; |
|
|
159 endif |
|
|
160 nx = length (c); |
|
|
161 ## Force column vector. |
|
|
162 c = c(:); |
|
5232
|
163 |
|
5237
|
164 ## 2) Matrix constraint |
|
5232
|
165 |
|
5233
|
166 if (isempty (a)) |
|
|
167 error ("A cannot be an empty matrix"); |
|
|
168 return; |
|
|
169 endif |
|
|
170 [nc, nxa] = size(a); |
|
|
171 if (! isreal (a) || nxa != nx) |
|
|
172 error ("A must be a real valued %d by %d matrix", nc, nx); |
|
|
173 return; |
|
|
174 endif |
|
|
175 |
|
5237
|
176 ## 3) RHS |
|
5232
|
177 |
|
5233
|
178 if (isempty (b)) |
|
|
179 error ("B cannot be an empty vector"); |
|
|
180 return; |
|
|
181 endif |
|
|
182 if (! isreal (b) || length (b) != nc) |
|
|
183 error ("B must be a real valued %d by 1 vector", nc); |
|
|
184 return; |
|
|
185 endif |
|
|
186 |
|
5237
|
187 ## 4) Vector with the lower bound of each variable |
|
5232
|
188 |
|
5237
|
189 if (nargin > 3) |
|
5233
|
190 if (isempty (lb)) |
|
5237
|
191 lb = zeros (0, nx, 1); |
|
5233
|
192 elseif (! isreal (lb) || all (size (lb) > 1) || length (lb) != nx) |
|
|
193 error ("LB must be a real valued %d by 1 column vector", nx); |
|
|
194 return; |
|
|
195 endif |
|
|
196 else |
|
5237
|
197 lb = zeros (nx, 1); |
|
5233
|
198 end |
|
|
199 |
|
5237
|
200 ## 5) Vector with the upper bound of each variable |
|
5232
|
201 |
|
5237
|
202 if (nargin > 4) |
|
5233
|
203 if (isempty (ub)) |
|
|
204 ub = repmat (Inf, nx, 1); |
|
|
205 elseif (! isreal (ub) || all (size (ub) > 1) || length (ub) != nx) |
|
|
206 error ("UB must be a real valued %d by 1 column vector", nx); |
|
|
207 return; |
|
|
208 endif |
|
|
209 else |
|
|
210 ub = repmat (Inf, nx, 1); |
|
|
211 end |
|
5232
|
212 |
|
5237
|
213 ## 6) Sense of each constraint |
|
5232
|
214 |
|
5237
|
215 if (nargin > 5) |
|
|
216 if (isempty (ctype)) |
|
|
217 ctype = repmat ("S", nc, 1); |
|
|
218 elseif (! ischar (ctype) || all (size (ctype) > 1) || length (ctype) != nc) |
|
|
219 error ("CTYPE must be a char valued %d by 1 column vector", nc); |
|
|
220 return; |
|
|
221 elseif (! all (ctype == "F" | ctype == "U" | ctype == "S" |
|
|
222 | ctype == "L" | ctype == "D")) |
|
|
223 error ("CTYPE must contain only F, U, S, L, or D"); |
|
|
224 return; |
|
|
225 endif |
|
|
226 else |
|
|
227 ctype = repmat ("S", nc, 1); |
|
|
228 end |
|
|
229 |
|
|
230 ## 7) Vector with the type of variables |
|
|
231 |
|
|
232 if (nargin > 6) |
|
5233
|
233 if isempty (vartype) |
|
|
234 vartype = repmat ("C", nx, 1); |
|
|
235 elseif (! ischar (vartype) || all (size (vartype) > 1) |
|
|
236 || length (vartype) != nx) |
|
|
237 error ("VARTYPE must be a char valued %d by 1 column vector", nx); |
|
|
238 return; |
|
|
239 elseif (! all (vartype == "C" | vartype == "I")) |
|
|
240 error ("VARTYPE must contain only C or I"); |
|
|
241 return; |
|
|
242 endif |
|
|
243 else |
|
|
244 ## As default we consider continuous vars |
|
|
245 vartype = repmat ("C", nx, 1); |
|
|
246 endif |
|
5232
|
247 |
|
5237
|
248 ## 8) Parameters vector |
|
5233
|
249 |
|
|
250 if (nargin > 8) |
|
|
251 if (! isstruct (param)) |
|
|
252 error ("PARAM must be a structure"); |
|
|
253 return; |
|
|
254 endif |
|
|
255 else |
|
|
256 param = struct (); |
|
|
257 endif |
|
5232
|
258 |
|
5233
|
259 [xopt, fmin, status, extra] = ... |
|
5237
|
260 __glpk__ (c, a, b, lb, ub, ctype, vartype, sense, param); |
|
5232
|
261 |
|
|
262 endfunction |
