1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
|
<html lang="en">
<head>
<title>Linear Programming - Untitled</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="Untitled">
<meta name="generator" content="makeinfo 4.11">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Optimization.html#Optimization" title="Optimization">
<link rel="next" href="Quadratic-Programming.html#Quadratic-Programming" title="Quadratic Programming">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="Linear-Programming"></a>
Next: <a rel="next" accesskey="n" href="Quadratic-Programming.html#Quadratic-Programming">Quadratic Programming</a>,
Up: <a rel="up" accesskey="u" href="Optimization.html#Optimization">Optimization</a>
<hr>
</div>
<h3 class="section">24.1 Linear Programming</h3>
<p>Octave can solve Linear Programming problems using the <code>glpk</code>
function. That is, Octave can solve
<pre class="example"> min C'*x
</pre>
<p>subject to the linear constraints
A*x = b where x >= 0.
<p class="noindent">The <code>glpk</code> function also supports variations of this problem.
<!-- ./optimization/glpk.m -->
<p><a name="doc_002dglpk"></a>
<div class="defun">
— Function File: [<var>xopt</var>, <var>fmin</var>, <var>status</var>, <var>extra</var>] = <b>glpk</b> (<var>c, a, b, lb, ub, ctype, vartype, sense, param</var>)<var><a name="index-glpk-1801"></a></var><br>
<blockquote><p>Solve a linear program using the GNU GLPK library. Given three
arguments, <code>glpk</code> solves the following standard LP:
<pre class="example"> min C'*x
</pre>
<p>subject to
<pre class="example"> A*x = b
x >= 0
</pre>
<p>but may also solve problems of the form
<pre class="example"> [ min | max ] C'*x
</pre>
<p>subject to
<pre class="example"> A*x [ "=" | "<=" | ">=" ] b
x >= LB
x <= UB
</pre>
<p>Input arguments:
<dl>
<dt><var>c</var><dd>A column array containing the objective function coefficients.
<br><dt><var>a</var><dd>A matrix containing the constraints coefficients.
<br><dt><var>b</var><dd>A column array containing the right-hand side value for each constraint
in the constraint matrix.
<br><dt><var>lb</var><dd>An array containing the lower bound on each of the variables. If
<var>lb</var> is not supplied, the default lower bound for the variables is
zero.
<br><dt><var>ub</var><dd>An array containing the upper bound on each of the variables. If
<var>ub</var> is not supplied, the default upper bound is assumed to be
infinite.
<br><dt><var>ctype</var><dd>An array of characters containing the sense of each constraint in the
constraint matrix. Each element of the array may be one of the
following values
<dl>
<dt><code>"F"</code><dd>A free (unbounded) constraint (the constraint is ignored).
<br><dt><code>"U"</code><dd>An inequality constraint with an upper bound (<code>A(i,:)*x <= b(i)</code>).
<br><dt><code>"S"</code><dd>An equality constraint (<code>A(i,:)*x = b(i)</code>).
<br><dt><code>"L"</code><dd>An inequality with a lower bound (<code>A(i,:)*x >= b(i)</code>).
<br><dt><code>"D"</code><dd>An inequality constraint with both upper and lower bounds
(<code>A(i,:)*x >= -b(i)</code> <em>and</em> (<code>A(i,:)*x <= b(i)</code>).
</dl>
<br><dt><var>vartype</var><dd>A column array containing the types of the variables.
<dl>
<dt><code>"C"</code><dd>A continuous variable.
<br><dt><code>"I"</code><dd>An integer variable.
</dl>
<br><dt><var>sense</var><dd>If <var>sense</var> is 1, the problem is a minimization. If <var>sense</var> is
-1, the problem is a maximization. The default value is 1.
<br><dt><var>param</var><dd>A structure containing the following parameters used to define the
behavior of solver. Missing elements in the structure take on default
values, so you only need to set the elements that you wish to change
from the default.
<p>Integer parameters:
<dl>
<dt><code>msglev (LPX_K_MSGLEV, default: 1)</code><dd>Level of messages output by solver routines:
<dl>
<dt>0<dd>No output.
<br><dt>1<dd>Error messages only.
<br><dt>2<dd>Normal output .
<br><dt>3<dd>Full output (includes informational messages).
</dl>
<br><dt><code>scale (LPX_K_SCALE, default: 1)</code><dd>Scaling option:
<dl>
<dt>0<dd>No scaling.
<br><dt>1<dd>Equilibration scaling.
<br><dt>2<dd>Geometric mean scaling, then equilibration scaling.
</dl>
<br><dt><code>dual (LPX_K_DUAL, default: 0)</code><dd>Dual simplex option:
<dl>
<dt>0<dd>Do not use the dual simplex.
<br><dt>1<dd>If initial basic solution is dual feasible, use the dual simplex.
</dl>
<br><dt><code>price (LPX_K_PRICE, default: 1)</code><dd>Pricing option (for both primal and dual simplex):
<dl>
<dt>0<dd>Textbook pricing.
<br><dt>1<dd>Steepest edge pricing.
</dl>
<br><dt><code>round (LPX_K_ROUND, default: 0)</code><dd>Solution rounding option:
<dl>
<dt>0<dd>Report all primal and dual values "as is".
<br><dt>1<dd>Replace tiny primal and dual values by exact zero.
</dl>
<br><dt><code>itlim (LPX_K_ITLIM, default: -1)</code><dd>Simplex iterations limit. If this value is positive, it is decreased by
one each time when one simplex iteration has been performed, and
reaching zero value signals the solver to stop the search. Negative
value means no iterations limit.
<br><dt><code>itcnt (LPX_K_OUTFRQ, default: 200)</code><dd>Output frequency, in iterations. This parameter specifies how
frequently the solver sends information about the solution to the
standard output.
<br><dt><code>branch (LPX_K_BRANCH, default: 2)</code><dd>Branching heuristic option (for MIP only):
<dl>
<dt>0<dd>Branch on the first variable.
<br><dt>1<dd>Branch on the last variable.
<br><dt>2<dd>Branch using a heuristic by Driebeck and Tomlin.
</dl>
<br><dt><code>btrack (LPX_K_BTRACK, default: 2)</code><dd>Backtracking heuristic option (for MIP only):
<dl>
<dt>0<dd>Depth first search.
<br><dt>1<dd>Breadth first search.
<br><dt>2<dd>Backtrack using the best projection heuristic.
</dl>
<br><dt><code>presol (LPX_K_PRESOL, default: 1)</code><dd>If this flag is set, the routine lpx_simplex solves the problem using
the built-in LP presolver. Otherwise the LP presolver is not used.
<br><dt><code>lpsolver (default: 1)</code><dd>Select which solver to use. If the problem is a MIP problem this flag
will be ignored.
<dl>
<dt>1<dd>Revised simplex method.
<br><dt>2<dd>Interior point method.
</dl>
<br><dt><code>save (default: 0)</code><dd>If this parameter is nonzero, save a copy of the problem in
CPLEX LP format to the file <samp><span class="file">"outpb.lp"</span></samp>. There is currently no
way to change the name of the output file.
</dl>
<p>Real parameters:
<dl>
<dt><code>relax (LPX_K_RELAX, default: 0.07)</code><dd>Relaxation parameter used in the ratio test. If it is zero, the textbook
ratio test is used. If it is non-zero (should be positive), Harris'
two-pass ratio test is used. In the latter case on the first pass of the
ratio test basic variables (in the case of primal simplex) or reduced
costs of non-basic variables (in the case of dual simplex) are allowed
to slightly violate their bounds, but not more than
<code>relax*tolbnd</code> or <code>relax*toldj (thus, relax is a
percentage of tolbnd or toldj</code>.
<br><dt><code>tolbnd (LPX_K_TOLBND, default: 10e-7)</code><dd>Relative tolerance used to check if the current basic solution is primal
feasible. It is not recommended that you change this parameter unless you
have a detailed understanding of its purpose.
<br><dt><code>toldj (LPX_K_TOLDJ, default: 10e-7)</code><dd>Absolute tolerance used to check if the current basic solution is dual
feasible. It is not recommended that you change this parameter unless you
have a detailed understanding of its purpose.
<br><dt><code>tolpiv (LPX_K_TOLPIV, default: 10e-9)</code><dd>Relative tolerance used to choose eligible pivotal elements of the
simplex table. It is not recommended that you change this parameter unless you
have a detailed understanding of its purpose.
<br><dt><code>objll (LPX_K_OBJLL, default: -DBL_MAX)</code><dd>Lower limit of the objective function. If on the phase II the objective
function reaches this limit and continues decreasing, the solver stops
the search. This parameter is used in the dual simplex method only.
<br><dt><code>objul (LPX_K_OBJUL, default: +DBL_MAX)</code><dd>Upper limit of the objective function. If on the phase II the objective
function reaches this limit and continues increasing, the solver stops
the search. This parameter is used in the dual simplex only.
<br><dt><code>tmlim (LPX_K_TMLIM, default: -1.0)</code><dd>Searching time limit, in seconds. If this value is positive, it is
decreased each time when one simplex iteration has been performed by the
amount of time spent for the iteration, and reaching zero value signals
the solver to stop the search. Negative value means no time limit.
<br><dt><code>outdly (LPX_K_OUTDLY, default: 0.0)</code><dd>Output delay, in seconds. This parameter specifies how long the solver
should delay sending information about the solution to the standard
output. Non-positive value means no delay.
<br><dt><code>tolint (LPX_K_TOLINT, default: 10e-5)</code><dd>Relative tolerance used to check if the current basic solution is integer
feasible. It is not recommended that you change this parameter unless
you have a detailed understanding of its purpose.
<br><dt><code>tolobj (LPX_K_TOLOBJ, default: 10e-7)</code><dd>Relative tolerance used to check if the value of the objective function
is not better than in the best known integer feasible solution. It is
not recommended that you change this parameter unless you have a
detailed understanding of its purpose.
</dl>
</dl>
<p>Output values:
<dl>
<dt><var>xopt</var><dd>The optimizer (the value of the decision variables at the optimum).
<br><dt><var>fopt</var><dd>The optimum value of the objective function.
<br><dt><var>status</var><dd>Status of the optimization.
<p>Simplex Method:
<dl>
<dt>180 (<code>LPX_OPT</code>)<dd>Solution is optimal.
<br><dt>181 (<code>LPX_FEAS</code>)<dd>Solution is feasible.
<br><dt>182 (<code>LPX_INFEAS</code>)<dd>Solution is infeasible.
<br><dt>183 (<code>LPX_NOFEAS</code>)<dd>Problem has no feasible solution.
<br><dt>184 (<code>LPX_UNBND</code>)<dd>Problem has no unbounded solution.
<br><dt>185 (<code>LPX_UNDEF</code>)<dd>Solution status is undefined.
</dl>
Interior Point Method:
<dl>
<dt>150 (<code>LPX_T_UNDEF</code>)<dd>The interior point method is undefined.
<br><dt>151 (<code>LPX_T_OPT</code>)<dd>The interior point method is optimal.
</dl>
Mixed Integer Method:
<dl>
<dt>170 (<code>LPX_I_UNDEF</code>)<dd>The status is undefined.
<br><dt>171 (<code>LPX_I_OPT</code>)<dd>The solution is integer optimal.
<br><dt>172 (<code>LPX_I_FEAS</code>)<dd>Solution integer feasible but its optimality has not been proven
<br><dt>173 (<code>LPX_I_NOFEAS</code>)<dd>No integer feasible solution.
</dl>
If an error occurs, <var>status</var> will contain one of the following
codes:
<dl>
<dt>204 (<code>LPX_E_FAULT</code>)<dd>Unable to start the search.
<br><dt>205 (<code>LPX_E_OBJLL</code>)<dd>Objective function lower limit reached.
<br><dt>206 (<code>LPX_E_OBJUL</code>)<dd>Objective function upper limit reached.
<br><dt>207 (<code>LPX_E_ITLIM</code>)<dd>Iterations limit exhausted.
<br><dt>208 (<code>LPX_E_TMLIM</code>)<dd>Time limit exhausted.
<br><dt>209 (<code>LPX_E_NOFEAS</code>)<dd>No feasible solution.
<br><dt>210 (<code>LPX_E_INSTAB</code>)<dd>Numerical instability.
<br><dt>211 (<code>LPX_E_SING</code>)<dd>Problems with basis matrix.
<br><dt>212 (<code>LPX_E_NOCONV</code>)<dd>No convergence (interior).
<br><dt>213 (<code>LPX_E_NOPFS</code>)<dd>No primal feasible solution (LP presolver).
<br><dt>214 (<code>LPX_E_NODFS</code>)<dd>No dual feasible solution (LP presolver).
</dl>
<br><dt><var>extra</var><dd>A data structure containing the following fields:
<dl>
<dt><code>lambda</code><dd>Dual variables.
<br><dt><code>redcosts</code><dd>Reduced Costs.
<br><dt><code>time</code><dd>Time (in seconds) used for solving LP/MIP problem.
<br><dt><code>mem</code><dd>Memory (in bytes) used for solving LP/MIP problem (this is not
available if the version of GLPK is 4.15 or later).
</dl>
</dl>
<p>Example:
<pre class="example"> c = [10, 6, 4]';
a = [ 1, 1, 1;
10, 4, 5;
2, 2, 6];
b = [100, 600, 300]';
lb = [0, 0, 0]';
ub = [];
ctype = "UUU";
vartype = "CCC";
s = -1;
param.msglev = 1;
param.itlim = 100;
[xmin, fmin, status, extra] = ...
glpk (c, a, b, lb, ub, ctype, vartype, s, param);
</pre>
</blockquote></div>
</body></html>
|
