DyLP 1.10.4
Loading...
Searching...
No Matches
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 Eclipse Public License (EPL).
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 407 2010-12-31 20:48:48Z 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
170typedef enum { lpFATAL = -1, lpINV = 0,
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
212typedef enum { dyINV = 0, dyINIT,
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
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
451typedef struct { int cndx ; int vndx ; } basisel_struct ;
452
453typedef struct
454{ int len ;
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 owner ID of the owner of this problem.
538 ctlopts Control and status flags.
539 phase (i) If set to dyDONE, dylp will free any retained data
540 structures and return. Any other value is ignored.
541 (o) Termination phase of the dynamic simplex algorithm;
542 should be dyDONE unless something screws up, in which
543 case it'll be dyINV.
544 lpret Return code from the simplex routine.
545 obj For lpOPTIMAL, the value of the objective function.
546 For lpINFEAS, the total infeasibility.
547 For lpUNBOUNDED, the index of the unbounded variable, negated
548 if the variable can decrease without bound, positive if it
549 can increase without bound. The logical for constraint i
550 is represented as n+i.
551 Otherwise, undefined.
552 iters The number of simplex iterations.
553 consys The constraint system.
554 fullsys True if the active constraint system is the full system, false
555 otherwise.
556 basis (i) Initial basis.
557 (o) Final basis.
558 status (i) Initial status vector.
559 (o) Final status vector.
560 x (i) No values used, but a vector can be supplied.
561 (o) The values of the basic variables (indexed by basis
562 position).
563 y (i) No values used, but a vector can be supplied.
564 (o) The values of the dual variables (indexed by basis
565 position).
566 actvars There is one entry for each variable, coded TRUE if the
567 variable is active, FALSE otherwise. The vector supplied on
568 input will be overwritten on output.
569 (i) Variables to be activated at startup. Used only for a
570 warm start. Validity is indicated by the lpctlACTVARSIN
571 flag. A vector can be supplied strictly for output use.
572 (o) The current active variables. Will be returned only if
573 requested by the lpctlACTVARSOUT flag. If the vector is
574 valid on return, lpctlACTVARSOUT will remain set,
575 otherwise it will be reset.
576
577 colsze Allocated column capacity (length of status vector).
578 rowsze Allocated row capacity (length of basis, x, and y vectors).
579
580
581 Note that dylp will reallocate status, basis->el, actvars, x, and y, if the
582 vectors supplied at startup are too small to report the solution. Don't set
583 colsze or rowsze to nonzero values without actually allocating space.
584*/
585
602
603
604
605/*
606 lptols_struct
607
608 This structure contains phase and tolerance information for the lp algorithm.
609
610 The philosophy with respect to the separate zero and feasibility tolerances
611 for primal and dual variables is that dylp uses the zero tolerance when
612 calculating primal or dual variables, and the feasibility tolerance when
613 checking for feasibility. This allows us to keep small values for accuracy
614 in computation, but not be so fussy when it comes to feasibility.
615
616 Field Definition
617 ----- ----------
618 inf Infinity. dylp uses IEEE FP infinity, but be careful not to
619 pass it to the basis package.
620 zero Zero tolerance for primal variables, and also the generic
621 zero tolerance for constraint coefficients, right-hand-side
622 values, etc.
623 pchk Primal accuracy check tolerance.
624 pfeas Primal feasibility check tolerance; dynamically scaled from
625 zero in proportion to the 1-norm of the primal basic variables.
626 pfeas_scale Primal feasibility check tolerance multiplier. This provides
627 some user-controllable decoupling of zero and pfeas.
628 cost Base zero tolerance for checks involving objective function
629 coefficients, reduced costs, and related values.
630 dchk Dual accuracy check tolerance. Also used by dy_duenna to
631 test for improvement in the objective.
632 dfeas Dual feasbility check tolerance; dynamically scaled from cost
633 in proportion to the 1-norm of the dual variables. Acts as the
634 zero tolerance for reduced costs.
635 dfeas_scale Dual feasibility check tolerance multiplier. This provides
636 some user-controllable decoupling of cost and dfeas.
637 pivot Simplex pivot selection tolerance, expressed as a multiplier
638 for the pivot selection tolerance used by the basis package
639 when factoring the basis. (I.e., the actual pivot selection
640 criteria will be to accept a simplex pivot a<i,j> if
641 |a<i,j>| > lptols.pivot*basis.pivot*MAX{i}|a<i,j>|.)
642 bogus Multiplier used to identify 'bogus' values, in the range
643 tol < |val| < bogus*tol for the appropriate tolerance.
644 swing Ratio used to identify excessive growth in primal variables
645 (pseudo-unboundedness).
646 toobig Absolute value of primal variables which will cause dual
647 multipivoting to consider primal infeasibility when selecting
648 a flip/pivot sequence.
649 purge Percentage change in objective function required before
650 constraint or variable purging is attempted.
651 purgevar Percentage of maximum reduced cost used to determine the
652 variable purge threshold; nonbasic architectural variables
653 at their optimum bound whose reduced cost exceeds
654 purgevar*MAX{j}cbar<j> are purged.
655
656 reframe Multiplier used to trigger a reference framework reset in
657 PSE pricing; reset occurs if
658 |gamma<j> - ||abar<j>||^2| > reframe*||abar<j>||^2.
659 The check is made in pseupdate.
660 Also used to trigger recalculation of the basis inverse row
661 norms used in DSE pricing; reset occurs if
662 |rho<i> - ||beta<i>||^2| > reframe*||beta<i>||^2.
663 The check is made in dseupdate.
664*/
665
666typedef struct
667{ double inf ;
668 double zero ;
669 double pchk ;
670 double pfeas ;
671 double pfeas_scale ;
672 double cost ;
673 double dchk ;
674 double dfeas ;
675 double dfeas_scale ;
676 double pivot ;
677 double bogus ;
678 double swing ;
679 double toobig ;
680 double purge ;
681 double purgevar ;
683
684#if defined(DYLP_INTERNAL) || defined(BONSAIG)
685/*
686 A few handy macros for testing values against tolerances.
687*/
688#ifdef DYLP_INTERNAL
689# ifdef BND_TOLER
690# undef BND_TOLER
691# endif
692# define BND_TOLER dy_tols->pfeas
693# ifdef INF_TOLER
694# undef INF_TOLER
695# endif
696# define INF_TOLER dy_tols->inf
697#endif
698
699#define withintol(zz_val_zz,zz_tgt_zz,zz_tol_zz) \
700 (fabs((zz_val_zz)-(zz_tgt_zz)) <= zz_tol_zz)
701
702#define setcleanzero(zz_val_zz,zz_tol_zz) \
703 if (fabs(zz_val_zz) < zz_tol_zz) zz_val_zz = 0
704
705#define atbnd(zz_val_zz,zz_bnd_zz) \
706 ((fabs(zz_bnd_zz) < INF_TOLER) && \
707 (fabs((zz_val_zz)-(zz_bnd_zz)) < BND_TOLER*(1.0+fabs(zz_bnd_zz))))
708
709#define belowbnd(zz_val_zz,zz_bnd_zz) \
710 ((fabs(zz_bnd_zz) < INF_TOLER) ? \
711 (((zz_bnd_zz)-(zz_val_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
712 (zz_val_zz < zz_bnd_zz))
713
714#define abovebnd(zz_val_zz,zz_bnd_zz) \
715 ((fabs(zz_bnd_zz) < INF_TOLER) ? \
716 (((zz_val_zz)-(zz_bnd_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
717 (zz_val_zz > zz_bnd_zz))
718
719#define withinbnds(zz_lb_zz,zz_val_zz,zz_ub_zz) \
720 (!abovebnd(zz_val_zz,zz_ub_zz) && !belowbnd(zz_val_zz,zz_lb_zz))
721
722#endif /* DYLP_INTERNAL || BONSAIG */
723
724#ifdef DYLP_INTERNAL
725/*
726 Finally, a macro to decide if we should snap to a value. The notion here is
727 that the accuracy with which one can hit a target value depends on both the
728 magnitude of the target and the distance travelled to get there. On a
729 64-bit machine, IEEE FP has about 15 decimal digits of accuracy. For
730 example, if we're travelling 1.0e7 and trying to hit zero, we only have 8
731 decimal places of accuracy remaining. If we're within 1.0e-8, might as well
732 snap to 0. In practice, there's already a bit of roundoff in any nontrivial
733 calculation, so we start with the zero tolerance and scale from there.
734
735 In some cases, we only know the target, so the best we can do is
736 scale to it.
737
738 The utility of this idea is highly questionable.
739*/
740
741#define snaptol1(zz_tgt_zz) (dy_tols->zero*(1.0+(zz_tgt_zz)))
742
743#define snaptol2(zz_tgt_zz,zz_dst_zz) \
744 (dy_tols->zero*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
745
746#define snaptol3(zz_tol_zz,zz_tgt_zz,zz_dst_zz) \
747 ((zz_tol_zz)*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
748
749#endif /* DYLP_INTERNAL */
750
751
752
753/*
754 Enum for initial basis type.
755
756 This determines the criteria used to select the initial set of basic
757 variables during a cold start.
758
759 ibINV invalid
760 ibLOGICAL Use only logical (slack and artificial) variables
761 ibSLACK Use slack variables for inequalities. Prefer architectural
762 over artificial variables for equalities.
763 ibARCH Prefer architectural variables over logical variables.
764*/
765
766typedef enum { ibINV = 0, ibLOGICAL, ibSLACK, ibARCH } ibtype_enum ;
767
768/*
769 Enum for calling context.
770
771 As dylp evolves, it has proven useful to know the context of the
772 call. Consider this a work in progress. The default context is INITIALLP.
773
774 cxINV invalid (context is unknown)
775 cxLOAD This call is only to (re)load data structures. Returns after
776 one iteration of dual or primal simplex, but shows problem
777 status rather than lpITERLIM.
778 cxUNLOAD This call is solely for the purpose of freeing the problem
779 data structures. (Replaces dyDONE/lpctlONLYFREE hack.)
780 cxSINGLELP This is a one-off call to solve a single LP from scratch.
781 cxINITIALLP This is a call to solve a single LP from scratch, but will
782 likely be followed by calls to reoptimise.
783 cxBANDC This call is made in the context of a branch-and-cut
784 algorithm.
785 cxUSERPIV This call is in the context of user control of pivoting.
786*/
787
788typedef enum { cxINV = 0, cxLOAD, cxUNLOAD,
790
791
792/*
793 lpopts_struct
794
795 This structure is used to pass option settings to dylp. Default values are
796 declared at the beginning of dy_setup.c.
797
798 Field Definition
799 ----- ----------
800 context The context in which dylp is being called. See comments
801 above for cxtype_enum.
802 forcecold TRUE to force a cold start, FALSE otherwise. If set to TRUE,
803 dominates warm and hot start.
804 forcewarm TRUE to force a warm start, FALSE otherwise. If set to TRUE,
805 dominates hot start.
806 fullsys Forces the use of the full constraint system at all times. The
807 full constraint system is loaded on startup, and all constraint
808 and variable deactivation/activation is skipped. (But see the
809 finpurge option below.) (Also, this will not prevent dylp
810 from resorting to forced phase transitions, which typically
811 involve deactivation of constraints or variables. Arguably
812 this is a bad thing, and may change in the future.)
813 active Used to estimate the initial size of the dylp constraint
814 system relative to the original system.
815 vars Fraction of original variables expected to be active at
816 any time.
817 cons Fraction of original inequalities expected to be active at
818 any time.
819 initcons Specifies how inequalities will be selected to initialize the
820 active system. See extensive comments in dy_coldstart.c.
821 frac Fraction of inequalities to be used.
822 i1l Lower bound on angle to objective, first interval
823 i1lopen TRUE if the bound is open.
824 i1u Upper bound on angle to objective, first interval
825 i1uopen TRUE if the bound is open.
826 i2valid TRUE if the second interval is specified
827 i2l Lower bound on angle to objective, second interval
828 i2lopen TRUE if the bound is open.
829 i2u Upper bound on angle to objective, second interval
830 i2uopen TRUE if the bound is open.
831 coldbasis Code specifying the kind of basis built for a cold start. See
832 comments for ibtype_enum and comments in dy_coldstart.c
833 finpurge Controls whether dylp does a final deactivation of constraints
834 and/or variables. This will occur only an optimal solution is
835 found, and is not suppressed by fullsys.
836 cons TRUE to purge constraints
837 vars TRUE to purge variables
838 heroics Controls behaviour during forced primal <-> dual transitions
839 d2p TRUE to allow deactivation of basic architecturals, FALSE
840 to disallow. FALSE is recommended, and the default.
841 p2d TRUE to allow deactivation of tight constraints, FALSE
842 to disallow. FALSE is recommended, and the default.
843 flip TRUE to allow flips to regain dual feasibility, FALSE to
844 disallow. Tends to cycle; default is false.
845 coldvars If the number of active variables exceeds this value after
846 a cold start, dylp will attempt to purge variables prior to
847 the initial primal simplex run.
848 con Options related to constraint activation/deactivation
849 actlvl The constraint activation strategy
850 0: (strict) activate violated constraints,
851 lhs < rhslow or lhs > rhs
852 1: (tight) activate tight or violated constraints,
853 lhs <= rhslow or lhs >= rhs
854 actlim If non-zero, limits the number of constraints that can be
855 activated in any one call to a constraint activation
856 routine.
857 deactlvl The constraint deactivation strategy:
858 0: (normal) deactivate only inequalities i which are
859 strictly loose (i.e., slk<i> basic, not at bound).
860 1: (aggressive) normal plus inequalities which are tight
861 with y<i> = 0.
862 2: (fanatic) aggressive plus equalities with y<i> = 0
863 usedual TRUE if dual phase II is to be used to regain feasibility after
864 adding constraints, FALSE to force use of primal phase I.
865 addvar If non-zero, at most this many variables will be added in
866 any one pass through phase dyADDVAR.
867 dualadd Controls the types of activation allowed when adding variables
868 during dual simplex.
869 0: variable activation is disallowed
870 1: type 1 activation (variables that will be dual feasible
871 when activated into the nonbasic partition)
872 2: type 2 activation (variables which can be activated
873 if immediately pivoted into the basis)
874 3: type 3 activation (activate with bound-to-bound pivot)
875 See dy_dualaddvars for more extensive comments.
876 scan Partial pricing parameter. Controls the number of columns to
877 be scanned for a new candidate entering variable when the
878 candidate selected during PSE update is rejected.
879 iterlim The per phase pivot limit for the code; if set to 0, no
880 limit is enforced.
881 idlelim The number of iterations without change in the objective
882 function before the code declares the problem is stalled or
883 cycling.
884 dpsel Options to control dual pivoting. Selection of the leaving
885 variable is always handled by DSE.
886 strat: The strategy used to select the entering variable:
887 0: standard ratio test; may use anti-degen lite
888 1: multipivoting, selecting for maximum dual objective
889 improvement.
890 2: multipivoting, select for minimum predicted
891 infeasibility.
892 3: multipivoting, select infeasibility reduction if
893 possible, otherwise maximum dual objective improvement.
894 flex If TRUE, dylp will switch between strategies 1 and 3, using
895 strategy 1 unless primal magnitudes become too large.
896 allownopiv If TRUE, sequences of flips with no finishing pivot will be
897 allowed. Defaults to false, very prone to cycling.
898 ppsel Options to control primal pivoting. Selection of the entering
899 variable is always handled by PSE.
900 strat: The strategy used to select the leaving variable:
901 0: standard ratio test; may use anti-degen lite
902 1: multipivoting
903 factor The LP basis will be refactored every factor iterations, in
904 the absence of some compelling reason (typically error
905 recovery) that forces it to occur sooner.
906 check An accuracy check will be forced every check iterations, in
907 the absence of some compelling reason to do it earlier.
908 groom Controls the action taken by the basis grooming routine
909 when it makes a nontrivial status correction:
910 0: catatonic
911 1: issue a warning
912 2: issue an error message and force an abort
913 Numeric codes should match keywords in dy_options.c:dy_ctlopt.
914 degen TRUE to allow creation of restricted subproblems to deal with
915 degeneracy, FALSE to disallow it.
916 degenpivlim The number of successive degenerate pivots required before
917 creating a restricted subproblem.
918 degenlite Controls secondary antidegeneracy --- `antidegen lite'
919 0: (pivotabort) break ties using |abar<kj>| and abort when
920 delta<j> = 0
921 1: (pivot) break ties using |abar<kj>| but always scan the
922 full basis
923 2: (alignobj) break ties by examining the alignment of the
924 hyperplane which will become tight on the pivot; choose
925 so that movement in the direction of the objective most
926 nearly lies in the hyperplane
927 3: (alignedge) break ties by examining the alignment of the
928 hyperplane which will become tight on the pivot; choose
929 so that the direction of motion defined by the entering
930 variable most nearly lies in the hyperplane.
931 4: (perpobj) break ties by examining the alignment of the
932 hyperplane which will become tight on the pivot; choose
933 so that the normal of the hyperplane is most nearly
934 aligned with the normal of the objective
935 5: (perpedge) break ties by examining the alignment of the
936 hyperplane which will become tight on the pivot; choose
937 so that the normal of the hyperplane is most nearly
938 aligned with the direction of motion
939 Numeric codes should match keywords in dy_options.c:dy_ctlopt.
940 patch TRUE to allow the code to patch a singular basis, FALSE to
941 prevent patching.
942 copyorigsys Controls whether dylp makes a local copy of the original
943 system. If set to TRUE, dylp will always make a local copy.
944 If set to FALSE, a copy will be made only if necessary.
945 Scaling will trigger a local copy.
946 scaling Controls whether dylp attempts to scale the original constraint
947 system for numeric stability.
948 0: scaling is forbidden
949 1: scale the original constraint system using numeric
950 scaling vectors attached to the system
951 2: evaluate the original constraint system and scale it if
952 necessary
953 Note that even if scaling = 0, dylp may install +/-1.0 scaling
954 vectors in order to flip >= constraints to <= constraints. See
955 comments in dy_scaling.c
956 print Substructure for picky printing control. For all print options,
957 a value of 0 suppresses all information messages.
958 major Controls printing of major phase information.
959 1: a message at each phase transition.
960 scaling Controls print level during initial evaluation and scaling of
961 the original constraint system.
962 1: start and finish messages
963 2: stability measures for original and scaled matrices;
964 adjustments to tolerances.
965 setup Controls print level while creating the initial constraint
966 system for dylp.
967 1: start and finish messages.
968 2: summary information about activated constraints
969 3: messages about each constraint included in the initial
970 system.
971 4: messages about each constraint processed for the initial
972 system
973 5: messages about each variable included in the initial
974 system.
975 6: lists value and status of inactive variables with
976 nonzero values
977 crash Controls print level while crashing the basis.
978 1: start & finish messages
979 2: summary counts for logicals, architecturals, artificials
980 3: a dump of the completed basis
981 4: detailed info on the selection of each architectural
982 and artificial variable
983 pricing Controls print level for pricing of columns (rows) in primal
984 (dual) simplex.
985 1: summary messages
986 2: lists candidate list and primal variable selected for
987 entry (exit) at each pivot
988 3: lists each variable as it's added to the candidate list
989 and again when reconsidered for pivoting
990 pivoting Controls print level for selection of the leaving (entering)
991 primal variable in primal (dual) simplex and updating of
992 variables.
993 1: prints result of leaving (entering) variable selection
994 2: information about the selection of the leaving (entering)
995 variable.
996 3: more information about the selection of the leaving
997 (entering) variable.
998 4: prints the pivot column (row) before and after
999 multiplication by the basis inverse, and yet more
1000 pivot selection information.
1001 5: prints a line for every candidate evaluated
1002 pivreject Controls print level for information related to the operation
1003 of the pivot rejection mechanism.
1004 1: Prints a message for each row/column added to the pivot
1005 rejection list, plus other major events.
1006 2: Prints a message for each row/column removed from the
1007 pivot rejection list.
1008 degen Controls print level for information related to the operation
1009 of the antidegeneracy mechanism.
1010 1: prints a message each time the antidegeneracy level
1011 changes
1012 2: prints a message when a true degenerate pivot is taken
1013 under duress
1014 3: prints a message when a degenerate pivot is taken
1015 4: prints anomalies as each degenerate set is formed and
1016 backed out
1017 5: prints details of each degenerate set as it's formed and
1018 backed out
1019 phase1 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: summary information about infeasible variables and phase
1026 I objective coefficients; information about primal
1027 variables updated at each pivot.
1028 6: prints the primal variables after each pivot; prints
1029 infeasible variables during phase I objective construction
1030 7: prints the dual variables after each pivot; prints
1031 infeasible variables during phase I objective modification
1032 phase2 Controls general print level for phase 1 of primal simplex.
1033 1: messages about extraordinary events -- problem pivots, etc.
1034 2: messages about 'routine' but infrequent events --
1035 termination conditions, refactoring, unboundedness, etc.
1036 3: messages with additional details of problems encountered
1037 4: a one line log message is printed for each pivot
1038 5: prints the updated basic primal variables after each pivot
1039 6: prints all basic primal variables after each pivot
1040 7: prints the dual variables after each pivot.
1041 dual Controls general print level for the dual simplex. As
1042 phase2.
1043 basis Controls print level in routines working with the basis.
1044 1: summary warnings about problems: empty rows, singularity,
1045 numerical instability, etc.
1046 2: information about factoring failures and recovery actions
1047 3: warnings about individual empty rows, details of column
1048 replacement when patching a singular basis, pivot
1049 tolerance adjustments; information about pivoting failures
1050 and recovery actions
1051 4: basis stability after factoring
1052 5: basis stability after pivoting
1053 conmgmt Controls print level while dylp is in the purge/generate/
1054 activate constraint phases.
1055 1: prints the number of constraints purged, generated,
1056 & activated, and new size of constraint system.
1057 2: prints a message for each constraint purged or activated.
1058 (The cut generation routine is responsible for
1059 handling this function when it generates cuts.)
1060 3: additional details about refactoring and new values
1061 of primal and dual variables.
1062 4: prints a message about any variables affected as a side
1063 effect of constraint changes, constraints processed
1064 but not activated, and information about direction of
1065 recession and relative angle of constraints when adding
1066 constraints to an unbounded problem.
1067 5: prints a running commentary on constraint and variable
1068 shifts, inactive variables.
1069 varmgmt Controls print level while dylp is in the purge/generate/
1070 activate variable phases.
1071 1: prints the number of variables purged, generated,
1072 & activated, and new size of constraint system.
1073 2: prints a message for each variable purged & activated.
1074 (The column generation routine is responsible for
1075 handling this function when it generates new variables).
1076 3: prints a message about any constraints affected as a side
1077 effect of variable changes, variables processed but not
1078 activated, and information about direction of recession
1079 and relative angle of dual constraints when adding
1080 variables to an unbounded dual.
1081 4: prints a running commentary on constraint and variable
1082 shifts.
1083 force Controls print level when dylp is attempting to force a
1084 transition (primal -> dual, dual -> primal) or force the
1085 use of the full constraint system.
1086 1: prints a summary message giving the result of the
1087 transition attempt
1088 2: prints messages about actions taken for individual
1089 constraints and variables.
1090 3: additional information about variables and constraints
1091 examined.
1092 tableau Controls print level for routines that generate tableau
1093 vectors (beta<i>, beta<j>, abar<i>, abar<j>) for use by
1094 external clients.
1095 1: prints summary messages about the circumstances
1096 4: prints nonzeros in the final vector.
1097 5: prints nonzeros in intermediate vectors and (dy_betaj,
1098 dy_abarj only) inactive rows
1099 6: prints nonzeros of active portion in internal reference
1100 frame (dy_betaj only)
1101 rays Controls print level for routines that generate primal
1102 and dual rays for use by external clients.
1103 1: prints summary messages about vectors found.
1104 3: print information about columns / rows examined.
1105 4: print information about why a column or row was rejected.
1106 5: print nonzeros for each ray
1107 soln Controls print level for routines that generate primal and
1108 dual solutions for use by external clients.
1109 1: prints summary messages about the circumstances
1110 3: prints nonzeros in the final vector
1111 4: prints nonzeros in intermediate vectors
1112*/
1113
1114typedef struct
1116 int scan ;
1119 struct { int strat ;
1120 bool flex ;
1121 bool allownopiv ; } dpsel ;
1122 struct { int strat ; } ppsel ;
1124 int check ;
1125 int groom ;
1126 struct { int actlvl ;
1128 int deactlvl ; } con ;
1134 bool usedual ;
1135 bool degen ;
1138 bool patch ;
1139 bool fullsys ;
1142 struct { float vars ;
1143 float cons ; } active ;
1144 struct { double frac ;
1145 bool i1lopen ;
1146 double i1l ;
1147 bool i1uopen ;
1148 double i1u ;
1149 bool i2valid ;
1150 bool i2lopen ;
1151 double i2l ;
1152 bool i2uopen ;
1153 double i2u ; } initcons ;
1155 struct { bool cons ;
1156 bool vars ; } finpurge ;
1157 struct { bool d2p ;
1158 bool p2d ;
1159 bool flips ; } heroics ;
1160 struct { int major ;
1161 int scaling ;
1162 int setup ;
1163 int crash ;
1167 int degen ;
1170 int dual ;
1171 int basis ;
1174 int force ;
1176 int rays ;
1177 int soln ; } print ; } lpopts_struct ;
1178
1179
1180
1181
1182 /*
1183 Statistics structure, used to collect information about aspects of dylp
1184 operation beyond simple pivot counts. The data structure definition is
1185 always present, but to fill it you have to define DYLP_STATISTICS.
1186
1187 Field Definition
1188 ----- ----------
1189 phasecnts[dyDONE] Array with counts for number of times each phase is
1190 executed.
1191 ini_simplex The initial simplex phase
1192 cons A set of arrays with data about individual constraints.
1193 sze Allocated capacity of the arrays.
1194 angle Angle to the objective function.
1195 actcnt Number of times constraint is activated.
1196 deactcnt Number of times constraint is deactivated.
1197 init True if constraint is active in initial system.
1198 fin True if constraint is active in final system.
1199 vars A set of arrays with data about individual variables.
1200 sze Allocated capacity of the arrays.
1201 actcnt Number of times variable is activated.
1202 deactcnt Number of times variable is deactivated.
1203 angle
1204 max Maximum angle to the objective function over all constraints.
1205 min Minimum angle to the objective function over all constraints.
1206 hist[*] Histogram of angles of constraints to the objective function.
1207 There are DYSTATS_HISTBINS bins. Currently, 37 bins: 36 bins
1208 spanning 5 degrees of angle, and a dedicated 90 degree bin.
1209
1210 factor Tracks how well we're doing with respect to refactoring the
1211 basis.
1212 cnt Number of time the basis has been refactored.
1213 prevpiv Pivot count at last refactorisation.
1214 avgpivs Average number of pivots between basis refactorisations.
1215 maxpivs Maximum number of pivots between basis refactorisations.
1216
1217 pivrej Statistics about the pivot rejection list and punts.
1218 max maximum number of entries on the pivot rejection list
1219 mad total number of entries attributed to mad pivots
1220 sing total number of entries attributed to singular pivots
1221 pivtol_red total number of times the pivot tolerance was reduced
1222 min_pivtol the minimum pivot tolerance used
1223 puntcall total number of calls to dealWithPunt
1224 puntret total number of dyrPUNT returns recommended
1225
1226 dmulti Tracks the dual multipivot algorithm. All fields except cnt are
1227 totals; divide by cnt to get averages.
1228 flippable Number of flippable variables in the constraint system.
1229 cnt Total calls to dualmultiin
1230 cands Number of candidates queued for evaluation for entry
1231 promote Number of calls that resulted in promoting a sane pivot
1232 over an unstable pivot.
1233 nontrivial Number of times that the initial scan and sort left
1234 multiple candidates for further evaluation.
1235 evals Actual number of candidates evaluated (ftran'd column)
1236 flips Number of bound-to-bound flips performed
1237 pivrnk Index in the list of candidates of the candidate finally
1238 selected for pivoting.
1239 maxrnk Maximum index selected for pivoting.
1240
1241 pmulti Tracks the primal multipivot algorithm.
1242 cnt Total calls to primalmultiin
1243 cands Number of candidates queued for evaluation to leave
1244 nontrivial Number of times that the candidate list was sorted
1245 promote Number of calls that resulted in promoting a sane pivot
1246 over an unstable pivot.
1247
1248 infeas Statistics on resolution of infeasibility in primal phase I.
1249 Basically, what we're interested in tracking is the number
1250 of infeasible variables and the number of pivots between a
1251 change in the number of infeasible variables. We're interested
1252 in separating the case of 1 variable from 2 or more, because
1253 the latter requires vastly more calculation. A little care
1254 is required because phase I can run many times.
1255
1256 prevpiv The pivot count (tot.iters) at the previous change.
1257 maxcnt The maximum number of infeasible variables encountered (this
1258 is not strictly monotonic, as dylp may enter phase I many
1259 times due to activating violated constraints).
1260 totpivs The total number of pivots expended in phase I.
1261 maxpivs The maximum number of pivots with no change in the number of
1262 feasible variables.
1263 chgcnt1 The number of times that the number of infeasible variables
1264 changed and reduced costs did not have to be recalculated
1265 (specifically, exactly one variable became feasible, and it
1266 left the basis as it did so).
1267 chgcnt2 The number of times that the number of infeasible variables
1268 changed in such a way as to require recalculation of the
1269 reduced costs.
1270
1271 [dp]degen[*] Array of stats for each restricted subproblem nesting level,
1272 with separate arrays for dual (ddegen) and primal (pdegen).
1273 degen[0].cnt is used to hold the maximum nesting level.
1274 cnt Number of times this nesting level was entered.
1275 avgsiz The average number of variables in a restricted subproblem.
1276 Kept by iterative update, as avg<k+1> = (avg<k>*k+size)/(k+1).
1277 Suffers from cumulative loss of accuracy, but it'll do for
1278 our purposes.
1279 maxsiz The maximum number of variables in a restricted subproblem.
1280 totpivs Total number of pivots at or above this nesting level.
1281 avgpivs Average number of pivots at or above this nesting level.
1282 maxpivs Maximum number of pivots for any one instance at or above
1283 this nesting level.
1284
1285 tot, p1, p2, d2 Iteration and pivot counts, total and for each
1286 individual phase. These are copied over from
1287 dy_lp (lp_struct) at the end of the run, so that
1288 they can be printed by dumpstats.
1289
1290 DYSTATS_MAXDEGEN is the maximum number of levels of nesting accommodated by
1291 antidegeneracy statistics and debugging structures. The actual algorithm
1292 has no inherent limitation.
1293
1294 DYSTATS_HISTBINS is the number of bins for constraint angles. It should be an
1295 odd number. Each bin will span 180/(DYSTATS_HISTBINS-1) degrees, with the
1296 final bin reserved for constraints at 90 degrees. For example, a value of 37
1297 gives 180/(37-1) = 5 degrees per bin.
1298 */
1299
1300 #define DYSTATS_MAXDEGEN 25
1301 #define DYSTATS_HISTBINS 37
1302
1303 typedef struct {
1304 int phasecnts[dyDONE+1] ;
1306 struct { int sze ;
1307 double *angle ;
1308 int *actcnt ;
1310 bool *init ;
1311 bool *fin ; } cons ;
1312 struct { int sze ;
1313 int *actcnt ;
1314 int *deactcnt ; } vars ;
1315 struct { float max ;
1316 float min ;
1317 int hist[DYSTATS_HISTBINS] ; } angle ;
1318 struct { int cnt ;
1320 float avgpivs ;
1321 int maxpivs ; } factor ;
1322 struct { int max ;
1323 int mad ;
1324 int sing ;
1326 double min_pivtol ;
1328 int puntret ; } pivrej ;
1329 struct { int flippable ;
1330 int cnt ;
1331 int cands ;
1334 int evals ;
1335 int flips ;
1337 int maxrnk ; } dmulti ;
1338 struct { int cnt ;
1339 int cands ;
1340 int nontrivial ;
1341 int promote ; } pmulti ;
1342 struct { int prevpiv ;
1345 int maxpivs ;
1347 int chgcnt2 ; } infeas ;
1348 struct { int cnt ;
1349 float avgsiz ;
1351 int totpivs ;
1352 float avgpivs ;
1353 int maxpivs ; } pdegen[DYSTATS_MAXDEGEN] ;
1354 struct { int cnt ;
1355 float avgsiz ;
1356 int maxsiz ;
1357 int totpivs ;
1358 float avgpivs ;
1359 int maxpivs ; } ddegen[DYSTATS_MAXDEGEN] ;
1360 struct { int iters ;
1361 int pivs ; } tot ;
1362 struct { int iters ;
1363 int pivs ; } p1 ;
1364 struct { int iters ;
1365 int pivs ; } p2 ;
1366 struct { int iters ;
1367 int pivs ; } d2 ; } lpstats_struct ;
1368
1369
1370
1371#ifdef DYLP_INTERNAL
1372
1373/*
1374 Macros to determine whether a constraint or variable is active, and whether
1375 it's eligible for activation. Coding is explained below for dy_origcons and
1376 dy_origvars. The main purpose served by these macros is to make it easy to
1377 find activiation/deactivation points in the code, should the conventions ever
1378 change.
1379*/
1380
1381#define ACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] > 0)
1382#define INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] <= 0)
1383#define LOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] == 0)
1384#define MARK_UNLOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = -1)
1385#define MARK_INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = 0)
1386
1387#define ACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] > 0)
1388#define INACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] <= 0)
1389#define LOADABLE_VAR(zz_vndx_zz) \
1390 ((dy_origvars[(zz_vndx_zz)] < 0) && \
1391 flgoff(((flags) -dy_origvars[(zz_vndx_zz)]),vstatNOLOAD|vstatNBFX))
1392#define MARK_INACTIVE_VAR(zz_vndx_zz,zz_val_zz) \
1393 (dy_origvars[(zz_vndx_zz)] = (zz_val_zz))
1394
1395
1396/*
1397 dy_logchn i/o id for the execution log file
1398 dy_gtxecho controls echoing of generated text to stdout
1399*/
1400
1401extern ioid dy_logchn ;
1402extern bool dy_gtxecho ;
1403
1404
1405/*
1406 lp_struct
1407
1408 This structure is the control structure for an LP problem within dylp.
1409
1410 Field Definition
1411 ----- ----------
1412 phase Current phase of the dynamic simplex algorithm.
1413 lpret Return code from the most recent simplex execution.
1414
1415 z Value of the objective function (includes inactzcorr).
1416 inactzcorr Correction to the objective function due to inactive variables
1417 with non-zero values.
1418
1419 simplex Simplex algorithm status and control
1420 active currently active or most recently completed
1421 next currently active or to be started
1422 init_pse TRUE if the PSE structures need to be reinitialised,
1423 FALSE otherwise
1424 init_dse TRUE if the DSE structures need to be reinitialised,
1425 FALSE otherwise
1426 These fields are used to determine when to update or
1427 reinitialise the PSE and DSE data structures. Active and next
1428 must be valid during the purge/gen/add variable/constraint
1429 cycles.
1430
1431 A word on infeas and infeascnt: They are guaranteed accurate
1432 only immediately after initialisation and following a primal
1433 feasibility check.
1434
1435 infeas Total infeasibility = SUM{j} max(0,x<j>-ub<j>,lb<j>-x<j>)
1436 infeascnt The number of infeasible variables; refreshed when dy_accchk
1437 is asked to do a primal feasibility check.
1438
1439 ubnd Substructure for information on unbounded or pseudo-unbounded
1440 problems.
1441 ndx The index of the variable fingered for causing unboundedness
1442 or pseudo-unboundedness (swing).
1443 ratio The growth ratio.
1444
1445 p1obj The following fields relate to handling of the phase I
1446 objective function.
1447 installed TRUE if the phase I objective is currently installed
1448 infcnt Tracks the number of variables incorporated in p1obj which
1449 remain infeasible.
1450 infvars_sze Allocated size of the infvars vector.
1451 infvars Vector of indices of infeasible variables incorporated in the
1452 phase I objective.
1453 p1obj Pointer to the phase I objective (temporary storage while
1454 the phase II objective is installed).
1455 p2obj Pointer to the phase II objective (temporary storage while
1456 the phase I objective is installed).
1457
1458 A word on pivot and iteration counts: Iteration counts tally
1459 iterations of the pivoting loop, successful or not. Pivot
1460 counts tally successful bound-to-bound or change-of-basis
1461 pivots. Pretty much all messages will give tot.iters, so that
1462 it's possible to track the progress of an LP. Iterf has an
1463 entirely different function -- it's tracking the accumulation
1464 of eta matrices in the basis representation.
1465
1466 sys Substructure for dynamic system modification status.
1467 forcedfull Set to TRUE if the full system has been forced in state
1468 dyFORCEFULL. This should happen at most once, so if we
1469 enter dyFORCEFULL and forcedfull == TRUE, it's fatal.
1470 cons
1471 loadable Count of constraints which could be activated
1472 unloadable Count of constraints which are ineligible for activation
1473 (empty constraints and nonbinding rows)
1474 vars
1475 loadable Count of variables which could be activated
1476 unloadable Count of variables which are ineligible for activation
1477 (nonbasic fixed)
1478
1479 tot Total simplex iterations and pivots, all phases
1480 iters
1481 pivs
1482 p1 Primal phase I iterations and pivots.
1483 iters
1484 pivs
1485 p2 Primal phase II iterations and pivots.
1486 iters
1487 pivs
1488 d2 Dual phase II iterations and pivots.
1489 iters
1490 pivs
1491
1492 pivok Set to TRUE in dy_{primal|dual}pivot if the current iteration
1493 is a successful pivot. Cleared to FALSE at the head of
1494 dy_duenna.
1495 prev_pivok Set to pivok at head of dy_duenna. Provides status of just
1496 completed pivot for post-Duenna decisions.
1497
1498 basis Various fields related to basis change, refactoring, etc.
1499
1500 etas The number of basis changes (hence eta matrices) since the
1501 the basis was last factored. Used to schedule periodic
1502 factoring of the basis. Reset to 0 each time the basis is
1503 factored.
1504 pivs The number of basis pivots since entry into a primal or dual
1505 simplex phase (excludes bound-to-bound simplex `pivots').
1506 Used when deciding whether to remove variables from the pivot
1507 reject list, and whether to pop out of a simplex phase due to
1508 excessive swing.
1509 dinf Number of successive refactors with dual infeasibility.
1510 Cleared at the start of a simplex phase.
1511 Incremented/cleared in dy_accchk iff a dual feasibility check
1512 is performed.
1513
1514 degen Activation level of antidegeneracy algorithm. Held at 0 when
1515 the antidegeneracy algorithm is not active. Incremented each
1516 time a restricted subproblem is formed, and decremented when
1517 the restriction is backed out. (Values > 1 indicate that
1518 degeneracy recurred while working on a restricted subproblem,
1519 resulting in further restriction.)
1520 degenpivcnt The number of successive degenerate pivots.
1521
1522 idlecnt The number of cycles since the objective has changed.
1523
1524 lastz Previous objective value for various activities; used to
1525 detect and suppress loops.
1526 piv Objective at last pivot (detects stalling)
1527 cd Objective at last entry into constraint deactivation
1528 (dyPURGECON) (detects constraint activate/deactivate loops)
1529 vd Objective at last entry into variable deactivation
1530 (dyPURGEVAR) (detects variable activate/deactivate loops)
1531 fp Objective at last entry into force primal (dyFORCEPRIMAL)
1532 (detects constraint activate/deactivate loops)
1533 fd Objective at last entry into force dual (dyFORCEDUAL)
1534 (detects variable activate/deactivate loops)
1535
1536 prim Primal variable information
1537 norm1 1-norm of basic primal variables inv(B)b
1538 norm2 2-norm of basic primal variables
1539 max inf-norm (max) of basic primal variables
1540 maxndx index of max primal variable
1541
1542 dual Dual variable information
1543 norm1 1-norm of dual variables c<B>inv(B)
1544 norm2 2-norm of dual variables
1545 max inf-norm (max) of dual variables
1546 maxndx index of max dual variable
1547
1548*/
1549
1550typedef struct
1553 double z ;
1554 double inactzcorr ;
1558 bool init_dse ; } simplex ;
1559 double infeas ;
1561 struct { int ndx ;
1562 double ratio ; } ubnd ;
1563 struct { bool installed ;
1566 int *infvars ;
1567 double *p1obj ;
1568 double *p2obj ; } p1obj ;
1569 struct { struct { int loadable ;
1570 int unloadable ; } cons ;
1571 struct { int loadable ;
1572 int unloadable ; } vars ;
1573 bool forcedfull ; } sys ;
1574 struct { int iters ;
1575 int pivs ; } tot ;
1576 struct { int iters ;
1577 int pivs ; } p1 ;
1578 struct { int iters ;
1579 int pivs ; } p2 ;
1580 struct { int iters ;
1581 int pivs ; } d2 ;
1582 bool pivok ;
1584 struct { int etas ;
1585 int pivs ;
1586 int dinf ; } basis ;
1587 int degen ;
1590 struct { double piv ;
1591 double cd ;
1592 double vd ;
1593 double fp ;
1594 double fd ; } lastz ;
1595 struct { double norm1 ;
1596 double norm2 ;
1597 double max ;
1598 int maxndx ; } prim ;
1599 struct { double norm1 ;
1600 double norm2 ;
1601 double max ;
1602 int maxndx ; } dual ;
1603 } lp_struct ;
1604
1605
1606/*
1607 Declarations global to the dylp implementation but not visible outside of
1608 it. With this we can avoid passing huge numbers of parameters and/or
1609 unpacking a structure on a regular basis. Unless otherwise indicated, indices
1610 are in the dy_sys (active system) frame of reference.
1611
1612 dy_owner Null if there's no active problem. Contains the ID of the
1613 current owner if there's an active problem. Passed in as
1614 part of the lpprob_struct.
1615
1616 Main structures
1617 ---------------
1618 dy_lp: The lp control structure for dylp.
1619 dy_sys: The active constraint system; initialised in dylp:startup
1620 dy_tols: Tolerances in effect for dylp; initialised in
1621 dylp:dylp from orig_tols.
1622 dy_opts: Options in effect for dylp; initialised in
1623 dylp:dylp to point to same structure as orig_opts.
1624 dy_stats Statistics structure for dylp; initialised in dylp:dylp to
1625 point ot the same structure as orig_stats.
1626
1627 Constraint & Variable Management
1628 --------------------------------
1629 dy_actvars: The active variables. Indexed in dy_sys frame, contains
1630 indices in orig_sys frame. Attached to dy_sys.
1631 Entries for logical variables (1 <= j <= concnt) are
1632 meaningless.
1633 dy_actcons: The active constraints. Indexed in dy_sys frame, contains
1634 indices in orig_sys frame. Attached to dy_sys.
1635 dy_origvars: Status of the original architectural variables.
1636 * A value of 0 indicates the entry hasn't been processed.
1637 Should never happen.
1638 * If the variable is active, the entry contains the index
1639 of the variable in the dy_sys frame.
1640 * If the variable is inactive, the coding is the negative of
1641 the vstat flags, limited to the nonbasic status values
1642 vstatNBFR, vstatNBFX, vstatNBLB, or vstatNBUB, and the
1643 qualifier vstatNOLOAD.
1644 Indexed in orig_sys frame. Attached to orig_sys.
1645 dy_origcons: Status of the original constraints.
1646 * If the constraint is active, the entry contains the index
1647 of the constraint in the dy_sys frame.
1648 * If the constraint is inactive, contains 0.
1649 * If the constraint cannot be activated, contains a negative
1650 value.
1651 Indexed in orig_sys frame. Attached to orig_sys.
1652
1653 Note that there are macros defined to test whether a variable or constraint
1654 is inactive, and whether it's eligible for activation. Use them!
1655
1656 Basis Management
1657 ----------------
1658 dy_basis: The basis vector. Indexed by basis position, attached to
1659 dy_sys.
1660 dy_var2basis: Translates a variable index to a basis pos'n. Indexed by
1661 column, attached to dy_sys. Entries for nonbasic variables
1662 must be kept at 0.
1663 dy_status: The status vector. Indexed by column, attached to dy_sys.
1664
1665 Primal and Dual Variables
1666 -------------------------
1667 dy_x: The values of all primal variables. Indexed by column,
1668 attached to dy_sys. Values of nonbasic variables must always
1669 be correct (to allow uniform handling of normal nonbasic
1670 variables and superbasic variables). Values of basic
1671 variables will retain unperturbed values while the
1672 antidegeneracy mechanism is active -- this allows the
1673 perturbation to be quickly backed out.
1674 dy_xbasic: The values of the basic variables. Indexed by basis pos'n,
1675 attached to dy_sys.
1676 dy_y: The dual variables. Indexed by basis pos'n, attached to
1677 dy_sys.
1678
1679 Projected Steepest Edge (PSE) Pricing
1680 -------------------------------------
1681 dy_cbar: Iteratively updated vector of reduced costs. Indexed by column,
1682 attached to dy_sys.
1683 dy_gamma: Iteratively updated vector of column norms ||abar<j>||^2.
1684 Indexed by column, attached to dy_sys.
1685 dy_frame: Boolean vector which indicates if a given variable is in the
1686 current frame of reference. Indexed by column, attached to
1687 dy_sys.
1688
1689 Dual Steepest Edge (DSE) Pricing
1690 --------------------------------
1691 dy_rho: Iteratively updated vector of row norms ||beta<i>||^2.
1692 Indexed by basis position, attached to dy_sys.
1693
1694 DSE pricing also makes use of dy_xbasic (the reduced costs of the dual
1695 variables), and maintains dy_cbar.
1696
1697 Antidegeneracy
1698 --------------
1699 dy_brkout: Specifies the direction a variable needs to move to escape
1700 from a degenerate vertex. Indexed by basis pos'n, attached
1701 to dy_sys.
1702 dy_degenset: Specifies the set of constraints (equivalently, basic
1703 variables) perturbed at each level of the antidegeneracy
1704 algorithm. Indexed by basis pos'n, attached to dy_sys. The
1705 entry for a constraint is the highest level of degenerate set
1706 which includes the constraint. If the entry is 0, the
1707 constraint is not involved in degeneracy.
1708 dy_ddegenset: Specifies the set of dual constraints (equivalently, reduced
1709 costs) perturbed at each level of the antidegeneracy
1710 algorithm. Indexed by variable index, attached to dy_sys.
1711 The entry for a dual constraint is the highest level of
1712 degenerate set which includes the constraint. If the entry is
1713 0, the constraint is not involved in degeneracy.
1714*/
1715
1716extern void *dy_owner ;
1717
1718extern lp_struct *dy_lp ;
1719extern consys_struct *dy_sys ;
1720extern lptols_struct *dy_tols ;
1721extern lpopts_struct *dy_opts ;
1725extern flags *dy_status ;
1727extern bool *dy_frame ;
1728
1729extern lpstats_struct *dy_stats ;
1730
1731/*
1732 dy_scaling.c
1733*/
1734
1735extern bool dy_initlclsystem(lpprob_struct *orig_lp, bool hotstart) ;
1736extern void dy_freelclsystem(lpprob_struct *orig_lp, bool freesys) ;
1737extern bool dy_isscaled(void) ;
1738extern void dy_scaling_vectors(const double **rscale, const double **cscale) ;
1740
1741/*
1742 dy_coldstart.c
1743*/
1744
1746 dy_crash(void) ;
1747
1748/*
1749 dy_warmstart.c
1750*/
1751
1753
1754/*
1755 dy_hotstart.c
1756*/
1757
1759
1760/*
1761 dy_basis.c
1762*/
1763
1764extern dyret_enum dy_factor(flags *calcflgs),
1765 dy_pivot(int xipos, double abarij, double maxabarj) ;
1766extern double dy_chkpiv(double abarij, double maxabarj) ;
1767extern void dy_btran(double *col), dy_ftran(double *col, bool save) ;
1768extern bool dy_setpivparms(int curdelta, int mindelta) ;
1769extern char *dy_prtpivparms(int lvl) ;
1770
1771/*
1772 dy_bound.c
1773*/
1774
1775extern int dy_activateBndCons(consys_struct *orig_sys) ;
1776extern int dy_dualaddvars(consys_struct *orig_sys) ;
1777
1778/*
1779 dy_conmgmt.c
1780*/
1781
1782extern bool dy_loadcon(consys_struct *orig_sys, int orig_ndx,
1783 bool genvars, int *inactndxs) ;
1784extern bool dy_deactNBLogPrimCon(consys_struct *orig_sys, int i),
1787 int *inactvars),
1789 int cnt, int *ocndxs, int **inactvars) ;
1790extern int dy_deactivateCons(consys_struct *orig_sys),
1791 dy_activateCons(consys_struct *orig_sys, bool with_vars) ;
1792
1793/*
1794 dy_varmgmt.c
1795*/
1796
1797extern bool dy_actNBPrimArch(consys_struct *orig_sys, int ovndx),
1799 int cnt, int *ovndxs),
1800 dy_deactBPrimArch(consys_struct *orig_sys, int ovndx),
1801 dy_deactNBPrimArch(consys_struct *orig_sys, int ovndx) ;
1802extern int dy_deactivateVars(consys_struct *orig_sys),
1803 dy_activateVars(consys_struct *orig_sys, int *candidates) ;
1804
1805/*
1806 dy_primalpivot.c
1807*/
1808
1809extern dyret_enum dy_primalin(int initcol, int scan, int *xjndx, int *nextcol),
1810 dy_primalpivot(int xjndx, int indir, int *xindx, int *outdir,
1811 double *abarij, double *delta, int *xjcand),
1812 dy_degenout(int level) ;
1813
1814/*
1815 dy_duenna.c
1816*/
1817
1818extern dyret_enum dy_duenna(dyret_enum pivresult, int xjndx, int xindx,
1819 int xjcand, int xicand),
1820 dy_accchk(flags *checks) ;
1821
1822/*
1823 dy_pivreject.c
1824*/
1825
1827 double abarij, double maxabarij),
1829extern bool dy_clrpivrej(int *entries) ;
1830extern void dy_checkpivtol(void) ;
1831extern void dy_initpivrej(int sze), dy_freepivrej(void) ;
1832
1833
1834/*
1835 dy_primal.c
1836*/
1837
1838extern lpret_enum dy_primal(void) ;
1839extern bool dy_initp1obj(void),dy_swapobjs(dyphase_enum phase) ;
1840
1841/*
1842 dy_dualpivot.c
1843*/
1844
1845extern dyret_enum
1846 dy_dualout(int *xindx),
1847 dy_dualpivot(int xindx, int outdir,
1848 int *p_xjndx, int *p_indir, double *p_cbarj,
1849 double *p_abarij, double *p_delta, int *xicand),
1850 dy_dualdegenout(int level) ;
1851
1852/*
1853 dy_dual.c
1854*/
1855
1856extern lpret_enum dy_dual(void) ;
1857
1858#endif /* DYLP_INTERNAL */
1859
1860/*
1861 dy_setup.c
1862*/
1863
1864extern void dy_defaults(lpopts_struct **opts, lptols_struct **tols),
1866 lpopts_struct *opts, lptols_struct *tols),
1868
1869
1870/*
1871 dylp.c
1872*/
1873
1874extern lpret_enum dylp(lpprob_struct *orig_lp, lpopts_struct *orig_opts,
1875 lptols_struct *orig_tols, lpstats_struct *orig_stats) ;
1876extern void *dy_getOwner() ;
1877
1878/*
1879 dylp_utils.c
1880*/
1881
1882#ifdef DYLP_INTERNAL
1883
1885extern dyret_enum dy_updateprimals(int j, double deltaj, double *p_abarj) ;
1886extern bool dy_reducerhs(double *rhs, bool init),
1888extern void dy_calcduals(void),dy_setbasicstatus(void),
1890extern double dy_calcobj(void),dy_calcdualobj(void),dy_calcpinfeas(void) ;
1891extern void dy_finishup(lpprob_struct *orig_lp, dyphase_enum phase) ;
1892
1893#ifdef DYLP_PARANOIA
1894
1895extern bool dy_chkstatus(int vndx),
1896 dy_chkdysys(consys_struct *orig_sys) ;
1897extern void dy_chkdual(int lvl) ;
1898
1899#endif
1900
1901#endif /* DYLP_INTERNAL */
1902
1903extern bool dy_dupbasis(int dst_basissze, basis_struct **p_dst_basis,
1904 basis_struct *src_basis, int dst_statussze,
1905 flags **p_dst_status,
1906 int src_statuslen, flags *src_status) ;
1907extern void dy_freesoln(lpprob_struct *lpprob) ;
1908
1909/*
1910 dy_penalty.c
1911*/
1912
1913extern bool dy_pricenbvars(lpprob_struct *orig_lp, flags priceme,
1914 double **p_ocbar, int *p_nbcnt, int **p_nbvars),
1915 dy_pricedualpiv(lpprob_struct *orig_lp, int oxindx,
1916 double nubi, double xi, double nlbi,
1917 int nbcnt, int *nbvars,
1918 double *cbar, double *p_upeni, double *p_dpeni) ;
1919
1920/*
1921 dy_tableau.c
1922*/
1923
1924extern bool dy_abarj(lpprob_struct *orig_lp, int tgt_j, double **p_abarj) ;
1925extern bool dy_betaj(lpprob_struct *orig_lp, int tgt_j, double **p_betaj) ;
1926extern bool dy_betak(lpprob_struct *orig_lp, int col_k, double **p_betaj) ;
1927extern bool dy_betai(lpprob_struct *orig_lp, int tgt_i, double **p_betai) ;
1928extern bool dy_abari(lpprob_struct *orig_lp, int tgt_i, double **p_abari,
1929 double **p_betai) ;
1930
1931/*
1932 dy_rays.c
1933*/
1934
1935extern bool dy_primalRays(lpprob_struct *orig_lp,
1936 int *p_numRays, double ***p_rays) ;
1937extern bool dy_dualRays(lpprob_struct *orig_lp, bool fullRay,
1938 int *p_numRays, double ***p_rays, bool trueDuals) ;
1939
1940/*
1941 dy_solutions.c
1942*/
1943
1944extern void dy_colDuals(lpprob_struct *orig_lp, double **p_cbar,
1945 bool trueDuals) ;
1946extern void dy_rowDuals(lpprob_struct *orig_lp, double **p_y,
1947 bool trueDuals) ;
1948extern void dy_rowDualsGivenC(lpprob_struct *orig_lp, double **p_y,
1949 const double *c, bool trueDuals) ;
1950
1951extern void dy_colPrimals(lpprob_struct *orig_lp, double **p_x) ;
1952extern void dy_rowPrimals(lpprob_struct *orig_lp,
1953 double **p_xB, int **p_indB) ;
1954extern void dy_logPrimals(lpprob_struct *orig_lp, double **p_logx) ;
1955
1956extern void dy_colStatus(lpprob_struct *orig_lp, flags **p_colstat) ;
1957extern void dy_logStatus(lpprob_struct *orig_lp, flags **p_logstat) ;
1958
1959extern bool dy_expandxopt(lpprob_struct *lp, double **p_xopt) ;
1960
1961/*
1962 dylp_io.c
1963*/
1964
1965#include <dylib_io.h>
1966
1967#ifdef DYLP_INTERNAL
1968
1969extern void dy_logpivot(dyret_enum result, int xjndx, int indir, double cbarj,
1970 int xindx, int outdir, double abarij, double delta) ;
1971extern const char *dy_prtdyret(dyret_enum retcode) ;
1972
1973#endif /* DYLP_INTERNAL */
1974
1975extern const char *dy_prtlpret(lpret_enum lpret),
1976 *dy_prtlpphase(dyphase_enum phase, bool abbrv) ;
1977extern char *dy_prtvstat(flags status) ;
1978extern bool dy_dumpcompact(ioid chn, bool echo, lpprob_struct *soln,
1979 bool nbzeros) ;
1980extern void dy_setlogchn (ioid chn) ;
1981extern void dy_setgtxecho (bool echo) ;
1982
1983/*
1984 dy_statistics.c
1985
1986 These routines are compiled unconditionally, but note that the compile-time
1987 symbol DYLP_STATISTICS must be defined before dylp will actually take the
1988 time to collect detailed statistics. See dy_statistics.c for additional
1989 instructions.
1990*/
1991
1992extern void dy_initstats(lpstats_struct **p_lpstats, consys_struct *orig_sys),
1993 dy_dumpstats(ioid chn, bool echo, lpstats_struct *lpstats,
1994 consys_struct *orig_sys),
1996
1997#ifdef DYLP_INTERNAL
1998
1999extern void dy_finalstats(lpstats_struct *lpstats) ;
2000
2001#endif /* DYLP_INTERNAL */
2002
2003
2004#endif /* _DYLP_H */
int ioid
Definition dylib_io.h:39
unsigned int flags
Definition dylib_std.h:95
int * dy_actvars
lpstats_struct * dy_stats
char * dy_prtpivparms(int lvl)
bool dy_abarj(lpprob_struct *orig_lp, int tgt_j, double **p_abarj)
bool dy_actNBPrimArch(consys_struct *orig_sys, int ovndx)
void dy_checkpivtol(void)
int * dy_brkout
Definition dylp.h:1724
void dy_freelclsystem(lpprob_struct *orig_lp, bool freesys)
dyret_enum dy_duenna(dyret_enum pivresult, int xjndx, int xindx, int xjcand, int xicand)
double * dy_y
Definition dylp.h:1726
void dy_colStatus(lpprob_struct *orig_lp, flags **p_colstat)
dyret_enum dy_pivot(int xipos, double abarij, double maxabarj)
bool dy_dumpcompact(ioid chn, bool echo, lpprob_struct *soln, bool nbzeros)
int * dy_degenset
Definition dylp.h:1724
lp_struct * dy_lp
void dy_setgtxecho(bool echo)
void dy_pseinit(void)
#define DYSTATS_HISTBINS
Definition dylp.h:1301
void dy_btran(double *col)
lpret_enum dy_primal(void)
double * dy_xbasic
Definition dylp.h:1726
dyret_enum dy_updateprimals(int j, double deltaj, double *p_abarj)
ibtype_enum
Definition dylp.h:766
@ ibINV
Definition dylp.h:766
@ ibARCH
Definition dylp.h:766
@ ibLOGICAL
Definition dylp.h:766
@ ibSLACK
Definition dylp.h:766
dyret_enum dy_factor(flags *calcflgs)
dyret_enum dy_coldstart(consys_struct *orig_sys)
lpopts_struct * dy_opts
lpret_enum dy_dual(void)
dyret_enum dy_dualdegenout(int level)
int * dy_actcons
Definition dylp.h:1722
dyret_enum dy_warmstart(lpprob_struct *orig_lp)
bool dy_isscaled(void)
double dy_calcdualobj(void)
bool dy_dupbasis(int dst_basissze, basis_struct **p_dst_basis, basis_struct *src_basis, int dst_statussze, flags **p_dst_status, int src_statuslen, flags *src_status)
bool dy_deactBLogPrimCon(consys_struct *orig_sys, int i)
int dy_activateCons(consys_struct *orig_sys, bool with_vars)
void dy_logStatus(lpprob_struct *orig_lp, flags **p_logstat)
dyret_enum dy_crash(void)
bool dy_abari(lpprob_struct *orig_lp, int tgt_i, double **p_abari, double **p_betai)
dyret_enum dy_dealWithPunt(void)
void dy_setprintopts(int lvl, lpopts_struct *opts)
consys_struct * dy_sys
cxtype_enum
Definition dylp.h:788
@ cxINITIALLP
Definition dylp.h:789
@ cxUSERPIV
Definition dylp.h:789
@ cxINV
Definition dylp.h:788
@ cxBANDC
Definition dylp.h:789
@ cxSINGLELP
Definition dylp.h:789
@ cxUNLOAD
Definition dylp.h:788
@ cxLOAD
Definition dylp.h:788
void dy_checkdefaults(consys_struct *sys, lpopts_struct *opts, lptols_struct *tols)
void dy_setbasicstatus(void)
bool dy_betak(lpprob_struct *orig_lp, int col_k, double **p_betaj)
dyret_enum dy_dualpivot(int xindx, int outdir, int *p_xjndx, int *p_indir, double *p_cbarj, double *p_abarij, double *p_delta, int *xicand)
lpret_enum dylp(lpprob_struct *orig_lp, lpopts_struct *orig_opts, lptols_struct *orig_tols, lpstats_struct *orig_stats)
dyret_enum dy_primalpivot(int xjndx, int indir, int *xindx, int *outdir, double *abarij, double *delta, int *xjcand)
bool dy_loadcon(consys_struct *orig_sys, int orig_ndx, bool genvars, int *inactndxs)
void dy_finishup(lpprob_struct *orig_lp, dyphase_enum phase)
void dy_freesoln(lpprob_struct *lpprob)
char * dy_prtvstat(flags status)
void dy_ftran(double *col, bool save)
void dy_freepivrej(void)
bool dy_expandxopt(lpprob_struct *lp, double **p_xopt)
void dy_rowDualsGivenC(lpprob_struct *orig_lp, double **p_y, const double *c, bool trueDuals)
bool dy_deactBPrimArch(consys_struct *orig_sys, int ovndx)
bool dy_pricedualpiv(lpprob_struct *orig_lp, int oxindx, double nubi, double xi, double nlbi, int nbcnt, int *nbvars, double *cbar, double *p_upeni, double *p_dpeni)
int * dy_ddegenset
Definition dylp.h:1724
void dy_calcduals(void)
void dy_initpivrej(int sze)
bool dy_reducerhs(double *rhs, bool init)
#define DYSTATS_MAXDEGEN
Definition dylp.h:1300
bool dy_actBLogPrimConList(consys_struct *orig_sys, int cnt, int *ocndxs, int **inactvars)
bool dy_deactNBLogPrimCon(consys_struct *orig_sys, int i)
bool dy_initp1obj(void)
lptols_struct * dy_tols
bool * dy_frame
const char * dy_prtlpret(lpret_enum lpret)
int dy_activateVars(consys_struct *orig_sys, int *candidates)
bool dy_calccbar(void)
void dy_dumpstats(ioid chn, bool echo, lpstats_struct *lpstats, consys_struct *orig_sys)
bool dy_calcprimals(void)
dyret_enum
Definition dylp.h:274
@ dyrSTALLED
Definition dylp.h:274
@ dyrRESELECT
Definition dylp.h:278
@ dyrSINGULAR
Definition dylp.h:275
@ dyrPATCHED
Definition dylp.h:277
@ dyrOPTIMAL
Definition dylp.h:279
@ dyrPUNT
Definition dylp.h:278
@ dyrLOSTPFEAS
Definition dylp.h:276
@ dyrDEGEN
Definition dylp.h:276
@ dyrMADPIV
Definition dylp.h:276
@ dyrBSPACE
Definition dylp.h:275
@ dyrACCCHK
Definition dylp.h:278
@ dyrSWING
Definition dylp.h:279
@ dyrITERLIM
Definition dylp.h:274
@ dyrREQCHK
Definition dylp.h:278
@ dyrUNBOUND
Definition dylp.h:279
@ dyrLOSTDFEAS
Definition dylp.h:276
@ dyrOK
Definition dylp.h:277
@ dyrFATAL
Definition dylp.h:274
@ dyrINFEAS
Definition dylp.h:279
@ dyrNUMERIC
Definition dylp.h:275
@ dyrINV
Definition dylp.h:277
bool dy_initlclsystem(lpprob_struct *orig_lp, bool hotstart)
bool dy_actNBPrimArchList(consys_struct *orig_sys, int cnt, int *ovndxs)
bool dy_betaj(lpprob_struct *orig_lp, int tgt_j, double **p_betaj)
bool dy_swapobjs(dyphase_enum phase)
int * dy_origcons
Definition dylp.h:1722
int * dy_var2basis
Definition dylp.h:1723
int * dy_origvars
Definition dylp.h:1722
bool dy_actBLogPrimCon(consys_struct *orig_sys, int i, int *inactvars)
bool dy_clrpivrej(int *entries)
void * dy_getOwner()
dyret_enum dy_addtopivrej(int xkndx, dyret_enum why, double abarij, double maxabarij)
void dy_rowDuals(lpprob_struct *orig_lp, double **p_y, bool trueDuals)
dyphase_enum
Definition dylp.h:212
@ dyFORCEDUAL
Definition dylp.h:216
@ dyPRIMAL1
Definition dylp.h:213
@ dyGENCON
Definition dylp.h:215
@ dyFORCEFULL
Definition dylp.h:216
@ dyPURGECON
Definition dylp.h:215
@ dyGENVAR
Definition dylp.h:214
@ dyDONE
Definition dylp.h:217
@ dyPRIMAL2
Definition dylp.h:213
@ dyADDCON
Definition dylp.h:215
@ dyINV
Definition dylp.h:212
@ dyPURGEVAR
Definition dylp.h:214
@ dyDUAL
Definition dylp.h:213
@ dyFORCEPRIMAL
Definition dylp.h:216
@ dyINIT
Definition dylp.h:212
@ dyADDVAR
Definition dylp.h:214
dyret_enum dy_primalin(int initcol, int scan, int *xjndx, int *nextcol)
void dy_setlogchn(ioid chn)
void dy_scaling_vectors(const double **rscale, const double **cscale)
void dy_logpivot(dyret_enum result, int xjndx, int indir, double cbarj, int xindx, int outdir, double abarij, double delta)
ioid dy_logchn
void dy_freestats(lpstats_struct **p_lpstats)
double * dy_x
bool dy_setpivparms(int curdelta, int mindelta)
double * dy_gamma
Definition dylp.h:1726
int * dy_basis
Definition dylp.h:1723
void dy_defaults(lpopts_struct **opts, lptols_struct **tols)
int dy_deactivateCons(consys_struct *orig_sys)
double * dy_cbar
Definition dylp.h:1726
lpret_enum
Definition dylp.h:170
@ lpPUNT
Definition dylp.h:174
@ lpFATAL
Definition dylp.h:170
@ lpACCCHK
Definition dylp.h:172
@ lpINFEAS
Definition dylp.h:171
@ lpFORCEFULL
Definition dylp.h:175
@ lpITERLIM
Definition dylp.h:173
@ lpLOSTFEAS
Definition dylp.h:174
@ lpFORCEDUAL
Definition dylp.h:175
@ lpOPTIMAL
Definition dylp.h:171
@ lpNOSPACE
Definition dylp.h:173
@ lpSWING
Definition dylp.h:171
@ lpUNBOUNDED
Definition dylp.h:171
@ lpINV
Definition dylp.h:170
@ lpSTALLED
Definition dylp.h:173
@ lpFORCEPRIMAL
Definition dylp.h:175
bool dy_gtxecho
flags * dy_status
consys_struct * dy_scaled_origsys()
int dy_deactivateVars(consys_struct *orig_sys)
bool dy_primalRays(lpprob_struct *orig_lp, int *p_numRays, double ***p_rays)
int dy_dualaddvars(consys_struct *orig_sys)
void dy_rowPrimals(lpprob_struct *orig_lp, double **p_xB, int **p_indB)
bool dy_deactNBPrimArch(consys_struct *orig_sys, int ovndx)
lpret_enum dyret2lpret(dyret_enum dyret)
void dy_colPrimals(lpprob_struct *orig_lp, double **p_x)
void dy_dseinit(void)
dyret_enum dy_hotstart(lpprob_struct *orig_lp)
void dy_colDuals(lpprob_struct *orig_lp, double **p_cbar, bool trueDuals)
dyret_enum dy_degenout(int level)
dyret_enum dy_accchk(flags *checks)
bool dy_pricenbvars(lpprob_struct *orig_lp, flags priceme, double **p_ocbar, int *p_nbcnt, int **p_nbvars)
dyret_enum dy_dualout(int *xindx)
double dy_calcpinfeas(void)
void * dy_owner
bool dy_betai(lpprob_struct *orig_lp, int tgt_i, double **p_betai)
double * dy_rho
Definition dylp.h:1726
double dy_calcobj(void)
const char * dy_prtdyret(dyret_enum retcode)
bool dy_dualRays(lpprob_struct *orig_lp, bool fullRay, int *p_numRays, double ***p_rays, bool trueDuals)
double dy_chkpiv(double abarij, double maxabarj)
int dy_activateBndCons(consys_struct *orig_sys)
void dy_logPrimals(lpprob_struct *orig_lp, double **p_logx)
const char * dy_prtlpphase(dyphase_enum phase, bool abbrv)
void dy_finalstats(lpstats_struct *lpstats)
void dy_initstats(lpstats_struct **p_lpstats, consys_struct *orig_sys)
#define print
Definition glplib.h:28
basisel_struct * el
Definition dylp.h:455
int len
Definition dylp.h:454
bool installed
Definition dylp.h:1563
double infeas
Definition dylp.h:1559
int infvars_sze
Definition dylp.h:1565
int iters
Definition dylp.h:1574
int * infvars
Definition dylp.h:1566
bool init_dse
Definition dylp.h:1558
bool forcedfull
Definition dylp.h:1573
double cd
Definition dylp.h:1591
double fd
Definition dylp.h:1594
int ndx
Definition dylp.h:1561
int idlecnt
Definition dylp.h:1589
double fp
Definition dylp.h:1593
double norm1
Definition dylp.h:1595
double max
Definition dylp.h:1597
dyphase_enum phase
Definition dylp.h:1551
double z
Definition dylp.h:1553
double vd
Definition dylp.h:1592
int degenpivcnt
Definition dylp.h:1588
dyphase_enum next
Definition dylp.h:1556
int infcnt
Definition dylp.h:1564
double piv
Definition dylp.h:1590
dyphase_enum active
Definition dylp.h:1555
bool init_pse
Definition dylp.h:1557
double ratio
Definition dylp.h:1562
int loadable
Definition dylp.h:1569
int maxndx
Definition dylp.h:1598
double norm2
Definition dylp.h:1596
lpret_enum lpret
Definition dylp.h:1552
int etas
Definition dylp.h:1584
int pivs
Definition dylp.h:1575
double inactzcorr
Definition dylp.h:1554
bool prev_pivok
Definition dylp.h:1583
int degen
Definition dylp.h:1587
bool pivok
Definition dylp.h:1582
double * p1obj
Definition dylp.h:1567
int infeascnt
Definition dylp.h:1560
bool cons
Definition dylp.h:1155
bool degen
Definition dylp.h:1135
int pricing
Definition dylp.h:1164
int degenpivlim
Definition dylp.h:1136
int degenlite
Definition dylp.h:1137
double i2u
Definition dylp.h:1153
bool i2lopen
Definition dylp.h:1150
bool flex
Definition dylp.h:1120
double i1u
Definition dylp.h:1148
bool copyorigsys
Definition dylp.h:1140
bool i1lopen
Definition dylp.h:1145
bool forcewarm
Definition dylp.h:1133
bool flips
Definition dylp.h:1159
double frac
Definition dylp.h:1144
bool i2valid
Definition dylp.h:1149
int pivreject
Definition dylp.h:1166
int conmgmt
Definition dylp.h:1172
int coldvars
Definition dylp.h:1131
int pivoting
Definition dylp.h:1165
bool forcecold
Definition dylp.h:1132
bool fullsys
Definition dylp.h:1139
double i1l
Definition dylp.h:1146
double i2l
Definition dylp.h:1151
bool patch
Definition dylp.h:1138
int idlelim
Definition dylp.h:1118
cxtype_enum context
Definition dylp.h:1115
bool i1uopen
Definition dylp.h:1147
float vars
Definition dylp.h:1142
bool i2uopen
Definition dylp.h:1152
int scaling
Definition dylp.h:1141
ibtype_enum coldbasis
Definition dylp.h:1154
int iterlim
Definition dylp.h:1117
bool allownopiv
Definition dylp.h:1121
bool usedual
Definition dylp.h:1134
int tableau
Definition dylp.h:1175
int dualadd
Definition dylp.h:1130
int varmgmt
Definition dylp.h:1173
basis_struct * basis
Definition dylp.h:595
bool fullsys
Definition dylp.h:594
void * owner
Definition dylp.h:587
int colsze
Definition dylp.h:600
double obj
Definition dylp.h:591
double * x
Definition dylp.h:597
flags ctlopts
Definition dylp.h:588
int iters
Definition dylp.h:592
dyphase_enum phase
Definition dylp.h:589
int rowsze
Definition dylp.h:601
bool * actvars
Definition dylp.h:599
lpret_enum lpret
Definition dylp.h:590
consys_struct * consys
Definition dylp.h:593
double * y
Definition dylp.h:598
flags * status
Definition dylp.h:596
float min
Definition dylp.h:1316
float max
Definition dylp.h:1315
int flippable
Definition dylp.h:1329
int pivtol_red
Definition dylp.h:1325
dyphase_enum ini_simplex
Definition dylp.h:1305
float avgpivs
Definition dylp.h:1320
float avgsiz
Definition dylp.h:1349
int * deactcnt
Definition dylp.h:1309
int nontrivial
Definition dylp.h:1333
double * angle
Definition dylp.h:1307
double min_pivtol
Definition dylp.h:1326
int * actcnt
Definition dylp.h:1308
bool * init
Definition dylp.h:1310
double swing
Definition dylp.h:678
double toobig
Definition dylp.h:679
double purgevar
Definition dylp.h:681
double reframe
Definition dylp.h:682
double dchk
Definition dylp.h:673
double pchk
Definition dylp.h:669
double dfeas_scale
Definition dylp.h:675
double pfeas_scale
Definition dylp.h:671
double purge
Definition dylp.h:680
double pivot
Definition dylp.h:676
double bogus
Definition dylp.h:677
double cost
Definition dylp.h:672
double zero
Definition dylp.h:668
double dfeas
Definition dylp.h:674
double inf
Definition dylp.h:667
double pfeas
Definition dylp.h:670