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,
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,
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,
277  dyrINV = 0, dyrOK = 1, dyrPATCHED = 2,
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 ;
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
587  double obj ;
588  int iters ;
592  double *x ;
593  double *y ;
594  bool *actvars ;
595  int colsze ;
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
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 ;
1125  bool patch ;
1126  bool fullsys ;
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 ;
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 ;
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] ;
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 ;
1313  double min_pivtol ;
1314  int puntcall ;
1315  int puntret ; } pivrej ;
1316  struct { int flippable ;
1317  int cnt ;
1318  int cands ;
1319  int promote ;
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),
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 */
int rays
Definition: dylp.h:1163
double reframe
Definition: dylp.h:677
int prevpiv
Definition: dylp.h:1306
double i1u
Definition: dylp.h:1135
int actlvl
Definition: dylp.h:1113
int addvar
Definition: dylp.h:1116
int strat
Definition: dylp.h:1106
Definition: dylp.h:276
int deactlvl
Definition: dylp.h:1115
double inf
Definition: dylp.h:662
Definition: dylp.h:170
double purge
Definition: dylp.h:675
int force
Definition: dylp.h:1161
char * dy_prtvstat(flags status)
double pfeas
Definition: dylp.h:665
int iters
Definition: dylp.h:588
Definition: dylp.h:761
Definition: dylp.h:761
unsigned int flags
Definition: dylib_std.h:98
int rowsze
Definition: dylp.h:596
double * angle
Definition: dylp.h:1294
int setup
Definition: dylp.h:1149
bool dy_abarj(lpprob_struct *orig_lp, int tgt_j, double **p_abarj)
bool flex
Definition: dylp.h:1107
bool vars
Definition: dylp.h:1143
Definition: dylp.h:170
int * deactcnt
Definition: dylp.h:1296
void dy_initstats(lpstats_struct **p_lpstats, consys_struct *orig_sys)
basisel_struct * el
Definition: dylp.h:455
double i2l
Definition: dylp.h:1138
flags * status
Definition: dylp.h:591
void dy_rowPrimals(lpprob_struct *orig_lp, double **p_xB, int **p_indB)
bool p2d
Definition: dylp.h:1145
int pivtol_red
Definition: dylp.h:1312
int chgcnt2
Definition: dylp.h:1334
#define DYSTATS_MAXDEGEN
Definition: dylp.h:1287
double zero
Definition: dylp.h:663
int varmgmt
Definition: dylp.h:1160
Definition: dylp.h:172
cxtype_enum
Definition: dylp.h:777
dyret_enum
Definition: dylp.h:274
Definition: dylp.h:215
void dy_colPrimals(lpprob_struct *orig_lp, double **p_x)
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)
double purgevar
Definition: dylp.h:676
void dy_setprintopts(int lvl, lpopts_struct *opts)
int actlim
Definition: dylp.h:1114
bool * actvars
Definition: dylp.h:594
int colsze
Definition: dylp.h:595
float avgpivs
Definition: dylp.h:1307
Definition: dylp.h:277
Definition: dylp.h:278
int maxcnt
Definition: dylp.h:1330
const char * dy_prtlpphase(dyphase_enum phase, bool abbrv)
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)
int soln
Definition: dylp.h:1164
int scaling
Definition: dylp.h:1128
bool i2valid
Definition: dylp.h:1136
Definition: dylp.h:212
Definition: dylp.h:214
void dy_colDuals(lpprob_struct *orig_lp, double **p_cbar, bool trueDuals)
int chgcnt1
Definition: dylp.h:1333
void dy_rowDuals(lpprob_struct *orig_lp, double **p_y, bool trueDuals)
bool forcecold
Definition: dylp.h:1119
const char * dy_prtlpret(lpret_enum lpret)
int pivoting
Definition: dylp.h:1152
bool dy_betaj(lpprob_struct *orig_lp, int tgt_j, double **p_betaj)
Definition: dylp.h:777
Definition: dylp.h:274
float vars
Definition: dylp.h:1129
int pivrnks
Definition: dylp.h:1323
Definition: dylp.h:171
#define DYSTATS_HISTBINS
Definition: dylp.h:1288
double bogus
Definition: dylp.h:672
float avgsiz
Definition: dylp.h:1336
Definition: dylp.h:174
void dy_logPrimals(lpprob_struct *orig_lp, double **p_logx)
int phase1
Definition: dylp.h:1155
double * x
Definition: dylp.h:592
Definition: dylp.h:279
void dy_defaults(lpopts_struct **opts, lptols_struct **tols)
bool * fin
Definition: dylp.h:1298
Definition: dylp.h:171
int phase2
Definition: dylp.h:1156
ibtype_enum coldbasis
Definition: dylp.h:1141
cxtype_enum context
Definition: dylp.h:1102
bool degen
Definition: dylp.h:1122
int totpivs
Definition: dylp.h:1331
bool dy_pricenbvars(lpprob_struct *orig_lp, flags priceme, double **p_ocbar, int *p_nbcnt, int **p_nbvars)
int ioid
Definition: dylib_io.h:39
double toobig
Definition: dylp.h:674
bool cons
Definition: dylp.h:1142
int maxpivs
Definition: dylp.h:1308
dyphase_enum phase
Definition: dylp.h:585
bool forcewarm
Definition: dylp.h:1120
bool copyorigsys
Definition: dylp.h:1127
ioid dy_logchn
ibtype_enum
Definition: dylp.h:761
bool i2uopen
Definition: dylp.h:1139
int degenlite
Definition: dylp.h:1124
int iterlim
Definition: dylp.h:1104
int conmgmt
Definition: dylp.h:1159
double dchk
Definition: dylp.h:668
int factor
Definition: dylp.h:1110
int dualadd
Definition: dylp.h:1117
int degenpivlim
Definition: dylp.h:1123
Definition: dylp.h:761
bool dy_dualRays(lpprob_struct *orig_lp, bool fullRay, int *p_numRays, double ***p_rays, bool trueDuals)
bool d2p
Definition: dylp.h:1144
int promote
Definition: dylp.h:1319
Definition: dylp.h:777
flags ctlopts
Definition: dylp.h:584
bool dy_primalRays(lpprob_struct *orig_lp, int *p_numRays, double ***p_rays)
void dy_logStatus(lpprob_struct *orig_lp, flags **p_logstat)
double dfeas_scale
Definition: dylp.h:670
int basis
Definition: dylp.h:1158
Definition: dylp.h:217
int degen
Definition: dylp.h:1154
Definition: dylp.h:277
float cons
Definition: dylp.h:1130
Definition: dylp.h:214
int puntret
Definition: dylp.h:1315
bool i1uopen
Definition: dylp.h:1134
double obj
Definition: dylp.h:587
double pchk
Definition: dylp.h:664
double i1l
Definition: dylp.h:1133
bool dy_gtxecho
int len
Definition: dylp.h:454
int scan
Definition: dylp.h:1103
double * y
Definition: dylp.h:593
int tableau
Definition: dylp.h:1162
dyphase_enum
Definition: dylp.h:212
double dfeas
Definition: dylp.h:669
bool dy_betai(lpprob_struct *orig_lp, int tgt_i, double **p_betai)
double i2u
Definition: dylp.h:1140
void dy_dumpstats(ioid chn, bool echo, lpstats_struct *lpstats, consys_struct *orig_sys)
int coldvars
Definition: dylp.h:1118
int * actcnt
Definition: dylp.h:1295
dyphase_enum ini_simplex
Definition: dylp.h:1292
bool i1lopen
Definition: dylp.h:1132
Definition: dylp.h:212
int vndx
Definition: dylp.h:451
bool allownopiv
Definition: dylp.h:1108
int pivreject
Definition: dylp.h:1153
double pfeas_scale
Definition: dylp.h:666
void dy_freestats(lpstats_struct **p_lpstats)
consys_struct * consys
Definition: dylp.h:589
bool fullsys
Definition: dylp.h:1126
bool dy_abari(lpprob_struct *orig_lp, int tgt_i, double **p_abari, double **p_betai)
bool * init
Definition: dylp.h:1297
int check
Definition: dylp.h:1111
double frac
Definition: dylp.h:1131
void print(const char *fmt,...)
int pricing
Definition: dylp.h:1151
int idlelim
Definition: dylp.h:1105
void dy_colStatus(lpprob_struct *orig_lp, flags **p_colstat)
void dy_freesoln(lpprob_struct *lpprob)
int maxrnk
Definition: dylp.h:1324
lpret_enum lpret
Definition: dylp.h:586
int groom
Definition: dylp.h:1112
lpret_enum dylp(lpprob_struct *orig_lp, lpopts_struct *orig_opts, lptols_struct *orig_tols, lpstats_struct *orig_stats)
bool dy_expandxopt(lpprob_struct *lp, double **p_xopt)
Definition: dylp.h:215
int dual
Definition: dylp.h:1157
int flippable
Definition: dylp.h:1316
int maxsiz
Definition: dylp.h:1337
int puntcall
Definition: dylp.h:1314
void dy_checkdefaults(consys_struct *sys, lpopts_struct *opts, lptols_struct *tols)
double cost
Definition: dylp.h:667
bool flips
Definition: dylp.h:1146
float max
Definition: dylp.h:1302
double pivot
Definition: dylp.h:671
int major
Definition: dylp.h:1147
Definition: dylp.h:213
bool usedual
Definition: dylp.h:1121
bool patch
Definition: dylp.h:1125
bool i2lopen
Definition: dylp.h:1137
lpret_enum
Definition: dylp.h:170
double swing
Definition: dylp.h:673
double min_pivtol
Definition: dylp.h:1313
int nontrivial
Definition: dylp.h:1320
basis_struct * basis
Definition: dylp.h:590
int crash
Definition: dylp.h:1150
float min
Definition: dylp.h:1303
bool dy_dumpcompact(ioid chn, bool echo, lpprob_struct *soln, bool nbzeros)