Main Page
Classes
Files
File List
File Members
opt
build
coinor-dylp
coinor-dylp-1.6.0
DyLP
src
Dylp
dylp.h
Go to the documentation of this file.
1
/*
2
This file is a part of the Dylp LP distribution.
3
4
Copyright (C) 2005 -- 2007 Lou Hafer
5
6
School of Computing Science
7
Simon Fraser University
8
Burnaby, B.C., V5A 1S6, Canada
9
lou@cs.sfu.ca
10
11
This code is licensed under the terms of the Common Public License (CPL).
12
*/
13
14
#ifndef _DYLP_H
15
#define _DYLP_H
16
17
/*
18
@(#)dylp.h 4.6 10/15/05
19
svn/cvs: $Id: dylp.h 299 2009-08-28 01:35:28Z lou $
20
21
This file contains definitions related to dylp, a subroutine library which
22
implements a dynamic (primal-dual) linear programming algorithm based on
23
the algorithm described by Padberg in Linear Optimisation & Extensions,
24
Springer-Verlag, 1995. dylp also owes a debt to previous and contemporary
25
codes the author has worked with --- la05, bandbx, zoom/xmp, ylp, and glpk.
26
27
At minimum, dylp requires only a constraint system. Since it manages a
28
dynamically sized private copy of the constraint system while solving the
29
LP, there's no point in having the client attach logical variables (they'd
30
just get in the way, really).
31
32
dylp will accept a basis specification. This takes the form of a status
33
vector giving the status of all variables, and a basis vector specifying
34
the active constraints and their associated basic variables. From this
35
dylp will construct an initial active problem which consists of exactly
36
the given constraints and basic variables, with the logicals for the
37
constraints making up the nonbasic partition.
38
39
dylp returns as a solution the simplex termination code, the objective
40
value (or related value, appropriate for the termination code), status for
41
all variables, the active constraints, and the associated primal and dual
42
variables (put a little differently, a basis, the values of the basic
43
variables, and the dual variables associated with the active constraints).
44
45
The conditional compilation symbol DYLP_INTERNAL is used to delimit
46
definitions that should be considered internal to dylp. Don't define this
47
symbol in a client.
48
*/
49
50
#include "
dylib_errs.h
"
51
#include "
dylib_io.h
"
52
#include "
dy_consys.h
"
53
54
/*
55
A few words on notation. Traditional matrix and vector notation for LP
56
suffers a bit when limited to ascii text, but it's readable if you're
57
familiar with the original. The notation in the comments and code is
58
loosely based on Chvatal, "Linear Programming", W.H. Freeman, 1983, which
59
the author happens to like.
60
61
A matrix is represented with a capital letter, e.g., B. A vector is
62
represented with a small letter, e.g., x. A subscript is given in angle
63
brackets, e.g., x<j> for the jth coefficient of x. An individual element of
64
a matrix has two subscripts, e.g., a<i,j> for the element in row i, column
65
j. Column and row vectors are shown with one subscript, e.g., a<j> for the
66
jth column (or row). Whether the vector is supposed to be a column or a
67
row should generally be clear from context. A capital letter in the
68
subscript position indicates a set of elements, e.g., x<N> is the non-basic
69
variables.
70
71
The inverse of a matrix is denoted inv(*), e.g., the basis inverse,
72
inv(B). The dot product of two vectors is denoted dot(*,*), e.g.,
73
dot(c,x), or sometimes just written directly, e.g., cx.
74
75
The system of constraints is assumed to be Ax <= b, with m rows and n
76
columns. Once the logical variables (aka slacks and artificials) have been
77
added, it becomes Ax = b. A is the constraint matrix, x is the vector of
78
primal variables, and b is the right-hand-side (rhs). NOTE that the
79
convention for indices is NOT the usual one. Logical variables are assigned
80
indices 1..m and architectural variables are assigned indices m+1..m+n. It
81
makes for more efficient addition/deletion of variables; see dy_consys.h for a
82
little more explanation.
83
84
There is an objective function z = cx, where z is the objective value and c
85
is the vector of coefficients. dylp minimises the objective.
86
87
The matrix A is partitioned into the set of basic columns B, and the set of
88
non-basic columns N (sometimes A<N>). The corresponding partitions of c and
89
x are c<B>, x<B>, and c<N>, x<N>.
90
91
Premultiplication by the basis inverse (e.g., inv(B)a<j>) is referred to as
92
an `ftran'; postmultiplication (e.g., c<B>inv(B)) as a `btran'. Quantities
93
that have been transformed using the basis inverse are often (but not
94
always) renamed as 'barred' quantities.
95
96
The basic primal variables are x<B> = inv(B)b. The dual variables are y =
97
c<B>inv(B). The jth column of A, premultiplied by inv(B), is abar<j> =
98
inv(B)a<j>. The reduced costs are cbar = c<N> - c<B>inv(B)N = c<N>-yN.
99
100
The variable i is used as a row index, j as a column index. Often they will
101
represent the entering primal variable (j) and the leaving primal variable
102
(i). Be aware that comments are often written as if the leaving primal
103
variable x<i> occupies row i of the basis. This simplifies the writing.
104
But keep in mind that variable x<i> can occupy an arbitrary row k of the
105
basis.
106
*/
107
108
/*
109
Termination codes for dy_primal and dy_dual, the top level routines of the
110
dylp simplex algorithms. Also used by various internal routines. Codes
111
marked with (*) will never be returned to the client unless dylp has
112
failed.
113
114
lpINV The code is not valid (i.e., not set by an execution of
115
dy_primal or dy_dual).
116
117
lpOPTIMAL The problem has an optimal solution.
118
119
lpUNBOUNDED The problem is unbounded.
120
121
lpSWING(*) The problem is pseudo-unbounded: Some primal variable grew
122
excessively in a single pivot.
123
124
lpINFEAS The problem is infeasible.
125
126
lpACCCHK An accuracy check failed and dylp's internal recovery
127
algorithms could not recover the situation.
128
129
lpSTALLED The problem has been abandoned due to stalling. (We could
130
in fact actually be cycling, but that's too much trouble
131
to prove.)
132
133
lpITERLIM The problem has been abandoned because it has exceeded an
134
absolute iteration limit.
135
136
lpNOSPACE The problem has been abandoned because the basis package did
137
not have sufficient space to maintain the basis.
138
139
lpLOSTFEAS Feasibility was lost during simplex execution.
140
141
lpPUNT The lp has punted because it ran into a pivoting problem.
142
143
The next three codes indicate that we're in the middle of
144
attempting a forced transition for error recovery purposes.
145
146
lpFORCEDUAL(*) Force a primal to dual transition.
147
148
lpFORCEPRIMAL(*) Force a dual to primal transition.
149
150
lpFORCEFULL(*) Force all inactive constraints and variables to be loaded.
151
152
lpFATAL Fatal confusion or error of some sort; covers a multitude
153
of sins.
154
155
The dual simplex routine does not have a phase I routine equivalent to
156
dy_primal1 for the primal simplex. (In the context of dylp, it expects
157
to run after dy_primal has been used to find an initial optimal solution.)
158
159
When using the dual simplex method, internal codes reflect the state of
160
the dual problem, but dy_dual makes the usual translation back to the
161
primal problem, as:
162
163
Dual Primal Rationale
164
---- ------ ---------
165
lpUNBOUNDED lpINFEAS Standard duality theorem.
166
167
Note that lpSWING always refers to primal variables.
168
*/
169
170
typedef
enum
{
lpFATAL
= -1,
lpINV
= 0,
171
lpOPTIMAL
,
lpUNBOUNDED
,
lpSWING
,
lpINFEAS
,
172
lpACCCHK
,
173
lpSTALLED
,
lpITERLIM
,
lpNOSPACE
,
174
lpLOSTFEAS
,
lpPUNT
,
175
lpFORCEDUAL
,
lpFORCEPRIMAL
,
lpFORCEFULL
}
lpret_enum
;
176
177
178
/*
179
Phase codes for dylp
180
181
dyINV Invalid phase
182
dyINIT Initialisation and setup, including establishing the
183
initial set of constraints and variables and crashing the
184
first basis.
185
dyPRIMAL1 Primal simplex phase I
186
dyPRIMAL2 Primal simplex phase II
187
dyDUAL Dual simplex
188
dyPURGEVAR Deactivation of variables.
189
dyGENVAR Generation of new variables (not part of original problem).
190
dyADDVAR Activation of variables.
191
dyPURGECON Deactivation of constraints.
192
dyGENCON Generation of new constraints (not part of original problem).
193
dyADDCON Activation of constraints.
194
dyFORCEDUAL Force dual feasibility (error recovery)
195
dyFORCEPRIMAL Force primal feasibility (error recovery)
196
dyFORCEFULL Force activation of the full system (error recovery)
197
dyDONE Execution is finished, for one reason or another.
198
199
It's true that new variables will be added during dyGENCON -- at the least,
200
each newly generated constraint will bring with it a logical variable.
201
dyGENVAR differs in that it is augmenting some subset of the constraints
202
with new variables (classic column generation, for example).
203
204
The main loop states (dyPRIMAL1 -- dyFORCEFULL) must remain a contiguous
205
block. dy_dumpstats counts on dyPRIMAL1 and dyFORCEPRIMAL being first and
206
last, respectively, in the block.
207
208
dyDONE must remain the last code --- it's used to dimension a statistics
209
array that tracks the number of times the main loop states are entered.
210
*/
211
212
typedef
enum
{
dyINV
= 0,
dyINIT
,
213
dyPRIMAL1
,
dyPRIMAL2
,
dyDUAL
,
214
dyPURGEVAR
,
dyGENVAR
,
dyADDVAR
,
215
dyPURGECON
,
dyGENCON
,
dyADDCON
,
216
dyFORCEDUAL
,
dyFORCEPRIMAL
,
dyFORCEFULL
,
217
dyDONE
}
dyphase_enum
;
218
/*
219
General return and error codes.
220
221
Used by various routines in dylp.
222
No routine
223
uses all of these, but there's enough overlap to make one big enum
224
convenient.
225
226
dyrINV Invalid code.
227
228
dyrOK Whatever it was that was being done was done without incident.
229
dyrOPTIMAL The problem is optimal.
230
dyrUNBOUND The problem is unbounded.
231
dyrSWING The problem is pseudo-unbounded: Some variable grew by an
232
excessive amount in a single pivot.
233
dyrINFEAS The problem is infeasible.
234
235
dyrREQCHK Requests a refactor and accuracy check (triggered by various
236
checks for bogus numbers).
237
dyrACCCHK An accuracy check has failed.
238
dyrLOSTPFEAS Primal feasibility has been lost.
239
dyrLOSTDFEAS Dual feasibility has been lost.
240
241
dyrDEGEN Degeneracy has been discovered, or a degenerate pivot has been
242
taken.
243
dyrRESELECT Reselect an incoming variable (after an abortive pivot
244
attempt).
245
dyrMADPIV The selected pivot coefficient was (numerically) unstable.
246
dyrPUNT In the context of the dual simplex: the dual simplex has
247
decided to punt to the primal simplex phase I, for any of
248
several reasons. Generally this is indicative of the relative
249
lack of sophistication in the dual simplex.
250
In the context of the primal simplex: this indicates that all
251
candidates to enter the basis were flagged with a NOPIVOT
252
qualifier.
253
254
dyrPATCHED The basis package managed to factor the basis after patching
255
it.
256
dyrSINGULAR The basis package discovered the basis was singular. (Typically
257
as a consequence of a pivot gone bad.)
258
dyrNUMERIC The basis package detected unacceptable growth in the basis
259
coefficients.
260
dyrBSPACE The basis package ran out of space for the basis
261
representation.
262
dyrSTALLED The LP seems to have stalled (and could possibly be cycling,
263
but that's too much trouble to prove); triggered by too many
264
iterations with no change in the objective.
265
dyrITERLIM The iteration limit has been exceeded.
266
267
dyrFATAL Fatal confusion; covers a multitude of sins.
268
269
The specific values assigned to some of the codes in the enum come from
270
earlier use of yla05 as the basis package. It's gone, but there's no
271
incentive to remove the values.
272
*/
273
274
typedef
enum
{
dyrFATAL
= -10,
dyrITERLIM
,
dyrSTALLED
,
275
dyrBSPACE
= -7,
dyrSINGULAR
= -6,
dyrNUMERIC
= -5,
276
dyrLOSTPFEAS
,
dyrLOSTDFEAS
,
dyrDEGEN
,
dyrMADPIV
,
277
dyrINV
= 0,
dyrOK
= 1,
dyrPATCHED
= 2,
278
dyrRESELECT
,
dyrREQCHK
,
dyrACCCHK
,
dyrPUNT
,
279
dyrOPTIMAL
,
dyrUNBOUND
,
dyrSWING
,
dyrINFEAS
}
dyret_enum
;
280
281
/*
282
Requests and results for checks and recalculations
283
284
Some symbolic names for requesting and reporting on factoring, accuracy
285
checks and primal and dual variable calculations. These originated with la
286
Duenna, hence the lad prefix. Interpretation varies subtly from routine to
287
routine, so check the parameter notes.
288
289
ladPRIMALCHK (i) set to request primal accuracy check, Bx<B> = b - Nx<N>,
290
(o) set to indicate failure of check
291
ladDUALCHK (i) set to to request dual accuracy check, yB = c<B>
292
(o) set to indicate failure of check
293
ladPRIMFEAS (i) set to request primal feasibility check (primal variables
294
within bounds)
295
(o) set to indicate loss of primal feasibility
296
ladDUALFEAS (i) set to request dual feasibility check (reduced costs of
297
proper sign)
298
(o) set to indicate loss of dual feasibility
299
ladPFQUIET (i) set to suppress warnings about variables which are not
300
primal feasible
301
ladDFQUIET (i) set to suppress warnings about variables which are not
302
dual feasible
303
ladDUALS (i) set to request calculation of the dual variables and
304
gradient vector
305
(o) set to indicate calculation of the dual variables and
306
gradient vector
307
ladPRIMALS (i) set to request calculation of the primal variables
308
(o) set to indicate calculation of the primal variables
309
ladFACTOR (i) set to indicate the basis should be refactored
310
(o) set to indicate the basis has been factored
311
ladEXPAND (i) set to force expansion of the space allocated for the
312
basis representation
313
(o) set to indicate the space allocated for the basis was
314
increased
315
*/
316
317
#define ladPRIMFEAS 1<<0
318
#define ladPRIMALCHK 1<<1
319
#define ladPFQUIET 1<<2
320
#define ladDUALFEAS 1<<3
321
#define ladDUALCHK 1<<4
322
#define ladDFQUIET 1<<5
323
#define ladDUALS 1<<6
324
#define ladPRIMALS 1<<7
325
#define ladFACTOR 1<<8
326
#define ladEXPAND 1<<9
327
328
329
330
/*
331
Variable status codes
332
333
dylp keeps explicit status for both basic and nonbasic variables. These are
334
set up as flags so that it's easy to test when more than one status will do
335
for a particular action.
336
337
vstatBFX basic, fixed
338
vstatBUUB basic, above upper bound
339
vstatBUB basic, at upper bound
340
vstatB basic, strictly between bounds (a well-behaved basic variable)
341
vstatBLB basic, at lower bound
342
vstatBLLB basic, below lower bound
343
vstatBFR basic, free (unbounded)
344
345
vstatNBFX nonbasic, fixed
346
vstatNBUB nonbasic at upper bound
347
vstatNBLB nonbasic at lower bound
348
vstatNBFR nonbasic free
349
350
vstatSB superbasic, within bounds
351
352
dylp ensures that superbasic variables are, in fact, always strictly within
353
bounds.
354
355
Inactive NBFR variables can be created at startup if dylp is working with a
356
partial system and there are free variables that are not selected to be in
357
the initial basis. If the client is forcing a full system, these will be
358
active NBFR variables. Error recovery may also create active NBFR
359
variables. By convention, NBFR variables always have a value of zero.
360
361
Inactive SB variables should not occur. SB status occurs only as the result
362
of error recovery and is only valid in primal simplex.
363
364
The value of SB variables is lost when they are reported out as part of a
365
solution. This will only happen if dylp could not find an optimal solution.
366
367
The following qualifiers can be added to the status:
368
369
vstatNOPIVOT Prevents the variable from being considered as a candidate
370
for pivoting; used by the pivot rejection machinery.
371
vstatNOPER Prevents the variable from being perturbed during the
372
formation of a restricted subproblem.
373
vstatNOLOAD Prevents the variable from being considered for activation;
374
used by startup and variable activation/deactivation routines.
375
*/
376
377
#define vstatINV 0
378
#define vstatBFX 1<<0
379
#define vstatBUB 1<<1
380
#define vstatB 1<<2
381
#define vstatBLB 1<<3
382
#define vstatBFR 1<<4
383
#define vstatNBFX 1<<5
384
#define vstatNBUB 1<<6
385
#define vstatNBLB 1<<7
386
#define vstatNBFR 1<<8
387
#define vstatSB 1<<9
388
#define vstatBUUB 1<<10
389
#define vstatBLLB 1<<11
390
391
/*
392
TAKE NOTE: Do not use the msb as a qualifier! The status value, with or
393
without qualifiers, must be a positive value when cast to a signed integer.
394
*/
395
396
#define vstatNOPIVOT ((flags) 1<<(sizeof(flags)*8-2))
397
#define vstatNOPER ((flags) 1<<(sizeof(flags)*8-3))
398
#define vstatNOLOAD ((flags) 1<<(sizeof(flags)*8-4))
399
400
#define vstatBASIC \
401
(vstatBFX|vstatBUUB|vstatBUB|vstatB|vstatBLB|vstatBLLB|vstatBFR)
402
#define vstatNONBASIC (vstatNBFX|vstatNBUB|vstatNBLB)
403
#define vstatEXOTIC (vstatSB|vstatNBFR)
404
405
#define vstatSTATUS (vstatBASIC|vstatNONBASIC|vstatEXOTIC)
406
#define vstatQUALS (vstatNOPIVOT|vstatNOPER|vstatNOLOAD)
407
408
/*
409
This macro checks (in a simplistic way) that its parameter encodes one and
410
only one status. It's intended for mild error checking. See
411
dylp_utils:dy_chkstatus if you're really feeling paranoid.
412
*/
413
414
#define VALID_STATUS(zz_status_zz) \
415
(zz_status_zz == vstatBFX || zz_status_zz == vstatBUB || \
416
zz_status_zz == vstatB || zz_status_zz == vstatBLB || \
417
zz_status_zz == vstatBFR || \
418
zz_status_zz == vstatNBFX || zz_status_zz == vstatNBUB || \
419
zz_status_zz == vstatNBLB || zz_status_zz == vstatNBFR || \
420
zz_status_zz == vstatSB)
421
422
423
424
/*
425
Interface structures: lpprob_struct, lptols_struct, lpopts_struct
426
*/
427
428
/*
429
basis_struct
430
431
This structure is used to describe a basis to dylp, and to return the
432
final basis at termination. The size of the basis depends on the
433
number of active constraints, which will be a subset of the constraints
434
in the system.
435
436
The constraint system as supplied to dylp should not have logical variables
437
(dylp will create them automatically). This presents a problem if the final
438
basis contains basic logical variables. In this case, vndx is set to the
439
negative of the index of the constraint which spawned the logical. This
440
same technique can be used on input to, for example, specify the traditional
441
all-logical starting basis.
442
443
Field Definition
444
----- ----------
445
len The number of rows in the basis.
446
el.cndx Index of the constraint in this basis position.
447
el.vndx Index of the variable in this basis position.
448
449
*/
450
451
typedef
struct
{
int
cndx ;
int
vndx
; }
basisel_struct
;
452
453
typedef
struct
454
{
int
len
;
455
basisel_struct
*
el
; }
basis_struct
;
456
457
458
/*
459
LP problem control and status flags
460
461
lpctlNOFREE (i) Prevents dylp from freeing the problem structures,
462
in anticipation of a subsequent hot start. If dylp
463
exits with a state that is not suitable for hot
464
start, this flag is ignored and the problem data
465
structures are released.
466
lpctlONLYFREE (i) In conjunction with an initial phase of dyDONE,
467
causes dylp to do nothing except free the problem
468
data structure and return.
469
lpctlUBNDCHG (i) Indicates that the variable upper bounds (vub) have
470
been changed.
471
lpctlLBNDCHG (i) Indicates that the variable lower bounds (lub) have
472
been changed.
473
lpctlRHSCHG (i) Indicates that the right-hand side (rhs) has been
474
changed. Includes the rhslow vector (if it exists).
475
lpctlOBJCHG (i) Indicates that the objective (obj) has been changed.
476
lpctlACTVARSIN (i) Indicates that a valid active variable vector has
477
been supplied.
478
lpctlINITACTVAR (i) Forces dylp to perform variable activation before
479
beginning simplex iterations.
480
lpctlINITACTCON (i) Forces dylp to perform constraint activation before
481
beginning simplex iterations. (If variable
482
activation is also requested, constraint activation
483
occurs first.)
484
485
lpctlACTVARSOUT (i) Indicates that an active variable vector is to be
486
returned.
487
(o) Indicates that a valid active variable vector has
488
been returned.
489
490
lpctlDYVALID (o) Indicates that dylp exited in a state which can
491
be restarted with a hot start.
492
493
*/
494
495
#define lpctlNOFREE 1<<0
496
#define lpctlONLYFREE 1<<1
497
#define lpctlUBNDCHG 1<<2
498
#define lpctlLBNDCHG 1<<3
499
#define lpctlRHSCHG 1<<4
500
#define lpctlOBJCHG 1<<5
501
#define lpctlACTVARSIN 1<<6
502
#define lpctlINITACTVAR 1<<7
503
#define lpctlINITACTCON 1<<8
504
505
#define lpctlACTVARSOUT 1<<10
506
507
#define lpctlDYVALID 1<<11
508
509
/*
510
lpprob_struct
511
512
This structure is used to pass an LP problem into dylp and convey the
513
results back to the client. The allocated size indicated in colsze and
514
rowsze is assumed to be accurate. If basis, status, x, or y are NULL, they
515
will be allocated as needed. If they are non-NULL, dylp will reallocate
516
them if necessary (i.e., when the actual size of the lp exceeds the
517
allocated size of the vectors).
518
519
The status vector has the following coding:
520
* for nonbasic variables, the normal dylp status flags are used;
521
* for basic variables, the negative of the basis index is used.
522
523
There is one unavoidable problem with this scheme -- the status vector
524
provides the only information about the value of nonbasic variables. This
525
is adequate for all but superbasic variables and nonbasic free variables
526
which are not at zero. Both of these cases are transient anomalies, created
527
only when the basis package is forced to patch a singular basis, and they
528
should not persist in the final solution when an optimal solution is found
529
or when the problem is infeasible. They may, however, occur in the
530
solution reported for an unbounded problem if the unbounded condition is
531
discovered before the nonbasic free or superbasic variable is chosen for
532
pivoting. On input, nonbasic free variables are assumed to take the value
533
0, and specifying a superbasic variable is illegal.
534
535
Field Definition
536
----- ----------
537
ctlopts Control and status flags.
538
phase (i) If set to dyDONE, dylp will free any retained data
539
structures and return. Any other value is ignored.
540
(o) Termination phase of the dynamic simplex algorithm;
541
should be dyDONE unless something screws up, in which
542
case it'll be dyINV.
543
lpret Return code from the simplex routine.
544
obj For lpOPTIMAL, the value of the objective function.
545
For lpINFEAS, the total infeasibility.
546
For lpUNBOUNDED, the index of the unbounded variable, negated
547
if the variable can decrease without bound, positive if it
548
can increase without bound. The logical for constraint i
549
is represented as n+i.
550
Otherwise, undefined.
551
iters The number of simplex iterations.
552
consys The constraint system.
553
basis (i) Initial basis.
554
(o) Final basis.
555
status (i) Initial status vector.
556
(o) Final status vector.
557
x (i) No values used, but a vector can be supplied.
558
(o) The values of the basic variables (indexed by basis
559
position).
560
y (i) No values used, but a vector can be supplied.
561
(o) The values of the dual variables (indexed by basis
562
position).
563
actvars There is one entry for each variable, coded TRUE if the
564
variable is active, FALSE otherwise. The vector supplied on
565
input will be overwritten on output.
566
(i) Variables to be activated at startup. Used only for a
567
warm start. Validity is indicated by the lpctlACTVARSIN
568
flag. A vector can be supplied strictly for output use.
569
(o) The current active variables. Will be returned only if
570
requested by the lpctlACTVARSOUT flag. If the vector is
571
valid on return, lpctlACTVARSOUT will remain set,
572
otherwise it will be reset.
573
574
colsze Allocated column capacity (length of status vector).
575
rowsze Allocated row capacity (length of basis, x, and y vectors).
576
577
578
Note that dylp will reallocate status, basis->el, actvars, x, and y, if the
579
vectors supplied at startup are too small to report the solution. Don't set
580
colsze or rowsze to nonzero values without actually allocating space.
581
*/
582
583
typedef
struct
584
{
flags
ctlopts
;
585
dyphase_enum
phase
;
586
lpret_enum
lpret
;
587
double
obj
;
588
int
iters
;
589
consys_struct
*
consys
;
590
basis_struct
*
basis
;
591
flags
*
status
;
592
double
*
x
;
593
double
*
y
;
594
bool
*
actvars
;
595
int
colsze
;
596
int
rowsze
; }
lpprob_struct
;
597
598
599
600
/*
601
lptols_struct
602
603
This structure contains phase and tolerance information for the lp algorithm.
604
605
The philosophy with respect to the separate zero and feasibility tolerances
606
for primal and dual variables is that dylp uses the zero tolerance when
607
calculating primal or dual variables, and the feasibility tolerance when
608
checking for feasibility. This allows us to keep small values for accuracy
609
in computation, but not be so fussy when it comes to feasibility.
610
611
Field Definition
612
----- ----------
613
inf Infinity. dylp uses IEEE FP infinity, but be careful not to
614
pass it to the basis package.
615
zero Zero tolerance for primal variables, and also the generic
616
zero tolerance for constraint coefficients, right-hand-side
617
values, etc.
618
pchk Primal accuracy check tolerance.
619
pfeas Primal feasibility check tolerance; dynamically scaled from
620
zero in proportion to the 1-norm of the primal basic variables.
621
pfeas_scale Primal feasibility check tolerance multiplier. This provides
622
some user-controllable decoupling of zero and pfeas.
623
cost Base zero tolerance for checks involving objective function
624
coefficients, reduced costs, and related values.
625
dchk Dual accuracy check tolerance. Also used by dy_duenna to
626
test for improvement in the objective.
627
dfeas Dual feasbility check tolerance; dynamically scaled from cost
628
in proportion to the 1-norm of the dual variables. Acts as the
629
zero tolerance for reduced costs.
630
dfeas_scale Dual feasibility check tolerance multiplier. This provides
631
some user-controllable decoupling of cost and dfeas.
632
pivot Simplex pivot selection tolerance, expressed as a multiplier
633
for the pivot selection tolerance used by the basis package
634
when factoring the basis. (I.e., the actual pivot selection
635
criteria will be to accept a simplex pivot a<i,j> if
636
|a<i,j>| > lptols.pivot*basis.pivot*MAX{i}|a<i,j>|.)
637
bogus Multiplier used to identify 'bogus' values, in the range
638
tol < |val| < bogus*tol for the appropriate tolerance.
639
swing Ratio used to identify excessive growth in primal variables
640
(pseudo-unboundedness).
641
toobig Absolute value of primal variables which will cause dual
642
multipivoting to consider primal infeasibility when selecting
643
a flip/pivot sequence.
644
purge Percentage change in objective function required before
645
constraint or variable purging is attempted.
646
purgevar Percentage of maximum reduced cost used to determine the
647
variable purge threshold; nonbasic architectural variables
648
at their optimum bound whose reduced cost exceeds
649
purgevar*MAX{j}cbar<j> are purged.
650
651
reframe Multiplier used to trigger a reference framework reset in
652
PSE pricing; reset occurs if
653
|gamma<j> - ||abar<j>||^2| > reframe*||abar<j>||^2.
654
The check is made in pseupdate.
655
Also used to trigger recalculation of the basis inverse row
656
norms used in DSE pricing; reset occurs if
657
|rho<i> - ||beta<i>||^2| > reframe*||beta<i>||^2.
658
The check is made in dseupdate.
659
*/
660
661
typedef
struct
662
{
double
inf
;
663
double
zero
;
664
double
pchk
;
665
double
pfeas
;
666
double
pfeas_scale
;
667
double
cost
;
668
double
dchk
;
669
double
dfeas
;
670
double
dfeas_scale
;
671
double
pivot
;
672
double
bogus
;
673
double
swing
;
674
double
toobig
;
675
double
purge
;
676
double
purgevar
;
677
double
reframe
; }
lptols_struct
;
678
679
#if defined(DYLP_INTERNAL) || defined(BONSAIG)
680
/*
681
A few handy macros for testing values against tolerances.
682
*/
683
#ifdef DYLP_INTERNAL
684
# ifdef BND_TOLER
685
# undef BND_TOLER
686
# endif
687
# define BND_TOLER dy_tols->pfeas
688
# ifdef INF_TOLER
689
# undef INF_TOLER
690
# endif
691
# define INF_TOLER dy_tols->inf
692
#endif
693
694
#define withintol(zz_val_zz,zz_tgt_zz,zz_tol_zz) \
695
(fabs((zz_val_zz)-(zz_tgt_zz)) <= zz_tol_zz)
696
697
#define setcleanzero(zz_val_zz,zz_tol_zz) \
698
if (fabs(zz_val_zz) < zz_tol_zz) zz_val_zz = 0
699
700
#define atbnd(zz_val_zz,zz_bnd_zz) \
701
((fabs(zz_bnd_zz) < INF_TOLER) && \
702
(fabs((zz_val_zz)-(zz_bnd_zz)) < BND_TOLER*(1.0+fabs(zz_bnd_zz))))
703
704
#define belowbnd(zz_val_zz,zz_bnd_zz) \
705
((fabs(zz_bnd_zz) < INF_TOLER) ? \
706
(((zz_bnd_zz)-(zz_val_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
707
(zz_val_zz < zz_bnd_zz))
708
709
#define abovebnd(zz_val_zz,zz_bnd_zz) \
710
((fabs(zz_bnd_zz) < INF_TOLER) ? \
711
(((zz_val_zz)-(zz_bnd_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
712
(zz_val_zz > zz_bnd_zz))
713
714
#define withinbnds(zz_lb_zz,zz_val_zz,zz_ub_zz) \
715
(!abovebnd(zz_val_zz,zz_ub_zz) && !belowbnd(zz_val_zz,zz_lb_zz))
716
717
#endif
/* DYLP_INTERNAL || BONSAIG */
718
719
#ifdef DYLP_INTERNAL
720
/*
721
Finally, a macro to decide if we should snap to a value. The notion here is
722
that the accuracy with which one can hit a target value depends on both the
723
magnitude of the target and the distance travelled to get there. On a
724
64-bit machine, IEEE FP has about 15 decimal digits of accuracy. For
725
example, if we're travelling 1.0e7 and trying to hit zero, we only have 8
726
decimal places of accuracy remaining. If we're within 1.0e-8, might as well
727
snap to 0. In practice, there's already a bit of roundoff in any nontrivial
728
calculation, so we start with the zero tolerance and scale from there.
729
730
In some cases, we only know the target, so the best we can do is
731
scale to it.
732
733
The utility of this idea is highly questionable.
734
*/
735
736
#define snaptol1(zz_tgt_zz) (dy_tols->zero*(1.0+(zz_tgt_zz)))
737
738
#define snaptol2(zz_tgt_zz,zz_dst_zz) \
739
(dy_tols->zero*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
740
741
#define snaptol3(zz_tol_zz,zz_tgt_zz,zz_dst_zz) \
742
((zz_tol_zz)*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
743
744
#endif
/* DYLP_INTERNAL */
745
746
747
748
/*
749
Enum for initial basis type.
750
751
This determines the criteria used to select the initial set of basic
752
variables during a cold start.
753
754
ibINV invalid
755
ibLOGICAL Use only logical (slack and artificial) variables
756
ibSLACK Use slack variables for inequalities. Prefer architectural
757
over artificial variables for equalities.
758
ibARCH Prefer architectural variables over logical variables.
759
*/
760
761
typedef
enum
{
ibINV
= 0,
ibLOGICAL
,
ibSLACK
,
ibARCH
}
ibtype_enum
;
762
763
/*
764
Enum for calling context.
765
766
As dylp evolves, it may well prove useful to know the context of the
767
call. Consider this an experiment. The default context is INITIALLP.
768
769
cxINV invalid (context is unknown)
770
cxSINGLELP This is a one-off call to solve a single LP from scratch.
771
cxINITIALLP This is a call to solve a single LP from scratch, but will
772
likely be followed by calls to reoptimise.
773
cxBANDC This call is made in the context of a branch-and-cut
774
algorithm.
775
*/
776
777
typedef
enum
{
cxINV
= 0,
cxSINGLELP
,
cxINITIALLP
,
cxBANDC
}
cxtype_enum
;
778
779
/*
780
lpopts_struct
781
782
This structure is used to pass option settings to dylp. Default values are
783
declared at the beginning of dy_setup.c.
784
785
Field Definition
786
----- ----------
787
context The context in which dylp is being called. See comments
788
above for cxtype_enum.
789
forcecold TRUE to force a cold start, FALSE otherwise. If set to TRUE,
790
dominates warm and hot start.
791
forcewarm TRUE to force a warm start, FALSE otherwise. If set to TRUE,
792
dominates hot start.
793
fullsys Forces the use of the full constraint system at all times. The
794
full constraint system is loaded on startup, and all constraint
795
and variable deactivation/activation is skipped. (But see the
796
finpurge option below.) (Also, this will not prevent dylp
797
from resorting to forced phase transitions, which typically
798
involve deactivation of constraints or variables. Arguably
799
this is a bad thing, and may change in the future.)
800
active Used to estimate the initial size of the dylp constraint
801
system relative to the original system.
802
vars Fraction of original variables expected to be active at
803
any time.
804
cons Fraction of original inequalities expected to be active at
805
any time.
806
initcons Specifies how inequalities will be selected to initialize the
807
active system. See extensive comments in dy_coldstart.c.
808
frac Fraction of inequalities to be used.
809
i1l Lower bound on angle to objective, first interval
810
i1lopen TRUE if the bound is open.
811
i1u Upper bound on angle to objective, first interval
812
i1uopen TRUE if the bound is open.
813
i2valid TRUE if the second interval is specified
814
i2l Lower bound on angle to objective, second interval
815
i2lopen TRUE if the bound is open.
816
i2u Upper bound on angle to objective, second interval
817
i2uopen TRUE if the bound is open.
818
coldbasis Code specifying the kind of basis built for a cold start. See
819
comments for ibtype_enum and comments in dy_coldstart.c
820
finpurge Controls whether dylp does a final deactivation of constraints
821
and/or variables. This will occur only an optimal solution is
822
found, and is not suppressed by fullsys.
823
cons TRUE to purge constraints
824
vars TRUE to purge variables
825
heroics Controls behaviour during forced primal <-> dual transitions
826
d2p TRUE to allow deactivation of basic architecturals, FALSE
827
to disallow. FALSE is recommended, and the default.
828
p2d TRUE to allow deactivation of tight constraints, FALSE
829
to disallow. FALSE is recommended, and the default.
830
flip TRUE to allow flips to regain dual feasibility, FALSE to
831
disallow. Tends to cycle; default is false.
832
coldvars If the number of active variables exceeds this value after
833
a cold start, dylp will attempt to purge variables prior to
834
the initial primal simplex run.
835
con Options related to constraint activation/deactivation
836
actlvl The constraint activation strategy
837
0: (strict) activate violated constraints,
838
lhs < rhslow or lhs > rhs
839
1: (tight) activate tight or violated constraints,
840
lhs <= rhslow or lhs >= rhs
841
actlim If non-zero, limits the number of constraints that can be
842
activated in any one call to a constraint activation
843
routine.
844
deactlvl The constraint deactivation strategy:
845
0: (normal) deactivate only inequalities i which are
846
strictly loose (i.e., slk<i> basic, not at bound).
847
1: (aggressive) normal plus inequalities which are tight
848
with y<i> = 0.
849
2: (fanatic) aggressive plus equalities with y<i> = 0
850
usedual TRUE if dual phase II is to be used to regain feasibility after
851
adding constraints, FALSE to force use of primal phase I.
852
addvar If non-zero, at most this many variables will be added in
853
any one pass through phase dyADDVAR.
854
dualadd Controls the types of activation allowed when adding variables
855
during dual simplex.
856
0: variable activation is disallowed
857
1: type 1 activation (variables that will be dual feasible
858
when activated into the nonbasic partition)
859
2: type 2 activation (variables which can be activated
860
if immediately pivoted into the basis)
861
3: type 3 activation (activate with bound-to-bound pivot)
862
See dy_dualaddvars for more extensive comments.
863
scan Partial pricing parameter. Controls the number of columns to
864
be scanned for a new candidate entering variable when the
865
candidate selected during PSE update is rejected.
866
iterlim The per phase pivot limit for the code; if set to 0, no
867
limit is enforced.
868
idlelim The number of iterations without change in the objective
869
function before the code declares the problem is stalled or
870
cycling.
871
dpsel Options to control dual pivoting. Selection of the leaving
872
variable is always handled by DSE.
873
strat: The strategy used to select the entering variable:
874
0: standard ratio test; may use anti-degen lite
875
1: multipivoting, selecting for maximum dual objective
876
improvement.
877
2: multipivoting, select for minimum predicted
878
infeasibility.
879
3: multipivoting, select infeasibility reduction if
880
possible, otherwise maximum dual objective improvement.
881
flex If TRUE, dylp will switch between strategies 1 and 3, using
882
strategy 1 unless primal magnitudes become too large.
883
allownopiv If TRUE, sequences of flips with no finishing pivot will be
884
allowed. Defaults to false, very prone to cycling.
885
ppsel Options to control primal pivoting. Selection of the entering
886
variable is always handled by PSE.
887
strat: The strategy used to select the leaving variable:
888
0: standard ratio test; may use anti-degen lite
889
1: multipivoting
890
factor The LP basis will be refactored every factor iterations, in
891
the absence of some compelling reason (typically error
892
recovery) that forces it to occur sooner.
893
check An accuracy check will be forced every check iterations, in
894
the absence of some compelling reason to do it earlier.
895
groom Controls the action taken by the basis grooming routine
896
when it makes a nontrivial status correction:
897
0: catatonic
898
1: issue a warning
899
2: issue an error message and force an abort
900
Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
901
degen TRUE to allow creation of restricted subproblems to deal with
902
degeneracy, FALSE to disallow it.
903
degenpivlim The number of successive degenerate pivots required before
904
creating a restricted subproblem.
905
degenlite Controls secondary antidegeneracy --- `antidegen lite'
906
0: (pivotabort) break ties using |abar<kj>| and abort when
907
delta<j> = 0
908
1: (pivot) break ties using |abar<kj>| but always scan the
909
full basis
910
2: (alignobj) break ties by examining the alignment of the
911
hyperplane which will become tight on the pivot; choose
912
so that movement in the direction of the objective most
913
nearly lies in the hyperplane
914
3: (alignedge) break ties by examining the alignment of the
915
hyperplane which will become tight on the pivot; choose
916
so that the direction of motion defined by the entering
917
variable most nearly lies in the hyperplane.
918
4: (perpobj) break ties by examining the alignment of the
919
hyperplane which will become tight on the pivot; choose
920
so that the normal of the hyperplane is most nearly
921
aligned with the normal of the objective
922
5: (perpedge) break ties by examining the alignment of the
923
hyperplane which will become tight on the pivot; choose
924
so that the normal of the hyperplane is most nearly
925
aligned with the direction of motion
926
Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
927
patch TRUE to allow the code to patch a singular basis, FALSE to
928
prevent patching.
929
copyorigsys Controls whether dylp makes a local copy of the original
930
system. If set to TRUE, dylp will always make a local copy.
931
If set to FALSE, a copy will be made only if necessary.
932
Scaling will trigger a local copy.
933
scaling Controls whether dylp attempts to scale the original constraint
934
system for numeric stability.
935
0: scaling is forbidden
936
1: scale the original constraint system using numeric
937
scaling vectors attached to the system
938
2: evaluate the original constraint system and scale it if
939
necessary
940
Note that even if scaling = 0, dylp may install +/-1.0 scaling
941
vectors in order to flip >= constraints to <= constraints. See
942
comments in dy_scaling.c
943
print Substructure for picky printing control. For all print options,
944
a value of 0 suppresses all information messages.
945
major Controls printing of major phase information.
946
1: a message at each phase transition.
947
scaling Controls print level during initial evaluation and scaling of
948
the original constraint system.
949
1: start and finish messages
950
2: stability measures for original and scaled matrices;
951
adjustments to tolerances.
952
setup Controls print level while creating the initial constraint
953
system for dylp.
954
1: start and finish messages.
955
2: summary information about activated constraints
956
3: messages about each constraint included in the initial
957
system.
958
4: messages about each constraint processed for the initial
959
system
960
5: messages about each variable included in the initial
961
system.
962
6: lists value and status of inactive variables with
963
nonzero values
964
crash Controls print level while crashing the basis.
965
1: start & finish messages
966
2: summary counts for logicals, architecturals, artificials
967
3: a dump of the completed basis
968
4: detailed info on the selection of each architectural
969
and artificial variable
970
pricing Controls print level for pricing of columns (rows) in primal
971
(dual) simplex.
972
1: summary messages
973
2: lists candidate list and primal variable selected for
974
entry (exit) at each pivot
975
3: lists each variable as it's added to the candidate list
976
and again when reconsidered for pivoting
977
pivoting Controls print level for selection of the leaving (entering)
978
primal variable in primal (dual) simplex and updating of
979
variables.
980
1: prints result of leaving (entering) variable selection
981
2: information about the selection of the leaving (entering)
982
variable.
983
3: more information about the selection of the leaving
984
(entering) variable.
985
4: prints the pivot column (row) before and after
986
multiplication by the basis inverse, and yet more
987
pivot selection information.
988
5: prints a line for every candidate evaluated
989
pivreject Controls print level for information related to the operation
990
of the pivot rejection mechanism.
991
1: Prints a message for each row/column added to the pivot
992
rejection list, plus other major events.
993
2: Prints a message for each row/column removed from the
994
pivot rejection list.
995
degen Controls print level for information related to the operation
996
of the antidegeneracy mechanism.
997
1: prints a message each time the antidegeneracy level
998
changes
999
2: prints a message when a true degenerate pivot is taken
1000
under duress
1001
3: prints a message when a degenerate pivot is taken
1002
4: prints anomalies as each degenerate set is formed and
1003
backed out
1004
5: prints details of each degenerate set as it's formed and
1005
backed out
1006
phase1 Controls general print level for phase 1 of primal simplex.
1007
1: messages about extraordinary events -- problem pivots, etc.
1008
2: messages about 'routine' but infrequent events --
1009
termination conditions, refactoring, unboundedness, etc.
1010
3: messages with additional details of problems encountered
1011
4: a one line log message is printed for each pivot
1012
5: summary information about infeasible variables and phase
1013
I objective coefficients; information about primal
1014
variables updated at each pivot.
1015
6: prints the primal variables after each pivot; prints
1016
infeasible variables during phase I objective construction
1017
7: prints the dual variables after each pivot; prints
1018
infeasible variables during phase I objective modification
1019
phase2 Controls general print level for phase 1 of primal simplex.
1020
1: messages about extraordinary events -- problem pivots, etc.
1021
2: messages about 'routine' but infrequent events --
1022
termination conditions, refactoring, unboundedness, etc.
1023
3: messages with additional details of problems encountered
1024
4: a one line log message is printed for each pivot
1025
5: prints the updated basic primal variables after each pivot
1026
6: prints all basic primal variables after each pivot
1027
7: prints the dual variables after each pivot.
1028
dual Controls general print level for the dual simplex. As
1029
phase2.
1030
basis Controls print level in routines working with the basis.
1031
1: summary warnings about problems: empty rows, singularity,
1032
numerical instability, etc.
1033
2: information about factoring failures and recovery actions
1034
3: warnings about individual empty rows, details of column
1035
replacement when patching a singular basis, pivot
1036
tolerance adjustments; information about pivoting failures
1037
and recovery actions
1038
4: basis stability after factoring
1039
5: basis stability after pivoting
1040
conmgmt Controls print level while dylp is in the purge/generate/
1041
activate constraint phases.
1042
1: prints the number of constraints purged, generated,
1043
& activated, and new size of constraint system.
1044
2: prints a message for each constraint purged or activated.
1045
(The cut generation routine is responsible for
1046
handling this function when it generates cuts.)
1047
3: additional details about refactoring and new values
1048
of primal and dual variables.
1049
4: prints a message about any variables affected as a side
1050
effect of constraint changes, constraints processed
1051
but not activated, and information about direction of
1052
recession and relative angle of constraints when adding
1053
constraints to an unbounded problem.
1054
5: prints a running commentary on constraint and variable
1055
shifts, inactive variables.
1056
varmgmt Controls print level while dylp is in the purge/generate/
1057
activate variable phases.
1058
1: prints the number of variables purged, generated,
1059
& activated, and new size of constraint system.
1060
2: prints a message for each variable purged & activated.
1061
(The column generation routine is responsible for
1062
handling this function when it generates new variables).
1063
3: prints a message about any constraints affected as a side
1064
effect of variable changes, variables processed but not
1065
activated, and information about direction of recession
1066
and relative angle of dual constraints when adding
1067
variables to an unbounded dual.
1068
4: prints a running commentary on constraint and variable
1069
shifts.
1070
force Controls print level when dylp is attempting to force a
1071
transition (primal -> dual, dual -> primal) or force the
1072
use of the full constraint system.
1073
1: prints a summary message giving the result of the
1074
transition attempt
1075
2: prints messages about actions taken for individual
1076
constraints and variables.
1077
3: additional information about variables and constraints
1078
examined.
1079
tableau Controls print level for routines that generate tableau
1080
vectors (beta<i>, beta<j>, abar<i>, abar<j>) for use by
1081
external clients.
1082
1: prints summary messages about the circumstances
1083
4: prints nonzeros in the final vector.
1084
5: prints nonzeros in intermediate vectors and (dy_betaj,
1085
dy_abarj only) inactive rows
1086
6: prints nonzeros of active portion in internal reference
1087
frame (dy_betaj only)
1088
rays Controls print level for routines that generate primal
1089
and dual rays for use by external clients.
1090
1: prints summary messages about vectors found.
1091
3: print information about columns / rows examined.
1092
4: print information about why a column or row was rejected.
1093
5: print nonzeros for each ray
1094
soln Controls print level for routines that generate primal and
1095
dual solutions for use by external clients.
1096
1: prints summary messages about the circumstances
1097
3: prints nonzeros in the final vector
1098
4: prints nonzeros in intermediate vectors
1099
*/
1100
1101
typedef
struct
1102
{
cxtype_enum
context
;
1103
int
scan
;
1104
int
iterlim
;
1105
int
idlelim
;
1106
struct
{
int
strat
;
1107
bool
flex
;
1108
bool
allownopiv
; } dpsel ;
1109
struct
{
int
strat ; } ppsel ;
1110
int
factor
;
1111
int
check
;
1112
int
groom
;
1113
struct
{
int
actlvl
;
1114
int
actlim
;
1115
int
deactlvl
; } con ;
1116
int
addvar
;
1117
int
dualadd
;
1118
int
coldvars
;
1119
bool
forcecold
;
1120
bool
forcewarm
;
1121
bool
usedual
;
1122
bool
degen
;
1123
int
degenpivlim
;
1124
int
degenlite
;
1125
bool
patch
;
1126
bool
fullsys
;
1127
bool
copyorigsys
;
1128
int
scaling
;
1129
struct
{
float
vars
;
1130
float
cons
; } active ;
1131
struct
{
double
frac
;
1132
bool
i1lopen
;
1133
double
i1l
;
1134
bool
i1uopen
;
1135
double
i1u
;
1136
bool
i2valid
;
1137
bool
i2lopen
;
1138
double
i2l
;
1139
bool
i2uopen
;
1140
double
i2u
; } initcons ;
1141
ibtype_enum
coldbasis
;
1142
struct
{
bool
cons
;
1143
bool
vars
; } finpurge ;
1144
struct
{
bool
d2p
;
1145
bool
p2d
;
1146
bool
flips
; } heroics ;
1147
struct
{
int
major
;
1148
int
scaling ;
1149
int
setup
;
1150
int
crash
;
1151
int
pricing
;
1152
int
pivoting
;
1153
int
pivreject
;
1154
int
degen
;
1155
int
phase1
;
1156
int
phase2
;
1157
int
dual
;
1158
int
basis
;
1159
int
conmgmt
;
1160
int
varmgmt
;
1161
int
force
;
1162
int
tableau
;
1163
int
rays
;
1164
int
soln
; }
print
; }
lpopts_struct
;
1165
1166
1167
1168
1169
/*
1170
Statistics structure, used to collect information about aspects of dylp
1171
operation beyond simple pivot counts. The data structure definition is
1172
always present, but to fill it you have to define DYLP_STATISTICS.
1173
1174
Field Definition
1175
----- ----------
1176
phasecnts[dyDONE] Array with counts for number of times each phase is
1177
executed.
1178
ini_simplex The initial simplex phase
1179
cons A set of arrays with data about individual constraints.
1180
sze Allocated capacity of the arrays.
1181
angle Angle to the objective function.
1182
actcnt Number of times constraint is activated.
1183
deactcnt Number of times constraint is deactivated.
1184
init True if constraint is active in initial system.
1185
fin True if constraint is active in final system.
1186
vars A set of arrays with data about individual variables.
1187
sze Allocated capacity of the arrays.
1188
actcnt Number of times variable is activated.
1189
deactcnt Number of times variable is deactivated.
1190
angle
1191
max Maximum angle to the objective function over all constraints.
1192
min Minimum angle to the objective function over all constraints.
1193
hist[*] Histogram of angles of constraints to the objective function.
1194
There are DYSTATS_HISTBINS bins. Currently, 37 bins: 36 bins
1195
spanning 5 degrees of angle, and a dedicated 90 degree bin.
1196
1197
factor Tracks how well we're doing with respect to refactoring the
1198
basis.
1199
cnt Number of time the basis has been refactored.
1200
prevpiv Pivot count at last refactorisation.
1201
avgpivs Average number of pivots between basis refactorisations.
1202
maxpivs Maximum number of pivots between basis refactorisations.
1203
1204
pivrej Statistics about the pivot rejection list and punts.
1205
max maximum number of entries on the pivot rejection list
1206
mad total number of entries attributed to mad pivots
1207
sing total number of entries attributed to singular pivots
1208
pivtol_red total number of times the pivot tolerance was reduced
1209
min_pivtol the minimum pivot tolerance used
1210
puntcall total number of calls to dealWithPunt
1211
puntret total number of dyrPUNT returns recommended
1212
1213
dmulti Tracks the dual multipivot algorithm. All fields except cnt are
1214
totals; divide by cnt to get averages.
1215
flippable Number of flippable variables in the constraint system.
1216
cnt Total calls to dualmultiin
1217
cands Number of candidates queued for evaluation for entry
1218
promote Number of calls that resulted in promoting a sane pivot
1219
over an unstable pivot.
1220
nontrivial Number of times that the initial scan and sort left
1221
multiple candidates for further evaluation.
1222
evals Actual number of candidates evaluated (ftran'd column)
1223
flips Number of bound-to-bound flips performed
1224
pivrnk Index in the list of candidates of the candidate finally
1225
selected for pivoting.
1226
maxrnk Maximum index selected for pivoting.
1227
1228
pmulti Tracks the primal multipivot algorithm.
1229
cnt Total calls to primalmultiin
1230
cands Number of candidates queued for evaluation to leave
1231
nontrivial Number of times that the candidate list was sorted
1232
promote Number of calls that resulted in promoting a sane pivot
1233
over an unstable pivot.
1234
1235
infeas Statistics on resolution of infeasibility in primal phase I.
1236
Basically, what we're interested in tracking is the number
1237
of infeasible variables and the number of pivots between a
1238
change in the number of infeasible variables. We're interested
1239
in separating the case of 1 variable from 2 or more, because
1240
the latter requires vastly more calculation. A little care
1241
is required because phase I can run many times.
1242
1243
prevpiv The pivot count (tot.iters) at the previous change.
1244
maxcnt The maximum number of infeasible variables encountered (this
1245
is not strictly monotonic, as dylp may enter phase I many
1246
times due to activating violated constraints).
1247
totpivs The total number of pivots expended in phase I.
1248
maxpivs The maximum number of pivots with no change in the number of
1249
feasible variables.
1250
chgcnt1 The number of times that the number of infeasible variables
1251
changed and reduced costs did not have to be recalculated
1252
(specifically, exactly one variable became feasible, and it
1253
left the basis as it did so).
1254
chgcnt2 The number of times that the number of infeasible variables
1255
changed in such a way as to require recalculation of the
1256
reduced costs.
1257
1258
[dp]degen[*] Array of stats for each restricted subproblem nesting level,
1259
with separate arrays for dual (ddegen) and primal (pdegen).
1260
degen[0].cnt is used to hold the maximum nesting level.
1261
cnt Number of times this nesting level was entered.
1262
avgsiz The average number of variables in a restricted subproblem.
1263
Kept by iterative update, as avg<k+1> = (avg<k>*k+size)/(k+1).
1264
Suffers from cumulative loss of accuracy, but it'll do for
1265
our purposes.
1266
maxsiz The maximum number of variables in a restricted subproblem.
1267
totpivs Total number of pivots at or above this nesting level.
1268
avgpivs Average number of pivots at or above this nesting level.
1269
maxpivs Maximum number of pivots for any one instance at or above
1270
this nesting level.
1271
1272
tot, p1, p2, d2 Iteration and pivot counts, total and for each
1273
individual phase. These are copied over from
1274
dy_lp (lp_struct) at the end of the run, so that
1275
they can be printed by dumpstats.
1276
1277
DYSTATS_MAXDEGEN is the maximum number of levels of nesting accommodated by
1278
antidegeneracy statistics and debugging structures. The actual algorithm
1279
has no inherent limitation.
1280
1281
DYSTATS_HISTBINS is the number of bins for constraint angles. It should be an
1282
odd number. Each bin will span 180/(DYSTATS_HISTBINS-1) degrees, with the
1283
final bin reserved for constraints at 90 degrees. For example, a value of 37
1284
gives 180/(37-1) = 5 degrees per bin.
1285
*/
1286
1287
#define DYSTATS_MAXDEGEN 25
1288
#define DYSTATS_HISTBINS 37
1289
1290
typedef
struct
{
1291
int
phasecnts[
dyDONE
+1] ;
1292
dyphase_enum
ini_simplex
;
1293
struct
{
int
sze
;
1294
double
*
angle
;
1295
int
*
actcnt
;
1296
int
*
deactcnt
;
1297
bool
*
init
;
1298
bool
*
fin
; } cons ;
1299
struct
{
int
sze ;
1300
int
*actcnt ;
1301
int
*deactcnt ; } vars ;
1302
struct
{
float
max
;
1303
float
min
;
1304
int
hist[
DYSTATS_HISTBINS
] ; } angle ;
1305
struct
{
int
cnt
;
1306
int
prevpiv
;
1307
float
avgpivs
;
1308
int
maxpivs
; } factor ;
1309
struct
{
int
max
;
1310
int
mad
;
1311
int
sing
;
1312
int
pivtol_red
;
1313
double
min_pivtol
;
1314
int
puntcall
;
1315
int
puntret
; } pivrej ;
1316
struct
{
int
flippable
;
1317
int
cnt ;
1318
int
cands
;
1319
int
promote
;
1320
int
nontrivial
;
1321
int
evals
;
1322
int
flips
;
1323
int
pivrnks
;
1324
int
maxrnk
; } dmulti ;
1325
struct
{
int
cnt ;
1326
int
cands ;
1327
int
nontrivial ;
1328
int
promote ; } pmulti ;
1329
struct
{
int
prevpiv ;
1330
int
maxcnt
;
1331
int
totpivs
;
1332
int
maxpivs ;
1333
int
chgcnt1
;
1334
int
chgcnt2
; } infeas ;
1335
struct
{
int
cnt ;
1336
float
avgsiz
;
1337
int
maxsiz
;
1338
int
totpivs ;
1339
float
avgpivs ;
1340
int
maxpivs ; } pdegen[
DYSTATS_MAXDEGEN
] ;
1341
struct
{
int
cnt ;
1342
float
avgsiz ;
1343
int
maxsiz ;
1344
int
totpivs ;
1345
float
avgpivs ;
1346
int
maxpivs ; } ddegen[
DYSTATS_MAXDEGEN
] ;
1347
struct
{
int
iters
;
1348
int
pivs
; } tot ;
1349
struct
{
int
iters ;
1350
int
pivs ; } p1 ;
1351
struct
{
int
iters ;
1352
int
pivs ; } p2 ;
1353
struct
{
int
iters ;
1354
int
pivs ; } d2 ; }
lpstats_struct
;
1355
1356
1357
1358
#ifdef DYLP_INTERNAL
1359
1360
/*
1361
Macros to determine whether a constraint or variable is active, and whether
1362
it's eligible for activation. Coding is explained below for dy_origcons and
1363
dy_origvars. The main purpose served by these macros is to make it easy to
1364
find activiation/deactivation points in the code, should the conventions ever
1365
change.
1366
*/
1367
1368
#define ACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] > 0)
1369
#define INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] <= 0)
1370
#define LOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] == 0)
1371
#define MARK_UNLOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = -1)
1372
#define MARK_INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = 0)
1373
1374
#define ACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] > 0)
1375
#define INACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] <= 0)
1376
#define LOADABLE_VAR(zz_vndx_zz) \
1377
((dy_origvars[(zz_vndx_zz)] < 0) && \
1378
flgoff(((flags) -dy_origvars[(zz_vndx_zz)]),vstatNOLOAD|vstatNBFX))
1379
#define MARK_INACTIVE_VAR(zz_vndx_zz,zz_val_zz) \
1380
(dy_origvars[(zz_vndx_zz)] = (zz_val_zz))
1381
1382
1383
/*
1384
dy_logchn i/o id for the execution log file
1385
dy_gtxecho controls echoing of generated text to stdout
1386
*/
1387
1388
extern
ioid
dy_logchn
;
1389
extern
bool
dy_gtxecho
;
1390
1391
1392
/*
1393
lp_struct
1394
1395
This structure is the control structure for an LP problem within dylp.
1396
1397
Field Definition
1398
----- ----------
1399
phase Current phase of the dynamic simplex algorithm.
1400
lpret Return code from the most recent simplex execution.
1401
1402
z Value of the objective function (includes inactzcorr).
1403
inactzcorr Correction to the objective function due to inactive variables
1404
with non-zero values.
1405
1406
simplex Simplex algorithm status and control
1407
active currently active or most recently completed
1408
next currently active or to be started
1409
init_pse TRUE if the PSE structures need to be reinitialised,
1410
FALSE otherwise
1411
init_dse TRUE if the DSE structures need to be reinitialised,
1412
FALSE otherwise
1413
These fields are used to determine when to update or
1414
reinitialise the PSE and DSE data structures. Active and next
1415
must be valid during the purge/gen/add variable/constraint
1416
cycles.
1417
1418
A word on infeas and infeascnt: They are guaranteed accurate
1419
only immediately after initialisation and following a primal
1420
feasibility check.
1421
1422
infeas Total infeasibility = SUM{j} max(0,x<j>-ub<j>,lb<j>-x<j>)
1423
infeascnt The number of infeasible variables; refreshed when dy_accchk
1424
is asked to do a primal feasibility check.
1425
1426
ubnd Substructure for information on unbounded or pseudo-unbounded
1427
problems.
1428
ndx The index of the variable fingered for causing unboundedness
1429
or pseudo-unboundedness (swing).
1430
ratio The growth ratio.
1431
1432
p1obj The following fields relate to handling of the phase I
1433
objective function.
1434
installed TRUE if the phase I objective is currently installed
1435
infcnt Tracks the number of variables incorporated in p1obj which
1436
remain infeasible.
1437
infvars_sze Allocated size of the infvars vector.
1438
infvars Vector of indices of infeasible variables incorporated in the
1439
phase I objective.
1440
p1obj Pointer to the phase I objective (temporary storage while
1441
the phase II objective is installed).
1442
p2obj Pointer to the phase II objective (temporary storage while
1443
the phase I objective is installed).
1444
1445
A word on pivot and iteration counts: Iteration counts tally
1446
iterations of the pivoting loop, successful or not. Pivot
1447
counts tally successful bound-to-bound or change-of-basis
1448
pivots. Pretty much all messages will give tot.iters, so that
1449
it's possible to track the progress of an LP. Iterf has an
1450
entirely different function -- it's tracking the accumulation
1451
of eta matrices in the basis representation.
1452
1453
sys Substructure for dynamic system modification status.
1454
forcedfull Set to TRUE if the full system has been forced in state
1455
dyFORCEFULL. This should happen at most once, so if we
1456
enter dyFORCEFULL and forcedfull == TRUE, it's fatal.
1457
cons
1458
loadable Count of constraints which could be activated
1459
unloadable Count of constraints which are ineligible for activation
1460
(empty constraints and nonbinding rows)
1461
vars
1462
loadable Count of variables which could be activated
1463
unloadable Count of variables which are ineligible for activation
1464
(nonbasic fixed)
1465
1466
tot Total simplex iterations and pivots, all phases
1467
iters
1468
pivs
1469
p1 Primal phase I iterations and pivots.
1470
iters
1471
pivs
1472
p2 Primal phase II iterations and pivots.
1473
iters
1474
pivs
1475
d2 Dual phase II iterations and pivots.
1476
iters
1477
pivs
1478
1479
pivok Set to TRUE in dy_{primal|dual}pivot if the current iteration
1480
is a successful pivot. Cleared to FALSE at the head of
1481
dy_duenna.
1482
prev_pivok Set to pivok at head of dy_duenna. Provides status of just
1483
completed pivot for post-Duenna decisions.
1484
1485
basis Various fields related to basis change, refactoring, etc.
1486
1487
etas The number of basis changes (hence eta matrices) since the
1488
the basis was last factored. Used to schedule periodic
1489
factoring of the basis. Reset to 0 each time the basis is
1490
factored.
1491
pivs The number of basis pivots since entry into a primal or dual
1492
simplex phase (excludes bound-to-bound simplex `pivots').
1493
Used when deciding whether to remove variables from the pivot
1494
reject list, and whether to pop out of a simplex phase due to
1495
excessive swing.
1496
dinf Number of successive refactors with dual infeasibility.
1497
Cleared at the start of a simplex phase.
1498
Incremented/cleared in dy_accchk iff a dual feasibility check
1499
is performed.
1500
1501
degen Activation level of antidegeneracy algorithm. Held at 0 when
1502
the antidegeneracy algorithm is not active. Incremented each
1503
time a restricted subproblem is formed, and decremented when
1504
the restriction is backed out. (Values > 1 indicate that
1505
degeneracy recurred while working on a restricted subproblem,
1506
resulting in further restriction.)
1507
degenpivcnt The number of successive degenerate pivots.
1508
1509
idlecnt The number of cycles since the objective has changed.
1510
1511
lastz Previous objective value for various activities; used to
1512
detect and suppress loops.
1513
piv Objective at last pivot (detects stalling)
1514
cd Objective at last entry into constraint deactivation
1515
(dyPURGECON) (detects constraint activate/deactivate loops)
1516
vd Objective at last entry into variable deactivation
1517
(dyPURGEVAR) (detects variable activate/deactivate loops)
1518
fp Objective at last entry into force primal (dyFORCEPRIMAL)
1519
(detects constraint activate/deactivate loops)
1520
fd Objective at last entry into force dual (dyFORCEDUAL)
1521
(detects variable activate/deactivate loops)
1522
1523
prim Primal variable information
1524
norm1 1-norm of basic primal variables inv(B)b
1525
norm2 2-norm of basic primal variables
1526
max inf-norm (max) of basic primal variables
1527
maxndx index of max primal variable
1528
1529
dual Dual variable information
1530
norm1 1-norm of dual variables c<B>inv(B)
1531
norm2 2-norm of dual variables
1532
max inf-norm (max) of dual variables
1533
maxndx index of max dual variable
1534
1535
*/
1536
1537
typedef
struct
1538
{
dyphase_enum
phase ;
1539
lpret_enum
lpret ;
1540
double
z ;
1541
double
inactzcorr ;
1542
struct
{
dyphase_enum
active ;
1543
dyphase_enum
next ;
1544
bool
init_pse ;
1545
bool
init_dse ; } simplex ;
1546
double
infeas ;
1547
int
infeascnt ;
1548
struct
{
int
ndx ;
1549
double
ratio ; } ubnd ;
1550
struct
{
bool
installed ;
1551
int
infcnt ;
1552
int
infvars_sze ;
1553
int
*infvars ;
1554
double
*p1obj ;
1555
double
*p2obj ; } p1obj ;
1556
struct
{
struct
{
int
loadable ;
1557
int
unloadable ; } cons ;
1558
struct
{
int
loadable ;
1559
int
unloadable ; } vars ;
1560
bool
forcedfull ; } sys ;
1561
struct
{
int
iters ;
1562
int
pivs ; } tot ;
1563
struct
{
int
iters ;
1564
int
pivs ; } p1 ;
1565
struct
{
int
iters ;
1566
int
pivs ; } p2 ;
1567
struct
{
int
iters ;
1568
int
pivs ; } d2 ;
1569
bool
pivok ;
1570
bool
prev_pivok ;
1571
struct
{
int
etas ;
1572
int
pivs ;
1573
int
dinf ; } basis ;
1574
int
degen ;
1575
int
degenpivcnt ;
1576
int
idlecnt ;
1577
struct
{
double
piv ;
1578
double
cd ;
1579
double
vd ;
1580
double
fp ;
1581
double
fd ; } lastz ;
1582
struct
{
double
norm1 ;
1583
double
norm2 ;
1584
double
max ;
1585
int
maxndx ; } prim ;
1586
struct
{
double
norm1 ;
1587
double
norm2 ;
1588
double
max ;
1589
int
maxndx ; } dual ;
1590
} lp_struct ;
1591
1592
1593
/*
1594
Declarations global to the dylp implementation but not visible outside of
1595
it. With this we can avoid passing huge numbers of parameters and/or
1596
unpacking a structure on a regular basis. Unless otherwise indicated, indices
1597
are in the dy_sys (active system) frame of reference.
1598
1599
dy_retained TRUE if dylp thinks that the structures below are valid, FALSE
1600
otherwise.
1601
1602
Main structures
1603
---------------
1604
dy_lp: The lp control structure for dylp.
1605
dy_sys: The active constraint system; initialised in dylp:startup
1606
dy_tols: Tolerances in effect for dylp; initialised in
1607
dylp:dylp from orig_tols.
1608
dy_opts: Options in effect for dylp; initialised in
1609
dylp:dylp to point to same structure as orig_opts.
1610
dy_stats Statistics structure for dylp; initialised in dylp:dylp to
1611
point ot the same structure as orig_stats.
1612
1613
Constraint & Variable Management
1614
--------------------------------
1615
dy_actvars: The active variables. Indexed in dy_sys frame, contains
1616
indices in orig_sys frame. Attached to dy_sys.
1617
Entries for logical variables (1 <= j <= concnt) are
1618
meaningless.
1619
dy_actcons: The active constraints. Indexed in dy_sys frame, contains
1620
indices in orig_sys frame. Attached to dy_sys.
1621
dy_origvars: Status of the original architectural variables.
1622
* A value of 0 indicates the entry hasn't been processed.
1623
Should never happen.
1624
* If the variable is active, the entry contains the index
1625
of the variable in the dy_sys frame.
1626
* If the variable is inactive, the coding is the negative of
1627
the vstat flags, limited to the nonbasic status values
1628
vstatNBFR, vstatNBFX, vstatNBLB, or vstatNBUB, and the
1629
qualifier vstatNOLOAD.
1630
Indexed in orig_sys frame. Attached to orig_sys.
1631
dy_origcons: Status of the original constraints.
1632
* If the constraint is active, the entry contains the index
1633
of the constraint in the dy_sys frame.
1634
* If the constraint is inactive, contains 0.
1635
* If the constraint cannot be activated, contains a negative
1636
value.
1637
Indexed in orig_sys frame. Attached to orig_sys.
1638
1639
Note that there are macros defined to test whether a variable or constraint
1640
is inactive, and whether it's eligible for activation. Use them!
1641
1642
Basis Management
1643
----------------
1644
dy_basis: The basis vector. Indexed by basis position, attached to
1645
dy_sys.
1646
dy_var2basis: Translates a variable index to a basis pos'n. Indexed by
1647
column, attached to dy_sys. Entries for nonbasic variables
1648
must be kept at 0.
1649
dy_status: The status vector. Indexed by column, attached to dy_sys.
1650
1651
Primal and Dual Variables
1652
-------------------------
1653
dy_x: The values of all primal variables. Indexed by column,
1654
attached to dy_sys. Values of nonbasic variables must always
1655
be correct (to allow uniform handling of normal nonbasic
1656
variables and superbasic variables). Values of basic
1657
variables will retain unperturbed values while the
1658
antidegeneracy mechanism is active -- this allows the
1659
perturbation to be quickly backed out.
1660
dy_xbasic: The values of the basic variables. Indexed by basis pos'n,
1661
attached to dy_sys.
1662
dy_y: The dual variables. Indexed by basis pos'n, attached to
1663
dy_sys.
1664
1665
Projected Steepest Edge (PSE) Pricing
1666
-------------------------------------
1667
dy_cbar: Iteratively updated vector of reduced costs. Indexed by column,
1668
attached to dy_sys.
1669
dy_gamma: Iteratively updated vector of column norms ||abar<j>||^2.
1670
Indexed by column, attached to dy_sys.
1671
dy_frame: Boolean vector which indicates if a given variable is in the
1672
current frame of reference. Indexed by column, attached to
1673
dy_sys.
1674
1675
Dual Steepest Edge (DSE) Pricing
1676
--------------------------------
1677
dy_rho: Iteratively updated vector of row norms ||beta<i>||^2.
1678
Indexed by basis position, attached to dy_sys.
1679
1680
DSE pricing also makes use of dy_xbasic (the reduced costs of the dual
1681
variables), and maintains dy_cbar.
1682
1683
Antidegeneracy
1684
--------------
1685
dy_brkout: Specifies the direction a variable needs to move to escape
1686
from a degenerate vertex. Indexed by basis pos'n, attached
1687
to dy_sys.
1688
dy_degenset: Specifies the set of constraints (equivalently, basic
1689
variables) perturbed at each level of the antidegeneracy
1690
algorithm. Indexed by basis pos'n, attached to dy_sys. The
1691
entry for a constraint is the highest level of degenerate set
1692
which includes the constraint. If the entry is 0, the
1693
constraint is not involved in degeneracy.
1694
dy_ddegenset: Specifies the set of dual constraints (equivalently, reduced
1695
costs) perturbed at each level of the antidegeneracy
1696
algorithm. Indexed by variable index, attached to dy_sys.
1697
The entry for a dual constraint is the highest level of
1698
degenerate set which includes the constraint. If the entry is
1699
0, the constraint is not involved in degeneracy.
1700
*/
1701
1702
extern
bool
dy_retained ;
1703
1704
extern
lp_struct *dy_lp ;
1705
extern
consys_struct
*dy_sys ;
1706
extern
lptols_struct
*dy_tols ;
1707
extern
lpopts_struct
*dy_opts ;
1708
extern
int
*dy_actvars,*dy_actcons,*dy_origvars,*dy_origcons,
1709
*dy_basis,*dy_var2basis,
1710
*dy_brkout,*dy_degenset,*dy_ddegenset ;
1711
extern
flags
*dy_status ;
1712
extern
double
*dy_x,*dy_xbasic,*dy_y,*dy_cbar,*dy_gamma,*dy_rho ;
1713
extern
bool
*dy_frame ;
1714
1715
extern
lpstats_struct
*dy_stats ;
1716
1717
/*
1718
dy_scaling.c
1719
*/
1720
1721
extern
bool
dy_initlclsystem(
lpprob_struct
*orig_lp,
bool
hotstart) ;
1722
extern
void
dy_freelclsystem(
lpprob_struct
*orig_lp,
bool
freesys) ;
1723
extern
bool
dy_isscaled(
void
) ;
1724
extern
void
dy_scaling_vectors(
const
double
**rscale,
const
double
**cscale) ;
1725
extern
consys_struct
*dy_scaled_origsys() ;
1726
1727
/*
1728
dy_coldstart.c
1729
*/
1730
1731
extern
dyret_enum
dy_coldstart(
consys_struct
*orig_sys),
1732
dy_crash(
void
) ;
1733
1734
/*
1735
dy_warmstart.c
1736
*/
1737
1738
extern
dyret_enum
dy_warmstart(
lpprob_struct
*orig_lp) ;
1739
1740
/*
1741
dy_hotstart.c
1742
*/
1743
1744
extern
dyret_enum
dy_hotstart(
lpprob_struct
*orig_lp) ;
1745
1746
/*
1747
dy_basis.c
1748
*/
1749
1750
extern
dyret_enum
dy_factor(
flags
*calcflgs),
1751
dy_pivot(
int
xipos,
double
abarij,
double
maxabarj) ;
1752
extern
double
dy_chkpiv(
double
abarij,
double
maxabarj) ;
1753
extern
void
dy_btran(
double
*col), dy_ftran(
double
*col,
bool
save) ;
1754
extern
bool
dy_setpivparms(
int
curdelta,
int
mindelta) ;
1755
extern
char
*dy_prtpivparms(
int
lvl) ;
1756
1757
/*
1758
dy_bound.c
1759
*/
1760
1761
extern
int
dy_activateBndCons(
consys_struct
*orig_sys) ;
1762
extern
int
dy_dualaddvars(
consys_struct
*orig_sys) ;
1763
1764
/*
1765
dy_conmgmt.c
1766
*/
1767
1768
extern
bool
dy_loadcon(
consys_struct
*orig_sys,
int
orig_ndx,
1769
bool
genvars,
int
*inactndxs) ;
1770
extern
bool
dy_deactNBLogPrimCon(
consys_struct
*orig_sys,
int
i),
1771
dy_deactBLogPrimCon(
consys_struct
*orig_sys,
int
i),
1772
dy_actBLogPrimCon(
consys_struct
*orig_sys,
int
i,
1773
int
*inactvars),
1774
dy_actBLogPrimConList(
consys_struct
*orig_sys,
1775
int
cnt,
int
*ocndxs,
int
**inactvars) ;
1776
extern
int
dy_deactivateCons(
consys_struct
*orig_sys),
1777
dy_activateCons(
consys_struct
*orig_sys,
bool
with_vars) ;
1778
1779
/*
1780
dy_varmgmt.c
1781
*/
1782
1783
extern
bool
dy_actNBPrimArch(
consys_struct
*orig_sys,
int
ovndx),
1784
dy_actNBPrimArchList(
consys_struct
*orig_sys,
1785
int
cnt,
int
*ovndxs),
1786
dy_deactBPrimArch(
consys_struct
*orig_sys,
int
ovndx),
1787
dy_deactNBPrimArch(
consys_struct
*orig_sys,
int
ovndx) ;
1788
extern
int
dy_deactivateVars(
consys_struct
*orig_sys),
1789
dy_activateVars(
consys_struct
*orig_sys,
int
*candidates) ;
1790
1791
/*
1792
dy_primalpivot.c
1793
*/
1794
1795
extern
dyret_enum
dy_primalin(
int
initcol,
int
scan,
int
*xjndx,
int
*nextcol),
1796
dy_primalpivot(
int
xjndx,
int
indir,
int
*xindx,
int
*outdir,
1797
double
*abarij,
double
*delta,
int
*xjcand),
1798
dy_degenout(
int
level) ;
1799
1800
/*
1801
dy_duenna.c
1802
*/
1803
1804
extern
dyret_enum
dy_duenna(
dyret_enum
pivresult,
int
xjndx,
int
xindx,
1805
int
xjcand,
int
xicand),
1806
dy_accchk(
flags
*checks) ;
1807
1808
/*
1809
dy_pivreject.c
1810
*/
1811
1812
extern
dyret_enum
dy_addtopivrej(
int
xkndx,
dyret_enum
why,
1813
double
abarij,
double
maxabarij),
1814
dy_dealWithPunt(
void
) ;
1815
extern
bool
dy_clrpivrej(
int
*entries) ;
1816
extern
void
dy_checkpivtol(
void
) ;
1817
extern
void
dy_initpivrej(
int
sze), dy_freepivrej(
void
) ;
1818
1819
1820
/*
1821
dy_primal.c
1822
*/
1823
1824
extern
lpret_enum
dy_primal(
void
) ;
1825
extern
bool
dy_initp1obj(
void
),dy_swapobjs(
dyphase_enum
phase) ;
1826
1827
/*
1828
dy_dualpivot.c
1829
*/
1830
1831
extern
dyret_enum
1832
dy_dualout(
int
*xindx),
1833
dy_dualpivot(
int
xindx,
int
outdir,
1834
int
*p_xjndx,
int
*p_indir,
double
*p_cbarj,
1835
double
*p_abarij,
double
*p_delta,
int
*xicand),
1836
dy_dualdegenout(
int
level) ;
1837
1838
/*
1839
dy_dual.c
1840
*/
1841
1842
extern
lpret_enum
dy_dual(
void
) ;
1843
1844
#endif
/* DYLP_INTERNAL */
1845
1846
/*
1847
dy_setup.c
1848
*/
1849
1850
extern
void
dy_defaults
(
lpopts_struct
**opts,
lptols_struct
**tols),
1851
dy_checkdefaults
(
consys_struct
*sys,
1852
lpopts_struct
*opts,
lptols_struct
*tols),
1853
dy_setprintopts
(
int
lvl,
lpopts_struct
*opts) ;
1854
1855
1856
/*
1857
dylp.c
1858
*/
1859
1860
extern
lpret_enum
dylp
(
lpprob_struct
*orig_lp,
lpopts_struct
*orig_opts,
1861
lptols_struct
*orig_tols,
lpstats_struct
*orig_stats) ;
1862
1863
/*
1864
dylp_utils.c
1865
*/
1866
1867
#ifdef DYLP_INTERNAL
1868
1869
extern
lpret_enum
dyret2lpret(
dyret_enum
dyret) ;
1870
extern
dyret_enum
dy_updateprimals(
int
j,
double
deltaj,
double
*p_abarj) ;
1871
extern
bool
dy_reducerhs(
double
*rhs,
bool
init),
1872
dy_calcprimals(
void
),dy_calccbar(
void
) ;
1873
extern
void
dy_calcduals(
void
),dy_setbasicstatus(
void
),
1874
dy_dseinit(
void
),dy_pseinit(
void
) ;
1875
extern
double
dy_calcobj(
void
),dy_calcdualobj(
void
),dy_calcpinfeas(
void
) ;
1876
extern
void
dy_finishup(
lpprob_struct
*orig_lp,
dyphase_enum
phase) ;
1877
1878
#ifdef DYLP_PARANOIA
1879
1880
extern
bool
dy_chkstatus(
int
vndx),
1881
dy_chkdysys(
consys_struct
*orig_sys) ;
1882
extern
void
dy_chkdual(
int
lvl) ;
1883
1884
#endif
1885
1886
#endif
/* DYLP_INTERNAL */
1887
1888
extern
bool
dy_dupbasis
(
int
dst_basissze,
basis_struct
**p_dst_basis,
1889
basis_struct
*src_basis,
int
dst_statussze,
1890
flags
**p_dst_status,
1891
int
src_statuslen,
flags
*src_status) ;
1892
extern
void
dy_freesoln
(
lpprob_struct
*lpprob) ;
1893
1894
/*
1895
dy_penalty.c
1896
*/
1897
1898
extern
bool
dy_pricenbvars
(
lpprob_struct
*orig_lp,
flags
priceme,
1899
double
**p_ocbar,
int
*p_nbcnt,
int
**p_nbvars),
1900
dy_pricedualpiv
(
lpprob_struct
*orig_lp,
int
oxindx,
1901
double
nubi,
double
xi,
double
nlbi,
1902
int
nbcnt,
int
*nbvars,
1903
double
*cbar,
double
*p_upeni,
double
*p_dpeni) ;
1904
1905
/*
1906
dy_tableau.c
1907
*/
1908
1909
extern
bool
dy_abarj
(
lpprob_struct
*orig_lp,
int
tgt_j,
double
**p_abarj) ;
1910
extern
bool
dy_betaj
(
lpprob_struct
*orig_lp,
int
tgt_j,
double
**p_betaj) ;
1911
extern
bool
dy_betai
(
lpprob_struct
*orig_lp,
int
tgt_i,
double
**p_betai) ;
1912
extern
bool
dy_abari
(
lpprob_struct
*orig_lp,
int
tgt_i,
double
**p_abari,
1913
double
**p_betai) ;
1914
1915
/*
1916
dy_rays.c
1917
*/
1918
1919
extern
bool
dy_primalRays
(
lpprob_struct
*orig_lp,
1920
int
*p_numRays,
double
***p_rays) ;
1921
extern
bool
dy_dualRays
(
lpprob_struct
*orig_lp,
bool
fullRay,
1922
int
*p_numRays,
double
***p_rays,
bool
trueDuals) ;
1923
1924
/*
1925
dy_solutions.c
1926
*/
1927
1928
extern
void
dy_colDuals
(
lpprob_struct
*orig_lp,
double
**p_cbar,
1929
bool
trueDuals) ;
1930
extern
void
dy_rowDuals
(
lpprob_struct
*orig_lp,
double
**p_y,
1931
bool
trueDuals) ;
1932
1933
extern
void
dy_colPrimals
(
lpprob_struct
*orig_lp,
double
**p_x) ;
1934
extern
void
dy_rowPrimals
(
lpprob_struct
*orig_lp,
1935
double
**p_xB,
int
**p_indB) ;
1936
extern
void
dy_logPrimals
(
lpprob_struct
*orig_lp,
double
**p_logx) ;
1937
1938
extern
void
dy_colStatus
(
lpprob_struct
*orig_lp,
flags
**p_colstat) ;
1939
extern
void
dy_logStatus
(
lpprob_struct
*orig_lp,
flags
**p_logstat) ;
1940
1941
extern
bool
dy_expandxopt
(
lpprob_struct
*lp,
double
**p_xopt) ;
1942
1943
/*
1944
dylp_io.c
1945
*/
1946
1947
#include <
dylib_io.h
>
1948
1949
#ifdef DYLP_INTERNAL
1950
1951
extern
void
dy_logpivot(
dyret_enum
result,
int
xjndx,
int
indir,
double
cbarj,
1952
int
xindx,
int
outdir,
double
abarij,
double
delta) ;
1953
extern
const
char
*dy_prtdyret(
dyret_enum
retcode) ;
1954
1955
#endif
/* DYLP_INTERNAL */
1956
1957
extern
const
char
*
dy_prtlpret
(
lpret_enum
lpret),
1958
*
dy_prtlpphase
(
dyphase_enum
phase,
bool
abbrv) ;
1959
extern
char
*
dy_prtvstat
(
flags
status) ;
1960
extern
bool
dy_dumpcompact
(
ioid
chn,
bool
echo,
lpprob_struct
*soln,
1961
bool
nbzeros) ;
1962
1963
/*
1964
dy_statistics.c
1965
1966
These routines are compiled unconditionally, but note that the compile-time
1967
symbol DYLP_STATISTICS must be defined before dylp will actually take the
1968
time to collect detailed statistics. See dy_statistics.c for additional
1969
instructions.
1970
*/
1971
1972
extern
void
dy_initstats
(
lpstats_struct
**p_lpstats,
consys_struct
*orig_sys),
1973
dy_dumpstats
(
ioid
chn,
bool
echo,
lpstats_struct
*lpstats,
1974
consys_struct
*orig_sys),
1975
dy_freestats
(
lpstats_struct
**p_lpstats) ;
1976
1977
#ifdef DYLP_INTERNAL
1978
1979
extern
void
dy_finalstats(
lpstats_struct
*lpstats) ;
1980
1981
#endif
/* DYLP_INTERNAL */
1982
1983
1984
#endif
/* _DYLP_H */
Generated on Tue Mar 1 2016 22:36:49 by
1.8.4