|
5232
|
1 function varargout=glpk(varargin) |
|
|
2 ## GLPK - An Octave Interface for the GNU GLPK library |
|
|
3 ## |
|
|
4 ## This routine calls the glpk library to solve an LP/MIP problem. A typical |
|
|
5 ## LP problem has following structure: |
|
|
6 ## |
|
|
7 ## [min|max] C'x |
|
|
8 ## s.t. |
|
|
9 ## Ax ["="|"<="|">="] b |
|
|
10 ## {x <= UB} |
|
|
11 ## {x >= LB} |
|
|
12 ## |
|
|
13 ## The calling syntax is: |
|
|
14 ## [XOPT,FOPT,STATUS,EXTRA]=glpkmex(SENSE,C,... |
|
|
15 ## A,B,CTYPE,LB,UB,... |
|
|
16 ## VARTYPE,PARAM,LPSOLVER,SAVE) |
|
|
17 ## |
|
|
18 ## For a quick reference to the syntax just type glpk at command prompt. |
|
|
19 ## |
|
|
20 ## The minimum number of input arguments is 4 (SENSE,C,A,B). In this case we |
|
|
21 ## assume all the constraints are '<=' and all the variables are continuous. |
|
|
22 ## |
|
|
23 ## --- INPUTS --- |
|
|
24 ## |
|
|
25 ## SENSE: indicates whether the problem is a minimization |
|
|
26 ## or maximization problem. |
|
|
27 ## SENSE = 1 minimize |
|
|
28 ## SENSE = -1 maximize. |
|
|
29 ## |
|
|
30 ## C: A column array containing the objective function |
|
|
31 ## coefficients. |
|
|
32 ## |
|
|
33 ## A: A matrix containing the constraints coefficients. |
|
|
34 ## |
|
|
35 ## B: A column array containing the right-hand side value for |
|
|
36 ## each constraint in the constraint matrix. |
|
|
37 ## |
|
|
38 ## CTYPE: A column array containing the sense of each constraint |
|
|
39 ## in the constraint matrix. |
|
|
40 ## CTYPE(i) = 'F' Free (unbounded) variable |
|
|
41 ## CTYPE(i) = 'U' "<=" Variable with upper bound |
|
|
42 ## CTYPE(i) = 'S' "=" Fixed Variable |
|
|
43 ## CTYPE(i) = 'L' ">=" Variable with lower bound |
|
|
44 ## CTYPE(i) = 'D' Double-bounded variable |
|
|
45 ## (This is case sensitive). |
|
|
46 ## |
|
|
47 ## LB: An array of at least length numcols containing the lower |
|
|
48 ## bound on each of the variables. |
|
|
49 ## |
|
|
50 ## UB: An array of at least length numcols containing the upper |
|
|
51 ## bound on each of the variables. |
|
|
52 ## |
|
|
53 ## VARTYPE: A column array containing the types of the variables. |
|
|
54 ## VARTYPE(i) = 'C' continuous variable |
|
|
55 ## VARTYPE(i) = 'I' Integer variable |
|
|
56 ## (This is case sensitive). |
|
|
57 ## |
|
|
58 ## PARAM: A structure containing some parameters used to define |
|
|
59 ## the behavior of solver. For more details type |
|
|
60 ## HELP GLPKPARAMS. |
|
|
61 ## |
|
|
62 ## LPSOLVER: Selects which solver using to solve LP problems. |
|
|
63 ## LPSOLVER=1 Revised Simplex Method |
|
|
64 ## LPSOLVER=2 Interior Point Method |
|
|
65 ## If the problem is a MIP problem this flag will be ignored. |
|
|
66 ## |
|
|
67 ## SAVE: Saves a copy of the problem if SAVE<>0. |
|
|
68 ## The file name can not be specified and defaults to "outpb.lp". |
|
|
69 ## The output file is CPLEX LP format. |
|
|
70 ## |
|
|
71 ## --- OUTPUTS --- |
|
|
72 ## |
|
|
73 ## XOPT: The optimizer. |
|
|
74 ## |
|
|
75 ## FOPT: The optimum. |
|
|
76 ## |
|
|
77 ## STATUS: Status of the optimization. |
|
|
78 ## |
|
|
79 ## - Simplex Method - |
|
|
80 ## Value Code |
|
|
81 ## 180 LPX_OPT solution is optimal |
|
|
82 ## 181 LPX_FEAS solution is feasible |
|
|
83 ## 182 LPX_INFEAS solution is infeasible |
|
|
84 ## 183 LPX_NOFEAS problem has no feasible solution |
|
|
85 ## 184 LPX_UNBND problem has no unbounded solution |
|
|
86 ## 185 LPX_UNDEF solution status is undefined |
|
|
87 ## |
|
|
88 ## - Interior Point Method - |
|
|
89 ## Value Code |
|
|
90 ## 150 LPX_T_UNDEF the interior point method is undefined |
|
|
91 ## 151 LPX_T_OPT the interior point method is optimal |
|
|
92 ## * Note that additional status codes may appear in |
|
|
93 ## the future versions of this routine * |
|
|
94 ## |
|
|
95 ## - Mixed Integer Method - |
|
|
96 ## Value Code |
|
|
97 ## 170 LPX_I_UNDEF the status is undefined |
|
|
98 ## 171 LPX_I_OPT the solution is integer optimal |
|
|
99 ## 172 LPX_I_FEAS solution integer feasible but |
|
|
100 ## its optimality has not been proven |
|
|
101 ## 173 LPX_I_NOFEAS no integer feasible solution |
|
|
102 ## |
|
|
103 ## EXTRA: A data structure containing the following fields: |
|
|
104 ## LAMBDA Dual variables |
|
|
105 ## REDCOSTS Reduced Costs |
|
|
106 ## TIME Time (in seconds) used for solving LP/MIP problem in seconds. |
|
|
107 ## MEM Memory (in bytes) used for solving LP/MIP problem. |
|
|
108 ## |
|
|
109 ## |
|
|
110 ## In case of error the glpkmex returns one of the |
|
|
111 ## following codes (these codes are in STATUS). For more informations on |
|
|
112 ## the causes of these codes refer to the GLPK reference manual. |
|
|
113 ## |
|
|
114 ## Value Code |
|
|
115 ## 204 LPX_E_FAULT unable to start the search |
|
|
116 ## 205 LPX_E_OBJLL objective function lower limit reached |
|
|
117 ## 206 LPX_E_OBJUL objective function upper limit reached |
|
|
118 ## 207 LPX_E_ITLIM iterations limit exhausted |
|
|
119 ## 208 LPX_E_TMLIM time limit exhausted |
|
|
120 ## 209 LPX_E_NOFEAS no feasible solution |
|
|
121 ## 210 LPX_E_INSTAB numerical instability |
|
|
122 ## 211 LPX_E_SING problems with basis matrix |
|
|
123 ## 212 LPX_E_NOCONV no convergence (interior) |
|
|
124 ## 213 LPX_E_NOPFS no primal feas. sol. (LP presolver) |
|
|
125 ## 214 LPX_E_NODFS no dual feas. sol. (LP presolver) |
|
|
126 ## |
|
|
127 |
|
|
128 % --- CODE --- |
|
|
129 % If there is no input output the version and syntax |
|
|
130 if nargin==0 |
|
|
131 printf("glpk: An Octave interface to the GLPK library\n"); |
|
|
132 printf("Version: 1.0\n"); |
|
|
133 printf("\nSyntax: [xopt,fopt,status,extra]=glpk(sense,c,a,b,ctype,lb,ub,vartype,param,lpsolver,save)\n"); |
|
|
134 return; |
|
|
135 endif |
|
|
136 |
|
|
137 % If there are less than 4 arguments output an error message |
|
|
138 if nargin<4 |
|
|
139 error("At least 4 inputs required (sense,c,a,b)\n"); |
|
|
140 return; |
|
|
141 endif |
|
|
142 |
|
|
143 % At least 2 outputs required |
|
|
144 if nargout<2 |
|
|
145 error("2 outputs required\n"); |
|
|
146 return; |
|
|
147 endif |
|
|
148 |
|
|
149 % 1) Sense of optimization |
|
|
150 sense=varargin{1}; |
|
|
151 |
|
|
152 % 2) Cost vector |
|
|
153 c=varargin{2}; |
|
|
154 |
|
|
155 if (all(size(c)>1) | iscomplex(c) | ischar(c)) |
|
|
156 error("C must be a real vector\n"); |
|
|
157 return; |
|
|
158 endif |
|
|
159 nx=length(c); |
|
|
160 if size(c,1) ~= nx |
|
|
161 c=c'; |
|
|
162 endif |
|
|
163 |
|
|
164 % 3) Matrix constraint |
|
|
165 a=varargin{3}; |
|
|
166 if isempty(a) |
|
|
167 error("A cannot be an empty matrix\n"); |
|
|
168 return; |
|
|
169 endif |
|
|
170 [nc, nxa]=size(a); |
|
|
171 if (ischar(a) | iscomplex(a) | (nxa ~= nx)) |
|
|
172 error("A must be a real valued %d by %d matrix\n",nc,nx); |
|
|
173 return; |
|
|
174 endif |
|
|
175 |
|
|
176 % 4) RHS |
|
|
177 b=varargin{4}; |
|
|
178 if isempty(b) |
|
|
179 error("B cannot be an empty vector\n"); |
|
|
180 return; |
|
|
181 endif |
|
|
182 if (ischar(b) | iscomplex(b) | (length(b) ~= nc)) |
|
|
183 error("B must be a real valued %d by 1 vector\n",nc); |
|
|
184 return; |
|
|
185 endif |
|
|
186 |
|
|
187 % 5) Sense of each constraint |
|
|
188 ctype=[]; |
|
|
189 if nargin>4 |
|
|
190 ctype=varargin{5}; |
|
|
191 if isempty(ctype) |
|
|
192 ctype=char('U'*ones(nc,1)); |
|
|
193 elseif (isnumeric(ctype) | all(size(ctype)>1) | (length(ctype) ~= nc)) |
|
|
194 error("CTYPE must be a char valued %d by 1 column vector\n",nc); |
|
|
195 return; |
|
|
196 else |
|
|
197 for i=1:nc |
|
|
198 if (ctype(i)!='F' & ctype(i)!='U' & ctype(i)!='S' & ctype(i)!='L' & ctype(i)!='D') |
|
|
199 error("CTYPE must contain only F,U,S,L and D\n"); |
|
|
200 return; |
|
|
201 endif |
|
|
202 endfor |
|
|
203 endif |
|
|
204 else |
|
|
205 ctype=char('U'*ones(nc,1)); |
|
|
206 end |
|
|
207 |
|
|
208 % 6) Vector with the lower bound of each variable |
|
|
209 lb=[]; |
|
|
210 if nargin>5 |
|
|
211 lb=varargin{6}; |
|
|
212 if isempty(lb) |
|
|
213 lb=-Inf*ones(nx,1); |
|
|
214 elseif (ischar(lb) | iscomplex(lb) | all(size(lb)>1) | (length(lb)~=nx)) |
|
|
215 error("LB must be a real valued %d by 1 column vector\n",nx); |
|
|
216 return; |
|
|
217 endif |
|
|
218 else |
|
|
219 lb=-Inf*ones(nx,1); |
|
|
220 end |
|
|
221 |
|
|
222 % 7) Vector with the upper bound of each variable |
|
|
223 ub=[]; |
|
|
224 if nargin>6 |
|
|
225 ub=varargin{7}; |
|
|
226 if isempty(ub) |
|
|
227 ub=Inf*ones(nx,1); |
|
|
228 elseif (ischar(ub) | iscomplex(ub) | all(size(ub)>1) | (length(ub)~=nx)) |
|
|
229 error("UB must be a real valued %d by 1 column vector\n",nx); |
|
|
230 return; |
|
|
231 endif |
|
|
232 else |
|
|
233 ub=Inf*ones(nx,1); |
|
|
234 end |
|
|
235 |
|
|
236 % 8) Vector with the type of variables |
|
|
237 vartype=[]; |
|
|
238 if nargin>7 |
|
|
239 vartype=varargin{8}; |
|
|
240 if isempty(vartype) |
|
|
241 vartype=char('C'*ones(nx,1)); |
|
|
242 elseif (isnumeric(vartype) | all(size(vartype)>1) | (length(vartype)~=nx)) |
|
|
243 error("VARTYPE must be a char valued %d by 1 column vector\n",nx); |
|
|
244 return; |
|
|
245 else |
|
|
246 for i=1:nx |
|
|
247 if (vartype(i)!='C' & vartype(i)!='I') |
|
|
248 error("VARTYPE must contain only C or I\n"); |
|
|
249 return; |
|
|
250 endif |
|
|
251 endfor |
|
|
252 endif |
|
|
253 else |
|
|
254 vartype=char('C'*ones(nx,1)); % As default we consider continuous vars |
|
|
255 endif |
|
|
256 |
|
|
257 % 9) Parameters vector |
|
|
258 param=[]; |
|
|
259 if nargin>8 |
|
|
260 param=varargin{9}; |
|
|
261 if !isstruct(param) |
|
|
262 error("PARAM must be a structure\n"); |
|
|
263 return; |
|
|
264 endif |
|
|
265 else |
|
|
266 param=struct; |
|
|
267 endif |
|
|
268 |
|
|
269 % 10) Select solver method: simplex or interior point |
|
|
270 lpsolver=[]; |
|
|
271 if nargin>9 |
|
|
272 lpsolver=varargin{10}; |
|
|
273 if (!isnumeric(lpsolver) | all(size(lpsolver)>1)) |
|
|
274 error("LPSOLVER must be a real scalar value\n"); |
|
|
275 return; |
|
|
276 endif |
|
|
277 else |
|
|
278 lpsolver=1; |
|
|
279 endif |
|
|
280 |
|
|
281 % 11) Save the problem |
|
|
282 savepb=[]; |
|
|
283 if nargin>10 |
|
|
284 savepb=varargin{11}; |
|
|
285 if (!isnumeric(savepb) | all(size(savepb)>1)) |
|
|
286 error("LPSOLVER must be a real scalar value\n"); |
|
|
287 return; |
|
|
288 endif |
|
|
289 else |
|
|
290 savepb=0; |
|
|
291 end |
|
|
292 |
|
|
293 if nargin>11 |
|
|
294 warning("Extra parameters ignored\n"); |
|
|
295 endif |
|
|
296 |
|
|
297 try |
|
|
298 [xopt, fmin, status, extra]=glpkoct(sense,c,a,b,ctype,lb,ub,vartype,param,lpsolver,savepb); |
|
|
299 catch |
|
|
300 error("Problems with glpkoct"); |
|
|
301 end_try_catch |
|
|
302 |
|
|
303 varargout{1}=xopt; |
|
|
304 varargout{2}=fmin; |
|
|
305 varargout{3}=status; |
|
|
306 varargout{4}=extra; |
|
|
307 |
|
|
308 |
|
|
309 endfunction |
