# dylp.h

Go to the documentation of this file.

    00001 /*
    00002   This file is a part of the Dylp LP distribution.
    00003
    00004         Copyright (C) 2005 -- 2007 Lou Hafer
    00005
    00006         School of Computing Science
    00007         Simon Fraser University
    00008         Burnaby, B.C., V5A 1S6, Canada
    00009         lou@cs.sfu.ca
    00010
    00011   This code is licensed under the terms of the Eclipse Public License (EPL).
    00012 */
    00013
    00014 #ifndef _DYLP_H
    00015 #define _DYLP_H
    00016
    00017 /*
    00018   @(#)dylp.h    4.6     10/15/05
    00019   svn/cvs: $Id: dylp.h 407 2010-12-31 20:48:48Z lou $
    00020
    00021   This file contains definitions related to dylp, a subroutine library which
    00022   implements a dynamic (primal-dual) linear programming algorithm based on
    00023   the algorithm described by Padberg in Linear Optimisation & Extensions,
    00024   Springer-Verlag, 1995.  dylp also owes a debt to previous and contemporary
    00025   codes the author has worked with --- la05, bandbx, zoom/xmp, ylp, and glpk.
    00026
    00027   At minimum, dylp requires only a constraint system. Since it manages a
    00028   dynamically sized private copy of the constraint system while solving the
    00029   LP, there's no point in having the client attach logical variables (they'd
    00030   just get in the way, really).
    00031
    00032   dylp will accept a basis specification. This takes the form of a status
    00033   vector giving the status of all variables, and a basis vector specifying
    00034   the active constraints and their associated basic variables. From this
    00035   dylp will construct an initial active problem which consists of exactly
    00036   the given constraints and basic variables, with the logicals for the
    00037   constraints making up the nonbasic partition.
    00038
    00039   dylp returns as a solution the simplex termination code, the objective
    00040   value (or related value, appropriate for the termination code), status for
    00041   all variables, the active constraints, and the associated primal and dual
    00042   variables (put a little differently, a basis, the values of the basic
    00043   variables, and the dual variables associated with the active constraints).
    00044
    00045   The conditional compilation symbol DYLP_INTERNAL is used to delimit
    00046   definitions that should be considered internal to dylp. Don't define this
    00047   symbol in a client.
    00048 */
    00049
    00050 #include "dylib_errs.h"
    00051 #include "dylib_io.h"
    00052 #include "dy_consys.h"
    00053
    00054 /*
    00055   A few words on notation. Traditional matrix and vector notation for LP
    00056   suffers a bit when limited to ascii text, but it's readable if you're
    00057   familiar with the original. The notation in the comments and code is
    00058   loosely based on Chvatal, "Linear Programming", W.H. Freeman, 1983, which
    00059   the author happens to like.
    00060
    00061   A matrix is represented with a capital letter, e.g., B. A vector is
    00062   represented with a small letter, e.g., x. A subscript is given in angle
    00063   brackets, e.g., x<j> for the jth coefficient of x. An individual element of
    00064   a matrix has two subscripts, e.g., a<i,j> for the element in row i, column
    00065   j. Column and row vectors are shown with one subscript, e.g., a<j> for the
    00066   jth column (or row).  Whether the vector is supposed to be a column or a
    00067   row should generally be clear from context. A capital letter in the
    00068   subscript position indicates a set of elements, e.g., x<N> is the non-basic
    00069   variables.
    00070
    00071   The inverse of a matrix is denoted inv(*), e.g., the basis inverse,
    00072   inv(B).  The dot product of two vectors is denoted dot(*,*), e.g.,
    00073   dot(c,x), or sometimes just written directly, e.g., cx.
    00074
    00075   The system of constraints is assumed to be Ax <= b, with m rows and n
    00076   columns. Once the logical variables (aka slacks and artificials) have been
    00077   added, it becomes Ax = b.  A is the constraint matrix, x is the vector of
    00078   primal variables, and b is the right-hand-side (rhs).  NOTE that the
    00079   convention for indices is NOT the usual one. Logical variables are assigned
    00080   indices 1..m and architectural variables are assigned indices m+1..m+n. It
    00081   makes for more efficient addition/deletion of variables; see dy_consys.h for a
    00082   little more explanation.
    00083
    00084   There is an objective function z = cx, where z is the objective value and c
    00085   is the vector of coefficients.  dylp minimises the objective.
    00086
    00087   The matrix A is partitioned into the set of basic columns B, and the set of
    00088   non-basic columns N (sometimes A<N>). The corresponding partitions of c and
    00089   x are c<B>, x<B>, and c<N>, x<N>.
    00090
    00091   Premultiplication by the basis inverse (e.g., inv(B)a<j>) is referred to as
    00092   an `ftran'; postmultiplication (e.g., c<B>inv(B)) as a `btran'.  Quantities
    00093   that have been transformed using the basis inverse are often (but not
    00094   always) renamed as 'barred' quantities.
    00095
    00096   The basic primal variables are x<B> = inv(B)b.  The dual variables are y =
    00097   c<B>inv(B).  The jth column of A, premultiplied by inv(B), is abar<j> =
    00098   inv(B)a<j>. The reduced costs are cbar = c<N> - c<B>inv(B)N = c<N>-yN.
    00099
    00100   The variable i is used as a row index, j as a column index. Often they will
    00101   represent the entering primal variable (j) and the leaving primal variable
    00102   (i). Be aware that comments are often written as if the leaving primal
    00103   variable x<i> occupies row i of the basis. This simplifies the writing.
    00104   But keep in mind that variable x<i> can occupy an arbitrary row k of the
    00105   basis.
    00106 */
    00107
    00108 /*
    00109   Termination codes for dy_primal and dy_dual, the top level routines of the
    00110   dylp simplex algorithms. Also used by various internal routines.  Codes
    00111   marked with (*) will never be returned to the client unless dylp has
    00112   failed.
    00113
    00114   lpINV         The code is not valid (i.e., not set by an execution of
    00115                 dy_primal or dy_dual).
    00116
    00117   lpOPTIMAL     The problem has an optimal solution.
    00118
    00119   lpUNBOUNDED   The problem is unbounded.
    00120
    00121   lpSWING(*)    The problem is pseudo-unbounded: Some primal variable grew
    00122                 excessively in a single pivot.
    00123
    00124   lpINFEAS      The problem is infeasible.
    00125
    00126   lpACCCHK      An accuracy check failed and dylp's internal recovery
    00127                 algorithms could not recover the situation.
    00128
    00129   lpSTALLED     The problem has been abandoned due to stalling. (We could
    00130                 in fact actually be cycling, but that's too much trouble
    00131                 to prove.)
    00132
    00133   lpITERLIM     The problem has been abandoned because it has exceeded an
    00134                 absolute iteration limit.
    00135
    00136   lpNOSPACE     The problem has been abandoned because the basis package did
    00137                 not have sufficient space to maintain the basis.
    00138
    00139   lpLOSTFEAS    Feasibility was lost during simplex execution.
    00140
    00141   lpPUNT        The lp has punted because it ran into a pivoting problem.
    00142
    00143                 The next three codes indicate that we're in the middle of
    00144                 attempting a forced transition for error recovery purposes.
    00145
    00146   lpFORCEDUAL(*) Force a primal to dual transition.
    00147
    00148   lpFORCEPRIMAL(*) Force a dual to primal transition.
    00149
    00150   lpFORCEFULL(*) Force all inactive constraints and variables to be loaded.
    00151
    00152   lpFATAL       Fatal confusion or error of some sort; covers a multitude
    00153                 of sins.
    00154
    00155   The dual simplex routine does not have a phase I routine equivalent to
    00156   dy_primal1 for the primal simplex. (In the context of dylp, it expects
    00157   to run after dy_primal has been used to find an initial optimal solution.)
    00158
    00159   When using the dual simplex method, internal codes reflect the state of
    00160   the dual problem, but dy_dual makes the usual translation back to the
    00161   primal problem, as:
    00162
    00163   Dual          Primal          Rationale
    00164   ----          ------          ---------
    00165   lpUNBOUNDED   lpINFEAS        Standard duality theorem.
    00166
    00167   Note that lpSWING always refers to primal variables.
    00168 */
    00169
    00170 typedef enum { lpFATAL = -1, lpINV = 0,
    00171                lpOPTIMAL, lpUNBOUNDED, lpSWING, lpINFEAS,
    00172                lpACCCHK,
    00173                lpSTALLED, lpITERLIM, lpNOSPACE,
    00174                lpLOSTFEAS, lpPUNT,
    00175                lpFORCEDUAL, lpFORCEPRIMAL, lpFORCEFULL } lpret_enum ;
    00176
    00177
    00178 /*
    00179   Phase codes for dylp
    00180
    00181   dyINV         Invalid phase
    00182   dyINIT        Initialisation and setup, including establishing the
    00183                 initial set of constraints and variables and crashing the
    00184                 first basis.
    00185   dyPRIMAL1     Primal simplex phase I
    00186   dyPRIMAL2     Primal simplex phase II
    00187   dyDUAL        Dual simplex
    00188   dyPURGEVAR    Deactivation of variables.
    00189   dyGENVAR      Generation of new variables (not part of original problem).
    00190   dyADDVAR      Activation of variables.
    00191   dyPURGECON    Deactivation of constraints.
    00192   dyGENCON      Generation of new constraints (not part of original problem).
    00193   dyADDCON      Activation of constraints.
    00194   dyFORCEDUAL   Force dual feasibility (error recovery)
    00195   dyFORCEPRIMAL Force primal feasibility (error recovery)
    00196   dyFORCEFULL   Force activation of the full system (error recovery)
    00197   dyDONE        Execution is finished, for one reason or another.
    00198
    00199   It's true that new variables will be added during dyGENCON -- at the least,
    00200   each newly generated constraint will bring with it a logical variable.
    00201   dyGENVAR differs in that it is augmenting some subset of the constraints
    00202   with new variables (classic column generation, for example).
    00203
    00204   The main loop states (dyPRIMAL1 -- dyFORCEFULL) must remain a contiguous
    00205   block. dy_dumpstats counts on dyPRIMAL1 and dyFORCEPRIMAL being first and
    00206   last, respectively, in the block.
    00207
    00208   dyDONE must remain the last code --- it's used to dimension a statistics
    00209   array that tracks the number of times the main loop states are entered.
    00210 */
    00211
    00212 typedef enum { dyINV = 0, dyINIT,
    00213                dyPRIMAL1, dyPRIMAL2, dyDUAL,
    00214                dyPURGEVAR, dyGENVAR, dyADDVAR,
    00215                dyPURGECON, dyGENCON, dyADDCON,
    00216                dyFORCEDUAL, dyFORCEPRIMAL, dyFORCEFULL,
    00217                dyDONE } dyphase_enum ;
    00218 /*
    00219   General return and error codes.
    00220
    00221   Used by various routines in dylp.
    00222   No routine
    00223   uses all of these, but there's enough overlap to make one big enum
    00224   convenient.
    00225
    00226   dyrINV        Invalid code.
    00227
    00228   dyrOK         Whatever it was that was being done was done without incident.
    00229   dyrOPTIMAL    The problem is optimal.
    00230   dyrUNBOUND    The problem is unbounded.
    00231   dyrSWING      The problem is pseudo-unbounded: Some variable grew by an
    00232                 excessive amount in a single pivot.
    00233   dyrINFEAS     The problem is infeasible.
    00234
    00235   dyrREQCHK     Requests a refactor and accuracy check (triggered by various
    00236                 checks for bogus numbers).
    00237   dyrACCCHK     An accuracy check has failed.
    00238   dyrLOSTPFEAS  Primal feasibility has been lost.
    00239   dyrLOSTDFEAS  Dual feasibility has been lost.
    00240
    00241   dyrDEGEN      Degeneracy has been discovered, or a degenerate pivot has been
    00242                 taken.
    00243   dyrRESELECT   Reselect an incoming variable (after an abortive pivot
    00244                 attempt).
    00245   dyrMADPIV     The selected pivot coefficient was (numerically) unstable.
    00246   dyrPUNT       In the context of the dual simplex: the dual simplex has
    00247                 decided to punt to the primal simplex phase I, for any of
    00248                 several reasons. Generally this is indicative of the relative
    00249                 lack of sophistication in the dual simplex.
    00250                 In the context of the primal simplex: this indicates that all
    00251                 candidates to enter the basis were flagged with a NOPIVOT
    00252                 qualifier.
    00253
    00254   dyrPATCHED    The basis package managed to factor the basis after patching
    00255                 it.
    00256   dyrSINGULAR   The basis package discovered the basis was singular. (Typically
    00257                 as a consequence of a pivot gone bad.)
    00258   dyrNUMERIC    The basis package detected unacceptable growth in the basis
    00259                 coefficients.
    00260   dyrBSPACE     The basis package ran out of space for the basis
    00261                 representation.
    00262   dyrSTALLED    The LP seems to have stalled (and could possibly be cycling,
    00263                 but that's too much trouble to prove); triggered by too many
    00264                 iterations with no change in the objective.
    00265   dyrITERLIM    The iteration limit has been exceeded.
    00266
    00267   dyrFATAL      Fatal confusion; covers a multitude of sins.
    00268
    00269    The specific values assigned to some of the codes in the enum come from
    00270    earlier use of yla05 as the basis package. It's gone, but there's no
    00271    incentive to remove the values.
    00272 */
    00273
    00274 typedef enum { dyrFATAL = -10, dyrITERLIM, dyrSTALLED,
    00275                dyrBSPACE = -7, dyrSINGULAR = -6, dyrNUMERIC = -5,
    00276                dyrLOSTPFEAS, dyrLOSTDFEAS, dyrDEGEN, dyrMADPIV,
    00277                dyrINV = 0, dyrOK = 1, dyrPATCHED = 2,
    00278                dyrRESELECT, dyrREQCHK, dyrACCCHK, dyrPUNT,
    00279                dyrOPTIMAL, dyrUNBOUND, dyrSWING, dyrINFEAS } dyret_enum ;
    00280
    00281 /*
    00282   Requests and results for checks and recalculations
    00283
    00284   Some symbolic names for requesting and reporting on factoring, accuracy
    00285   checks and primal and dual variable calculations. These originated with la
    00286   Duenna, hence the lad prefix. Interpretation varies subtly from routine to
    00287   routine, so check the parameter notes.
    00288
    00289   ladPRIMALCHK  (i) set to request primal accuracy check, Bx<B> = b - Nx<N>,
    00290                 (o) set to indicate failure of check
    00291   ladDUALCHK    (i) set to to request dual accuracy check, yB = c<B>
    00292                 (o) set to indicate failure of check
    00293   ladPRIMFEAS   (i) set to request primal feasibility check (primal variables
    00294                     within bounds)
    00295                 (o) set to indicate loss of primal feasibility
    00296   ladDUALFEAS   (i) set to request dual feasibility check (reduced costs of
    00297                     proper sign)
    00298                 (o) set to indicate loss of dual feasibility
    00299   ladPFQUIET    (i) set to suppress warnings about variables which are not
    00300                     primal feasible
    00301   ladDFQUIET    (i) set to suppress warnings about variables which are not
    00302                     dual feasible
    00303   ladDUALS      (i) set to request calculation of the dual variables and
    00304                     gradient vector
    00305                 (o) set to indicate calculation of the dual variables and
    00306                     gradient vector
    00307   ladPRIMALS    (i) set to request calculation of the primal variables
    00308                 (o) set to indicate calculation of the primal variables
    00309   ladFACTOR     (i) set to indicate the basis should be refactored
    00310                 (o) set to indicate the basis has been factored
    00311   ladEXPAND     (i) set to force expansion of the space allocated for the
    00312                     basis representation
    00313                 (o) set to indicate the space allocated for the basis was
    00314                     increased
    00315 */
    00316
    00317 #define ladPRIMFEAS     1<<0
    00318 #define ladPRIMALCHK    1<<1
    00319 #define ladPFQUIET      1<<2
    00320 #define ladDUALFEAS     1<<3
    00321 #define ladDUALCHK      1<<4
    00322 #define ladDFQUIET      1<<5
    00323 #define ladDUALS        1<<6
    00324 #define ladPRIMALS      1<<7
    00325 #define ladFACTOR       1<<8
    00326 #define ladEXPAND       1<<9
    00327
    00328
    00329
    00330 /*
    00331   Variable status codes
    00332
    00333   dylp keeps explicit status for both basic and nonbasic variables. These are
    00334   set up as flags so that it's easy to test when more than one status will do
    00335   for a particular action.
    00336
    00337   vstatBFX      basic, fixed
    00338   vstatBUUB     basic, above upper bound
    00339   vstatBUB      basic, at upper bound
    00340   vstatB        basic, strictly between bounds (a well-behaved basic variable)
    00341   vstatBLB      basic, at lower bound
    00342   vstatBLLB     basic, below lower bound
    00343   vstatBFR      basic, free (unbounded)
    00344
    00345   vstatNBFX     nonbasic, fixed
    00346   vstatNBUB     nonbasic at upper bound
    00347   vstatNBLB     nonbasic at lower bound
    00348   vstatNBFR     nonbasic free
    00349
    00350   vstatSB       superbasic, within bounds
    00351
    00352   dylp ensures that superbasic variables are, in fact, always strictly within
    00353   bounds.
    00354
    00355   Inactive NBFR variables can be created at startup if dylp is working with a
    00356   partial system and there are free variables that are not selected to be in
    00357   the initial basis. If the client is forcing a full system, these will be
    00358   active NBFR variables.  Error recovery may also create active NBFR
    00359   variables. By convention, NBFR variables always have a value of zero.
    00360
    00361   Inactive SB variables should not occur. SB status occurs only as the result
    00362   of error recovery and is only valid in primal simplex.
    00363
    00364   The value of SB variables is lost when they are reported out as part of a
    00365   solution. This will only happen if dylp could not find an optimal solution.
    00366
    00367   The following qualifiers can be added to the status:
    00368
    00369   vstatNOPIVOT  Prevents the variable from being considered as a candidate
    00370                 for pivoting; used by the pivot rejection machinery.
    00371   vstatNOPER    Prevents the variable from being perturbed during the
    00372                 formation of a restricted subproblem.
    00373   vstatNOLOAD   Prevents the variable from being considered for activation;
    00374                 used by startup and variable activation/deactivation routines.
    00375 */
    00376
    00377 #define vstatINV     0
    00378 #define vstatBFX  1<<0
    00379 #define vstatBUB  1<<1
    00380 #define vstatB    1<<2
    00381 #define vstatBLB  1<<3
    00382 #define vstatBFR  1<<4
    00383 #define vstatNBFX 1<<5
    00384 #define vstatNBUB 1<<6
    00385 #define vstatNBLB 1<<7
    00386 #define vstatNBFR 1<<8
    00387 #define vstatSB   1<<9
    00388 #define vstatBUUB  1<<10
    00389 #define vstatBLLB  1<<11
    00390
    00391 /*
    00392   TAKE NOTE: Do not use the msb as a qualifier! The status value, with or
    00393   without qualifiers, must be a positive value when cast to a signed integer.
    00394 */
    00395
    00396 #define vstatNOPIVOT ((flags) 1<<(sizeof(flags)*8-2))
    00397 #define vstatNOPER ((flags) 1<<(sizeof(flags)*8-3))
    00398 #define vstatNOLOAD ((flags) 1<<(sizeof(flags)*8-4))
    00399
    00400 #define vstatBASIC \
    00401         (vstatBFX|vstatBUUB|vstatBUB|vstatB|vstatBLB|vstatBLLB|vstatBFR)
    00402 #define vstatNONBASIC (vstatNBFX|vstatNBUB|vstatNBLB)
    00403 #define vstatEXOTIC (vstatSB|vstatNBFR)
    00404
    00405 #define vstatSTATUS (vstatBASIC|vstatNONBASIC|vstatEXOTIC)
    00406 #define vstatQUALS (vstatNOPIVOT|vstatNOPER|vstatNOLOAD)
    00407
    00408 /*
    00409   This macro checks (in a simplistic way) that its parameter encodes one and
    00410   only one status.  It's intended for mild error checking.  See
    00411   dylp_utils:dy_chkstatus if you're really feeling paranoid.
    00412 */
    00413
    00414 #define VALID_STATUS(zz_status_zz) \
    00415   (zz_status_zz == vstatBFX || zz_status_zz == vstatBUB || \
    00416    zz_status_zz == vstatB   || zz_status_zz == vstatBLB || \
    00417    zz_status_zz == vstatBFR || \
    00418    zz_status_zz == vstatNBFX || zz_status_zz == vstatNBUB || \
    00419    zz_status_zz == vstatNBLB || zz_status_zz == vstatNBFR || \
    00420    zz_status_zz == vstatSB)
    00421
    00422
    00423
    00424 /*
    00425   Interface structures: lpprob_struct, lptols_struct, lpopts_struct
    00426 */
    00427
    00428 /*
    00429   basis_struct
    00430
    00431   This structure is used to describe a basis to dylp, and to return the
    00432   final basis at termination. The size of the basis depends on the
    00433   number of active constraints, which will be a subset of the constraints
    00434   in the system.
    00435
    00436   The constraint system as supplied to dylp should not have logical variables
    00437   (dylp will create them automatically). This presents a problem if the final
    00438   basis contains basic logical variables. In this case, vndx is set to the
    00439   negative of the index of the constraint which spawned the logical. This
    00440   same technique can be used on input to, for example, specify the traditional
    00441   all-logical starting basis.
    00442
    00443   Field         Definition
    00444   -----         ----------
    00445   len           The number of rows in the basis.
    00446   el.cndx       Index of the constraint in this basis position.
    00447   el.vndx       Index of the variable in this basis position.
    00448
    00449 */
    00450
    00451 typedef struct { int cndx ; int vndx ; } basisel_struct ;
    00452
    00453 typedef struct
    00454 { int len ;
    00455   basisel_struct *el ; } basis_struct ;
    00456
    00457
    00458 /*
    00459   LP problem control and status flags
    00460
    00461   lpctlNOFREE           (i) Prevents dylp from freeing the problem structures,
    00462                             in anticipation of a subsequent hot start. If dylp
    00463                             exits with a state that is not suitable for hot
    00464                             start, this flag is ignored and the problem data
    00465                             structures are released.
    00466   lpctlONLYFREE         (i) In conjunction with an initial phase of dyDONE,
    00467                             causes dylp to do nothing except free the problem
    00468                             data structure and return.
    00469   lpctlUBNDCHG          (i) Indicates that the variable upper bounds (vub) have
    00470                             been changed.
    00471   lpctlLBNDCHG          (i) Indicates that the variable lower bounds (lub) have
    00472                             been changed.
    00473   lpctlRHSCHG           (i) Indicates that the right-hand side (rhs) has been
    00474                             changed. Includes the rhslow vector (if it exists).
    00475   lpctlOBJCHG           (i) Indicates that the objective (obj) has been changed.
    00476   lpctlACTVARSIN        (i) Indicates that a valid active variable vector has
    00477                             been supplied.
    00478   lpctlINITACTVAR       (i) Forces dylp to perform variable activation before
    00479                             beginning simplex iterations.
    00480   lpctlINITACTCON       (i) Forces dylp to perform constraint activation before
    00481                             beginning simplex iterations. (If variable
    00482                             activation is also requested, constraint activation
    00483                             occurs first.)
    00484
    00485   lpctlACTVARSOUT       (i) Indicates that an active variable vector is to be
    00486                             returned.
    00487                         (o) Indicates that a valid active variable vector has
    00488                             been returned.
    00489
    00490   lpctlDYVALID          (o) Indicates that dylp exited in a state which can
    00491                             be restarted with a hot start.
    00492
    00493 */
    00494
    00495 #define lpctlNOFREE     1<<0
    00496 #define lpctlONLYFREE   1<<1
    00497 #define lpctlUBNDCHG    1<<2
    00498 #define lpctlLBNDCHG    1<<3
    00499 #define lpctlRHSCHG     1<<4
    00500 #define lpctlOBJCHG     1<<5
    00501 #define lpctlACTVARSIN  1<<6
    00502 #define lpctlINITACTVAR 1<<7
    00503 #define lpctlINITACTCON 1<<8
    00504
    00505 #define lpctlACTVARSOUT 1<<10
    00506
    00507 #define lpctlDYVALID    1<<11
    00508
    00509 /*
    00510   lpprob_struct
    00511
    00512   This structure is used to pass an LP problem into dylp and convey the
    00513   results back to the client. The allocated size indicated in colsze and
    00514   rowsze is assumed to be accurate.  If basis, status, x, or y are NULL, they
    00515   will be allocated as needed. If they are non-NULL, dylp will reallocate
    00516   them if necessary (i.e., when the actual size of the lp exceeds the
    00517   allocated size of the vectors).
    00518
    00519   The status vector has the following coding:
    00520     * for nonbasic variables, the normal dylp status flags are used;
    00521     * for basic variables, the negative of the basis index is used.
    00522
    00523   There is one unavoidable problem with this scheme -- the status vector
    00524   provides the only information about the value of nonbasic variables. This
    00525   is adequate for all but superbasic variables and nonbasic free variables
    00526   which are not at zero. Both of these cases are transient anomalies, created
    00527   only when the basis package is forced to patch a singular basis, and they
    00528   should not persist in the final solution when an optimal solution is found
    00529   or when the problem is infeasible.  They may, however, occur in the
    00530   solution reported for an unbounded problem if the unbounded condition is
    00531   discovered before the nonbasic free or superbasic variable is chosen for
    00532   pivoting.  On input, nonbasic free variables are assumed to take the value
    00533   0, and specifying a superbasic variable is illegal.
    00534
    00535   Field         Definition
    00536   -----         ----------
    00537   owner         ID of the owner of this problem.
    00538   ctlopts       Control and status flags.
    00539   phase         (i) If set to dyDONE, dylp will free any retained data
    00540                     structures and return. Any other value is ignored.
    00541                 (o) Termination phase of the dynamic simplex algorithm;
    00542                     should be dyDONE unless something screws up, in which
    00543                     case it'll be dyINV.
    00544   lpret         Return code from the simplex routine.
    00545   obj           For lpOPTIMAL, the value of the objective function.
    00546                 For lpINFEAS, the total infeasibility.
    00547                 For lpUNBOUNDED, the index of the unbounded variable, negated
    00548                   if the variable can decrease without bound, positive if it
    00549                   can increase without bound. The logical for constraint i
    00550                   is represented as n+i.
    00551                 Otherwise, undefined.
    00552   iters         The number of simplex iterations.
    00553   consys        The constraint system.
    00554   fullsys       True if the active constraint system is the full system, false
    00555                 otherwise.
    00556   basis         (i) Initial basis.
    00557                 (o) Final basis.
    00558   status        (i) Initial status vector.
    00559                 (o) Final status vector.
    00560   x             (i) No values used, but a vector can be supplied.
    00561                 (o) The values of the basic variables (indexed by basis
    00562                     position).
    00563   y             (i) No values used, but a vector can be supplied.
    00564                 (o) The values of the dual variables (indexed by basis
    00565                     position).
    00566   actvars       There is one entry for each variable, coded TRUE if the
    00567                 variable is active, FALSE otherwise. The vector supplied on
    00568                 input will be overwritten on output.
    00569                 (i) Variables to be activated at startup. Used only for a
    00570                     warm start. Validity is indicated by the lpctlACTVARSIN
    00571                     flag. A vector can be supplied strictly for output use.
    00572                 (o) The current active variables. Will be returned only if
    00573                     requested by the lpctlACTVARSOUT flag. If the vector is
    00574                     valid on return, lpctlACTVARSOUT will remain set,
    00575                     otherwise it will be reset.
    00576
    00577   colsze        Allocated column capacity (length of status vector).
    00578   rowsze        Allocated row capacity (length of basis, x, and y vectors).
    00579
    00580
    00581   Note that dylp will reallocate status, basis->el, actvars, x, and y, if the
    00582   vectors supplied at startup are too small to report the solution. Don't set
    00583   colsze or rowsze to nonzero values without actually allocating space.
    00584 */
    00585
    00586 typedef struct
    00587 { void *owner ;
    00588   flags ctlopts ;
    00589   dyphase_enum phase ;
    00590   lpret_enum lpret ;
    00591   double obj ;
    00592   int iters ;
    00593   consys_struct *consys ;
    00594   bool fullsys ;
    00595   basis_struct *basis ;
    00596   flags *status ;
    00597   double *x ;
    00598   double *y ;
    00599   bool *actvars ;
    00600   int colsze ;
    00601   int rowsze ; } lpprob_struct ;
    00602
    00603
    00604
    00605 /*
    00606   lptols_struct
    00607
    00608   This structure contains phase and tolerance information for the lp algorithm.
    00609
    00610   The philosophy with respect to the separate zero and feasibility tolerances
    00611   for primal and dual variables is that dylp uses the zero tolerance when
    00612   calculating primal or dual variables, and the feasibility tolerance when
    00613   checking for feasibility. This allows us to keep small values for accuracy
    00614   in computation, but not be so fussy when it comes to feasibility.
    00615
    00616   Field         Definition
    00617   -----         ----------
    00618   inf           Infinity. dylp uses IEEE FP infinity, but be careful not to
    00619                 pass it to the basis package.
    00620   zero          Zero tolerance for primal variables, and also the generic
    00621                 zero tolerance for constraint coefficients, right-hand-side
    00622                 values, etc.
    00623   pchk          Primal accuracy check tolerance.
    00624   pfeas         Primal feasibility check tolerance; dynamically scaled from
    00625                 zero in proportion to the 1-norm of the primal basic variables.
    00626   pfeas_scale   Primal feasibility check tolerance multiplier. This provides
    00627                 some user-controllable decoupling of zero and pfeas.
    00628   cost          Base zero tolerance for checks involving objective function
    00629                 coefficients, reduced costs, and related values.
    00630   dchk          Dual accuracy check tolerance. Also used by dy_duenna to
    00631                 test for improvement in the objective.
    00632   dfeas         Dual feasbility check tolerance; dynamically scaled from cost
    00633                 in proportion to the 1-norm of the dual variables. Acts as the
    00634                 zero tolerance for reduced costs.
    00635   dfeas_scale   Dual feasibility check tolerance multiplier. This provides
    00636                 some user-controllable decoupling of cost and dfeas.
    00637   pivot         Simplex pivot selection tolerance, expressed as a multiplier
    00638                 for the pivot selection tolerance used by the basis package
    00639                 when factoring the basis. (I.e., the actual pivot selection
    00640                 criteria will be to accept a simplex pivot a<i,j> if
    00641                 |a<i,j>| > lptols.pivot*basis.pivot*MAX{i}|a<i,j>|.)
    00642   bogus         Multiplier used to identify 'bogus' values, in the range
    00643                 tol < |val| < bogus*tol for the appropriate tolerance.
    00644   swing         Ratio used to identify excessive growth in primal variables
    00645                 (pseudo-unboundedness).
    00646   toobig        Absolute value of primal variables which will cause dual
    00647                 multipivoting to consider primal infeasibility when selecting
    00648                 a flip/pivot sequence.
    00649   purge         Percentage change in objective function required before
    00650                 constraint or variable purging is attempted.
    00651   purgevar      Percentage of maximum reduced cost used to determine the
    00652                 variable purge threshold; nonbasic architectural variables
    00653                 at their optimum bound whose reduced cost exceeds
    00654                 purgevar*MAX{j}cbar<j> are purged.
    00655
    00656   reframe       Multiplier used to trigger a reference framework reset in
    00657                 PSE pricing; reset occurs if
    00658                   |gamma<j> - ||abar<j>||^2| > reframe*||abar<j>||^2.
    00659                 The check is made in pseupdate.
    00660                 Also used to trigger recalculation of the basis inverse row
    00661                 norms used in DSE pricing; reset occurs if
    00662                   |rho<i> - ||beta<i>||^2| > reframe*||beta<i>||^2.
    00663                 The check is made in dseupdate.
    00664 */
    00665
    00666 typedef struct
    00667 { double inf ;
    00668   double zero ;
    00669   double pchk ;
    00670   double pfeas ;
    00671   double pfeas_scale ;
    00672   double cost ;
    00673   double dchk ;
    00674   double dfeas ;
    00675   double dfeas_scale ;
    00676   double pivot ;
    00677   double bogus ;
    00678   double swing ;
    00679   double toobig ;
    00680   double purge ;
    00681   double purgevar ;
    00682   double reframe ; } lptols_struct ;
    00683
    00684 #if defined(DYLP_INTERNAL) || defined(BONSAIG)
    00685 /*
    00686   A few handy macros for testing values against tolerances.
    00687 */
    00688 #ifdef DYLP_INTERNAL
    00689 #  ifdef BND_TOLER
    00690 #    undef BND_TOLER
    00691 #  endif
    00692 #  define BND_TOLER dy_tols->pfeas
    00693 #  ifdef INF_TOLER
    00694 #    undef INF_TOLER
    00695 #  endif
    00696 #  define INF_TOLER dy_tols->inf
    00697 #endif
    00698
    00699 #define withintol(zz_val_zz,zz_tgt_zz,zz_tol_zz) \
    00700   (fabs((zz_val_zz)-(zz_tgt_zz)) <= zz_tol_zz)
    00701
    00702 #define setcleanzero(zz_val_zz,zz_tol_zz) \
    00703   if (fabs(zz_val_zz) < zz_tol_zz) zz_val_zz = 0
    00704
    00705 #define atbnd(zz_val_zz,zz_bnd_zz) \
    00706   ((fabs(zz_bnd_zz) < INF_TOLER) && \
    00707    (fabs((zz_val_zz)-(zz_bnd_zz)) < BND_TOLER*(1.0+fabs(zz_bnd_zz))))
    00708
    00709 #define belowbnd(zz_val_zz,zz_bnd_zz) \
    00710   ((fabs(zz_bnd_zz) < INF_TOLER) ? \
    00711    (((zz_bnd_zz)-(zz_val_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
    00712    (zz_val_zz < zz_bnd_zz))
    00713
    00714 #define abovebnd(zz_val_zz,zz_bnd_zz) \
    00715   ((fabs(zz_bnd_zz) < INF_TOLER) ? \
    00716    (((zz_val_zz)-(zz_bnd_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
    00717    (zz_val_zz > zz_bnd_zz))
    00718
    00719 #define withinbnds(zz_lb_zz,zz_val_zz,zz_ub_zz) \
    00720   (!abovebnd(zz_val_zz,zz_ub_zz) && !belowbnd(zz_val_zz,zz_lb_zz))
    00721
    00722 #endif /* DYLP_INTERNAL || BONSAIG */
    00723
    00724 #ifdef DYLP_INTERNAL
    00725 /*
    00726   Finally, a macro to decide if we should snap to a value. The notion here is
    00727   that the accuracy with which one can hit a target value depends on both the
    00728   magnitude of the target and the distance travelled to get there. On a
    00729   64-bit machine, IEEE FP has about 15 decimal digits of accuracy. For
    00730   example, if we're travelling 1.0e7 and trying to hit zero, we only have 8
    00731   decimal places of accuracy remaining. If we're within 1.0e-8, might as well
    00732   snap to 0. In practice, there's already a bit of roundoff in any nontrivial
    00733   calculation, so we start with the zero tolerance and scale from there.
    00734
    00735   In some cases, we only know the target, so the best we can do is
    00736   scale to it.
    00737
    00738   The utility of this idea is highly questionable.
    00739 */
    00740
    00741 #define snaptol1(zz_tgt_zz) (dy_tols->zero*(1.0+(zz_tgt_zz)))
    00742
    00743 #define snaptol2(zz_tgt_zz,zz_dst_zz) \
    00744   (dy_tols->zero*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
    00745
    00746 #define snaptol3(zz_tol_zz,zz_tgt_zz,zz_dst_zz) \
    00747   ((zz_tol_zz)*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
    00748
    00749 #endif /* DYLP_INTERNAL */
    00750
    00751
    00752
    00753 /*
    00754   Enum for initial basis type.
    00755
    00756   This determines the criteria used to select the initial set of basic
    00757   variables during a cold start.
    00758
    00759   ibINV         invalid
    00760   ibLOGICAL     Use only logical (slack and artificial) variables
    00761   ibSLACK       Use slack variables for inequalities. Prefer architectural
    00762                 over artificial variables for equalities.
    00763   ibARCH        Prefer architectural variables over logical variables.
    00764 */
    00765
    00766 typedef enum { ibINV = 0, ibLOGICAL, ibSLACK, ibARCH } ibtype_enum ;
    00767
    00768 /*
    00769   Enum for calling context.
    00770
    00771   As dylp evolves, it has proven useful to know the context of the
    00772   call. Consider this a work in progress. The default context is INITIALLP.
    00773
    00774   cxINV         invalid (context is unknown)
    00775   cxLOAD        This call is only to (re)load data structures. Returns after
    00776                 one iteration of dual or primal simplex, but shows problem
    00777                 status rather than lpITERLIM.
    00778   cxUNLOAD      This call is solely for the purpose of freeing the problem
    00779                 data structures. (Replaces dyDONE/lpctlONLYFREE hack.)
    00780   cxSINGLELP    This is a one-off call to solve a single LP from scratch.
    00781   cxINITIALLP   This is a call to solve a single LP from scratch, but will
    00782                 likely be followed by calls to reoptimise.
    00783   cxBANDC       This call is made in the context of a branch-and-cut
    00784                 algorithm.
    00785   cxUSERPIV     This call is in the context of user control of pivoting.
    00786 */
    00787
    00788 typedef enum { cxINV = 0, cxLOAD, cxUNLOAD,
    00789                cxSINGLELP, cxINITIALLP, cxBANDC, cxUSERPIV } cxtype_enum ;
    00790
    00791
    00792 /*
    00793   lpopts_struct
    00794
    00795   This structure is used to pass option settings to dylp. Default values are
    00796   declared at the beginning of dy_setup.c.
    00797
    00798   Field         Definition
    00799   -----         ----------
    00800   context       The context in which dylp is being called. See comments
    00801                 above for cxtype_enum.
    00802   forcecold     TRUE to force a cold start, FALSE otherwise. If set to TRUE,
    00803                 dominates warm and hot start.
    00804   forcewarm     TRUE to force a warm start, FALSE otherwise. If set to TRUE,
    00805                 dominates hot start.
    00806   fullsys       Forces the use of the full constraint system at all times. The
    00807                 full constraint system is loaded on startup, and all constraint
    00808                 and variable deactivation/activation is skipped. (But see the
    00809                 finpurge option below.) (Also, this will not prevent dylp
    00810                 from resorting to forced phase transitions, which typically
    00811                 involve deactivation of constraints or variables. Arguably
    00812                 this is a bad thing, and may change in the future.)
    00813   active        Used to estimate the initial size of the dylp constraint
    00814                 system relative to the original system.
    00815     vars          Fraction of original variables expected to be active at
    00816                   any time.
    00817     cons          Fraction of original inequalities expected to be active at
    00818                   any time.
    00819   initcons      Specifies how inequalities will be selected to initialize the
    00820                 active system. See extensive comments in dy_coldstart.c.
    00821     frac          Fraction of inequalities to be used.
    00822     i1l           Lower bound on angle to objective, first interval
    00823     i1lopen       TRUE if the bound is open.
    00824     i1u           Upper bound on angle to objective, first interval
    00825     i1uopen       TRUE if the bound is open.
    00826     i2valid       TRUE if the second interval is specified
    00827     i2l           Lower bound on angle to objective, second interval
    00828     i2lopen       TRUE if the bound is open.
    00829     i2u           Upper bound on angle to objective, second interval
    00830     i2uopen       TRUE if the bound is open.
    00831   coldbasis     Code specifying the kind of basis built for a cold start. See
    00832                 comments for ibtype_enum and comments in dy_coldstart.c
    00833   finpurge      Controls whether dylp does a final deactivation of constraints
    00834                 and/or variables. This will occur only an optimal solution is
    00835                 found, and is not suppressed by fullsys.
    00836     cons          TRUE to purge constraints
    00837     vars          TRUE to purge variables
    00838   heroics       Controls behaviour during forced primal <-> dual transitions
    00839     d2p           TRUE to allow deactivation of basic architecturals, FALSE
    00840                   to disallow. FALSE is recommended, and the default.
    00841     p2d           TRUE to allow deactivation of tight constraints, FALSE
    00842                   to disallow. FALSE is recommended, and the default.
    00843     flip          TRUE to allow flips to regain dual feasibility, FALSE to
    00844                   disallow. Tends to cycle; default is false.
    00845   coldvars      If the number of active variables exceeds this value after
    00846                 a cold start, dylp will attempt to purge variables prior to
    00847                 the initial primal simplex run.
    00848   con           Options related to constraint activation/deactivation
    00849     actlvl        The constraint activation strategy
    00850                     0: (strict) activate violated constraints,
    00851                        lhs < rhslow or lhs > rhs
    00852                     1: (tight) activate tight or violated constraints,
    00853                        lhs <= rhslow or lhs >= rhs
    00854     actlim        If non-zero, limits the number of constraints that can be
    00855                   activated in any one call to a constraint activation
    00856                   routine.
    00857     deactlvl    The constraint deactivation strategy:
    00858                   0: (normal) deactivate only inequalities i which are
    00859                      strictly loose (i.e., slk<i> basic, not at bound).
    00860                   1: (aggressive) normal plus inequalities which are tight
    00861                      with y<i> = 0.
    00862                   2: (fanatic) aggressive plus equalities with y<i> = 0
    00863   usedual       TRUE if dual phase II is to be used to regain feasibility after
    00864                 adding constraints, FALSE to force use of primal phase I.
    00865   addvar        If non-zero, at most this many variables will be added in
    00866                 any one pass through phase dyADDVAR.
    00867   dualadd       Controls the types of activation allowed when adding variables
    00868                 during dual simplex.
    00869                   0:    variable activation is disallowed
    00870                   1:    type 1 activation (variables that will be dual feasible
    00871                         when activated into the nonbasic partition)
    00872                   2:    type 2 activation (variables which can be activated
    00873                         if immediately pivoted into the basis)
    00874                   3:    type 3 activation (activate with bound-to-bound pivot)
    00875                 See dy_dualaddvars for more extensive comments.
    00876   scan          Partial pricing parameter. Controls the number of columns to
    00877                 be scanned for a new candidate entering variable when the
    00878                 candidate selected during PSE update is rejected.
    00879   iterlim       The per phase pivot limit for the code; if set to 0, no
    00880                 limit is enforced.
    00881   idlelim       The number of iterations without change in the objective
    00882                 function before the code declares the problem is stalled or
    00883                 cycling.
    00884   dpsel         Options to control dual pivoting. Selection of the leaving
    00885                 variable is always handled by DSE.
    00886     strat:        The strategy used to select the entering variable:
    00887                     0: standard ratio test; may use anti-degen lite
    00888                     1: multipivoting, selecting for maximum dual objective
    00889                        improvement.
    00890                     2: multipivoting, select for minimum predicted
    00891                        infeasibility.
    00892                     3: multipivoting, select infeasibility reduction if
    00893                        possible, otherwise maximum dual objective improvement.
    00894     flex          If TRUE, dylp will switch between strategies 1 and 3, using
    00895                   strategy 1 unless primal magnitudes become too large.
    00896     allownopiv    If TRUE, sequences of flips with no finishing pivot will be
    00897                   allowed. Defaults to false, very prone to cycling.
    00898   ppsel         Options to control primal pivoting. Selection of the entering
    00899                 variable is always handled by PSE.
    00900     strat:        The strategy used to select the leaving variable:
    00901                     0: standard ratio test; may use anti-degen lite
    00902                     1: multipivoting
    00903   factor        The LP basis will be refactored every factor iterations, in
    00904                 the absence of some compelling reason (typically error
    00905                 recovery) that forces it to occur sooner.
    00906   check         An accuracy check will be forced every check iterations, in
    00907                 the absence of some compelling reason to do it earlier.
    00908   groom         Controls the action taken by the basis grooming routine
    00909                 when it makes a nontrivial status correction:
    00910                   0:    catatonic
    00911                   1:    issue a warning
    00912                   2:    issue an error message and force an abort
    00913                 Numeric codes should match keywords in dy_options.c:dy_ctlopt.
    00914   degen         TRUE to allow creation of restricted subproblems to deal with
    00915                 degeneracy, FALSE to disallow it.
    00916   degenpivlim   The number of successive degenerate pivots required before
    00917                 creating a restricted subproblem.
    00918   degenlite     Controls secondary antidegeneracy --- `antidegen lite'
    00919                   0: (pivotabort) break ties using |abar<kj>| and abort when
    00920                      delta<j> = 0
    00921                   1: (pivot) break ties using |abar<kj>| but always scan the
    00922                      full basis
    00923                   2: (alignobj) break ties by examining the alignment of the
    00924                      hyperplane which will become tight on the pivot; choose
    00925                      so that movement in the direction of the objective most
    00926                      nearly lies in the hyperplane
    00927                   3: (alignedge) break ties by examining the alignment of the
    00928                      hyperplane which will become tight on the pivot; choose
    00929                      so that the direction of motion defined by the entering
    00930                      variable most nearly lies in the hyperplane.
    00931                   4: (perpobj) break ties by examining the alignment of the
    00932                      hyperplane which will become tight on the pivot; choose
    00933                      so that the normal of the hyperplane is most nearly
    00934                      aligned with the normal of the objective
    00935                   5: (perpedge) break ties by examining the alignment of the
    00936                      hyperplane which will become tight on the pivot; choose
    00937                      so that the normal of the hyperplane is most nearly
    00938                      aligned with the direction of motion
    00939                 Numeric codes should match keywords in dy_options.c:dy_ctlopt.
    00940   patch         TRUE to allow the code to patch a singular basis, FALSE to
    00941                 prevent patching.
    00942   copyorigsys   Controls whether dylp makes a local copy of the original
    00943                 system. If set to TRUE, dylp will always make a local copy.
    00944                 If set to FALSE, a copy will be made only if necessary.
    00945                 Scaling will trigger a local copy.
    00946   scaling       Controls whether dylp attempts to scale the original constraint
    00947                 system for numeric stability.
    00948                   0: scaling is forbidden
    00949                   1: scale the original constraint system using numeric
    00950                      scaling vectors attached to the system
    00951                   2: evaluate the original constraint system and scale it if
    00952                      necessary
    00953                 Note that even if scaling = 0, dylp may install +/-1.0 scaling
    00954                 vectors in order to flip >= constraints to <= constraints. See
    00955                 comments in dy_scaling.c
    00956   print         Substructure for picky printing control. For all print options,
    00957                 a value of 0 suppresses all information messages.
    00958     major         Controls printing of major phase information.
    00959                   1: a message at each phase transition.
    00960     scaling       Controls print level during initial evaluation and scaling of
    00961                   the original constraint system.
    00962                   1: start and finish messages
    00963                   2: stability measures for original and scaled matrices;
    00964                      adjustments to tolerances.
    00965     setup         Controls print level while creating the initial constraint
    00966                   system for dylp.
    00967                   1: start and finish messages.
    00968                   2: summary information about activated constraints
    00969                   3: messages about each constraint included in the initial
    00970                      system.
    00971                   4: messages about each constraint processed for the initial
    00972                      system
    00973                   5: messages about each variable included in the initial
    00974                      system.
    00975                   6: lists value and status of inactive variables with
    00976                      nonzero values
    00977     crash         Controls print level while crashing the basis.
    00978                   1: start & finish messages
    00979                   2: summary counts for logicals, architecturals, artificials
    00980                   3: a dump of the completed basis
    00981                   4: detailed info on the selection of each architectural
    00982                      and artificial variable
    00983     pricing       Controls print level for pricing of columns (rows) in primal
    00984                   (dual) simplex.
    00985                   1: summary messages
    00986                   2: lists candidate list and primal variable selected for
    00987                      entry (exit) at each pivot
    00988                   3: lists each variable as it's added to the candidate list
    00989                      and again when reconsidered for pivoting
    00990     pivoting      Controls print level for selection of the leaving (entering)
    00991                   primal variable in primal (dual) simplex and updating of
    00992                   variables.
    00993                   1: prints result of leaving (entering) variable selection
    00994                   2: information about the selection of the leaving (entering)
    00995                      variable.
    00996                   3: more information about the selection of the leaving
    00997                      (entering) variable.
    00998                   4: prints the pivot column (row) before and after
    00999                      multiplication by the basis inverse, and yet more
    01000                      pivot selection information.
    01001                   5: prints a line for every candidate evaluated
    01002     pivreject     Controls print level for information related to the operation
    01003                   of the pivot rejection mechanism.
    01004                   1: Prints a message for each row/column added to the pivot
    01005                      rejection list, plus other major events.
    01006                   2: Prints a message for each row/column removed from the
    01007                      pivot rejection list.
    01008     degen         Controls print level for information related to the operation
    01009                   of the antidegeneracy mechanism.
    01010                   1: prints a message each time the antidegeneracy level
    01011                      changes
    01012                   2: prints a message when a true degenerate pivot is taken
    01013                      under duress
    01014                   3: prints a message when a degenerate pivot is taken
    01015                   4: prints anomalies as each degenerate set is formed and
    01016                      backed out
    01017                   5: prints details of each degenerate set as it's formed and
    01018                      backed out
    01019     phase1        Controls general print level for phase 1 of primal simplex.
    01020                   1: messages about extraordinary events -- problem pivots, etc.
    01021                   2: messages about 'routine' but infrequent events --
    01022                      termination conditions, refactoring, unboundedness, etc.
    01023                   3: messages with additional details of problems encountered
    01024                   4: a one line log message is printed for each pivot
    01025                   5: summary information about infeasible variables and phase
    01026                      I objective coefficients; information about primal
    01027                      variables updated at each pivot.
    01028                   6: prints the primal variables after each pivot; prints
    01029                      infeasible variables during phase I objective construction
    01030                   7: prints the dual variables after each pivot; prints
    01031                      infeasible variables during phase I objective modification
    01032     phase2        Controls general print level for phase 1 of primal simplex.
    01033                   1: messages about extraordinary events -- problem pivots, etc.
    01034                   2: messages about 'routine' but infrequent events --
    01035                      termination conditions, refactoring, unboundedness, etc.
    01036                   3: messages with additional details of problems encountered
    01037                   4: a one line log message is printed for each pivot
    01038                   5: prints the updated basic primal variables after each pivot
    01039                   6: prints all basic primal variables after each pivot
    01040                   7: prints the dual variables after each pivot.
    01041     dual          Controls general print level for the dual simplex. As
    01042                   phase2.
    01043     basis         Controls print level in routines working with the basis.
    01044                   1: summary warnings about problems: empty rows, singularity,
    01045                      numerical instability, etc.
    01046                   2: information about factoring failures and recovery actions
    01047                   3: warnings about individual empty rows, details of column
    01048                      replacement when patching a singular basis, pivot
    01049                      tolerance adjustments; information about pivoting failures
    01050                      and recovery actions
    01051                   4: basis stability after factoring
    01052                   5: basis stability after pivoting
    01053     conmgmt       Controls print level while dylp is in the purge/generate/
    01054                   activate constraint phases.
    01055                   1: prints the number of constraints purged, generated,
    01056                      & activated, and new size of constraint system.
    01057                   2: prints a message for each constraint purged or activated.
    01058                      (The cut generation routine is responsible for
    01059                      handling this function when it generates cuts.)
    01060                   3: additional details about refactoring and new values
    01061                      of primal and dual variables.
    01062                   4: prints a message about any variables affected as a side
    01063                      effect of constraint changes, constraints processed
    01064                      but not activated, and information about direction of
    01065                      recession and relative angle of constraints when adding
    01066                      constraints to an unbounded problem.
    01067                   5: prints a running commentary on constraint and variable
    01068                      shifts, inactive variables.
    01069     varmgmt       Controls print level while dylp is in the purge/generate/
    01070                   activate variable phases.
    01071                   1: prints the number of variables purged, generated,
    01072                      & activated, and new size of constraint system.
    01073                   2: prints a message for each variable purged & activated.
    01074                      (The column generation routine is responsible for
    01075                      handling this function when it generates new variables).
    01076                   3: prints a message about any constraints affected as a side
    01077                      effect of variable changes, variables processed but not
    01078                      activated, and information about direction of recession
    01079                      and relative angle of dual constraints when adding
    01080                      variables to an unbounded dual.
    01081                   4: prints a running commentary on constraint and variable
    01082                      shifts.
    01083     force         Controls print level when dylp is attempting to force a
    01084                   transition (primal -> dual, dual -> primal) or force the
    01085                   use of the full constraint system.
    01086                   1: prints a summary message giving the result of the
    01087                      transition attempt
    01088                   2: prints messages about actions taken for individual
    01089                      constraints and variables.
    01090                   3: additional information about variables and constraints
    01091                      examined.
    01092     tableau       Controls print level for routines that generate tableau
    01093                   vectors (beta<i>, beta<j>, abar<i>, abar<j>) for use by
    01094                   external clients.
    01095                   1: prints summary messages about the circumstances
    01096                   4: prints nonzeros in the final vector.
    01097                   5: prints nonzeros in intermediate vectors and (dy_betaj,
    01098                      dy_abarj only) inactive rows
    01099                   6: prints nonzeros of active portion in internal reference
    01100                      frame (dy_betaj only)
    01101     rays          Controls print level for routines that generate primal
    01102                   and dual rays for use by external clients.
    01103                   1: prints summary messages about vectors found.
    01104                   3: print information about columns / rows examined.
    01105                   4: print information about why a column or row was rejected.
    01106                   5: print nonzeros for each ray
    01107     soln          Controls print level for routines that generate primal and
    01108                   dual solutions for use by external clients.
    01109                   1: prints summary messages about the circumstances
    01110                   3: prints nonzeros in the final vector
    01111                   4: prints nonzeros in intermediate vectors
    01112 */
    01113
    01114 typedef struct
    01115 { cxtype_enum context ;
    01116   int scan ;
    01117   int iterlim ;
    01118   int idlelim ;
    01119   struct { int strat ;
    01120            bool flex ;
    01121            bool allownopiv ; } dpsel ;
    01122   struct { int strat ; } ppsel ;
    01123   int factor ;
    01124   int check ;
    01125   int groom ;
    01126   struct { int actlvl ;
    01127            int actlim ;
    01128            int deactlvl ; } con ;
    01129   int addvar ;
    01130   int dualadd ;
    01131   int coldvars ;
    01132   bool forcecold ;
    01133   bool forcewarm ;
    01134   bool usedual ;
    01135   bool degen ;
    01136   int degenpivlim ;
    01137   int degenlite ;
    01138   bool patch ;
    01139   bool fullsys ;
    01140   bool copyorigsys ;
    01141   int scaling ;
    01142   struct { float vars ;
    01143            float cons ; } active ;
    01144   struct { double frac ;
    01145            bool i1lopen ;
    01146            double i1l ;
    01147            bool i1uopen ;
    01148            double i1u ;
    01149            bool i2valid ;
    01150            bool i2lopen ;
    01151            double i2l ;
    01152            bool i2uopen ;
    01153            double i2u ; } initcons ;
    01154   ibtype_enum coldbasis ;
    01155   struct { bool cons ;
    01156            bool vars ; } finpurge ;
    01157   struct { bool d2p ;
    01158            bool p2d ;
    01159            bool flips ; } heroics ;
    01160   struct { int major ;
    01161            int scaling ;
    01162            int setup ;
    01163            int crash ;
    01164            int pricing ;
    01165            int pivoting ;
    01166            int pivreject ;
    01167            int degen ;
    01168            int phase1 ;
    01169            int phase2 ;
    01170            int dual ;
    01171            int basis ;
    01172            int conmgmt ;
    01173            int varmgmt ;
    01174            int force ;
    01175            int tableau ;
    01176            int rays ;
    01177            int soln ; } print ; } lpopts_struct ;
    01178
    01179
    01180
    01181
    01182   /*
    01183     Statistics structure, used to collect information about aspects of dylp
    01184     operation beyond simple pivot counts. The data structure definition is
    01185     always present, but to fill it you have to define DYLP_STATISTICS.
    01186
    01187     Field               Definition
    01188     -----               ----------
    01189     phasecnts[dyDONE] Array with counts for number of times each phase is
    01190                   executed.
    01191     ini_simplex The initial simplex phase
    01192     cons                A set of arrays with data about individual constraints.
    01193       sze                 Allocated capacity of the arrays.
    01194       angle       Angle to the objective function.
    01195       actcnt      Number of times constraint is activated.
    01196       deactcnt    Number of times constraint is deactivated.
    01197       init        True if constraint is active in initial system.
    01198       fin                 True if constraint is active in final system.
    01199     vars                A set of arrays with data about individual variables.
    01200       sze                 Allocated capacity of the arrays.
    01201       actcnt      Number of times variable is activated.
    01202       deactcnt    Number of times variable is deactivated.
    01203     angle
    01204       max               Maximum angle to the objective function over all constraints.
    01205       min               Minimum angle to the objective function over all constraints.
    01206       hist[*]   Histogram of angles of constraints to the objective function.
    01207                   There are DYSTATS_HISTBINS bins. Currently, 37 bins: 36 bins
    01208                   spanning 5 degrees of angle, and a dedicated 90 degree bin.
    01209
    01210     factor      Tracks how well we're doing with respect to refactoring the
    01211                   basis.
    01212       cnt               Number of time the basis has been refactored.
    01213       prevpiv   Pivot count at last refactorisation.
    01214       avgpivs   Average number of pivots between basis refactorisations.
    01215       maxpivs   Maximum number of pivots between basis refactorisations.
    01216
    01217     pivrej      Statistics about the pivot rejection list and punts.
    01218       max                 maximum number of entries on the pivot rejection list
    01219       mad                 total number of entries attributed to mad pivots
    01220       sing        total number of entries attributed to singular pivots
    01221       pivtol_red          total number of times the pivot tolerance was reduced
    01222       min_pivtol          the minimum pivot tolerance used
    01223       puntcall    total number of calls to dealWithPunt
    01224       puntret     total number of dyrPUNT returns recommended
    01225
    01226     dmulti      Tracks the dual multipivot algorithm. All fields except cnt are
    01227                   totals; divide by cnt to get averages.
    01228       flippable   Number of flippable variables in the constraint system.
    01229       cnt                 Total calls to dualmultiin
    01230       cands       Number of candidates queued for evaluation for entry
    01231       promote     Number of calls that resulted in promoting a sane pivot
    01232                     over an unstable pivot.
    01233       nontrivial          Number of times that the initial scan and sort left
    01234                     multiple candidates for further evaluation.
    01235       evals       Actual number of candidates evaluated (ftran'd column)
    01236       flips       Number of bound-to-bound flips performed
    01237       pivrnk      Index in the list of candidates of the candidate finally
    01238                     selected for pivoting.
    01239       maxrnk      Maximum index selected for pivoting.
    01240
    01241     pmulti      Tracks the primal multipivot algorithm.
    01242       cnt                 Total calls to primalmultiin
    01243       cands       Number of candidates queued for evaluation to leave
    01244       nontrivial          Number of times that the candidate list was sorted
    01245       promote     Number of calls that resulted in promoting a sane pivot
    01246                     over an unstable pivot.
    01247
    01248     infeas      Statistics on resolution of infeasibility in primal phase I.
    01249                   Basically, what we're interested in tracking is the number
    01250                   of infeasible variables and the number of pivots between a
    01251                   change in the number of infeasible variables. We're interested
    01252                   in separating the case of 1 variable from 2 or more, because
    01253                   the latter requires vastly more calculation. A little care
    01254                   is required because phase I can run many times.
    01255
    01256       prevpiv   The pivot count (tot.iters) at the previous change.
    01257       maxcnt    The maximum number of infeasible variables encountered (this
    01258                   is not strictly monotonic, as dylp may enter phase I many
    01259                   times due to activating violated constraints).
    01260       totpivs   The total number of pivots expended in phase I.
    01261       maxpivs   The maximum number of pivots with no change in the number of
    01262                   feasible variables.
    01263       chgcnt1   The number of times that the number of infeasible variables
    01264                   changed and reduced costs did not have to be recalculated
    01265                   (specifically, exactly one variable became feasible, and it
    01266                   left the basis as it did so).
    01267       chgcnt2   The number of times that the number of infeasible variables
    01268                   changed in such a way as to require recalculation of the
    01269                   reduced costs.
    01270
    01271     [dp]degen[*]        Array of stats for each restricted subproblem nesting level,
    01272                   with separate arrays for dual (ddegen) and primal (pdegen).
    01273                   degen[0].cnt is used to hold the maximum nesting level.
    01274       cnt               Number of times this nesting level was entered.
    01275       avgsiz    The average number of variables in a restricted subproblem.
    01276                   Kept by iterative update, as avg<k+1> = (avg<k>*k+size)/(k+1).
    01277                   Suffers from cumulative loss of accuracy, but it'll do for
    01278                   our purposes.
    01279       maxsiz    The maximum number of variables in a restricted subproblem.
    01280       totpivs   Total number of pivots at or above this nesting level.
    01281       avgpivs   Average number of pivots at or above this nesting level.
    01282       maxpivs   Maximum number of pivots for any one instance at or above
    01283                   this nesting level.
    01284
    01285     tot, p1, p2, d2     Iteration and pivot counts, total and for each
    01286                           individual phase. These are copied over from
    01287                           dy_lp (lp_struct) at the end of the run, so that
    01288                           they can be printed by dumpstats.
    01289
    01290     DYSTATS_MAXDEGEN is the maximum number of levels of nesting accommodated by
    01291     antidegeneracy statistics and debugging structures. The actual algorithm
    01292     has no inherent limitation.
    01293
    01294     DYSTATS_HISTBINS is the number of bins for constraint angles. It should be an
    01295     odd number. Each bin will span 180/(DYSTATS_HISTBINS-1) degrees, with the
    01296     final bin reserved for constraints at 90 degrees. For example, a value of 37
    01297     gives 180/(37-1) = 5 degrees per bin.
    01298   */
    01299
    01300   #define DYSTATS_MAXDEGEN 25
    01301   #define DYSTATS_HISTBINS 37
    01302
    01303   typedef struct {
    01304     int phasecnts[dyDONE+1] ;
    01305     dyphase_enum ini_simplex ;
    01306     struct { int sze ;
    01307              double *angle ;
    01308              int *actcnt ;
    01309              int *deactcnt ;
    01310              bool *init ;
    01311              bool *fin ; } cons ;
    01312     struct { int sze ;
    01313              int *actcnt ;
    01314              int *deactcnt ; } vars ;
    01315     struct { float max ;
    01316              float min ;
    01317              int hist[DYSTATS_HISTBINS] ; } angle ;
    01318     struct { int cnt ;
    01319              int prevpiv ;
    01320              float avgpivs ;
    01321              int maxpivs ; } factor ;
    01322     struct { int max ;
    01323              int mad ;
    01324              int sing ;
    01325              int pivtol_red ;
    01326              double min_pivtol ;
    01327              int puntcall ;
    01328              int puntret ; } pivrej ;
    01329     struct { int flippable ;
    01330              int cnt ;
    01331              int cands ;
    01332              int promote ;
    01333              int nontrivial ;
    01334              int evals ;
    01335              int flips ;
    01336              int pivrnks ;
    01337              int maxrnk ; } dmulti ;
    01338     struct { int cnt ;
    01339              int cands ;
    01340              int nontrivial ;
    01341              int promote ; } pmulti ;
    01342     struct { int prevpiv ;
    01343              int maxcnt ;
    01344              int totpivs ;
    01345              int maxpivs ;
    01346              int chgcnt1 ;
    01347              int chgcnt2 ; } infeas ;
    01348     struct { int cnt ;
    01349              float avgsiz ;
    01350              int maxsiz ;
    01351              int totpivs ;
    01352              float avgpivs ;
    01353              int maxpivs ; } pdegen[DYSTATS_MAXDEGEN] ;
    01354     struct { int cnt ;
    01355              float avgsiz ;
    01356              int maxsiz ;
    01357              int totpivs ;
    01358              float avgpivs ;
    01359              int maxpivs ; } ddegen[DYSTATS_MAXDEGEN] ;
    01360     struct { int iters ;
    01361              int pivs ; } tot ;
    01362     struct { int iters ;
    01363              int pivs ; } p1 ;
    01364     struct { int iters ;
    01365              int pivs ; } p2 ;
    01366     struct { int iters ;
    01367              int pivs ; } d2 ; } lpstats_struct ;
    01368
    01369
    01370
    01371 #ifdef DYLP_INTERNAL
    01372
    01373 /*
    01374   Macros to determine whether a constraint or variable is active, and whether
    01375   it's eligible for activation. Coding is explained below for dy_origcons and
    01376   dy_origvars. The main purpose served by these macros is to make it easy to
    01377   find activiation/deactivation points in the code, should the conventions ever
    01378   change.
    01379 */
    01380
    01381 #define ACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] > 0)
    01382 #define INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] <= 0)
    01383 #define LOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] == 0)
    01384 #define MARK_UNLOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = -1)
    01385 #define MARK_INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = 0)
    01386
    01387 #define ACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] > 0)
    01388 #define INACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] <= 0)
    01389 #define LOADABLE_VAR(zz_vndx_zz) \
    01390   ((dy_origvars[(zz_vndx_zz)] < 0) && \
    01391    flgoff(((flags) -dy_origvars[(zz_vndx_zz)]),vstatNOLOAD|vstatNBFX))
    01392 #define MARK_INACTIVE_VAR(zz_vndx_zz,zz_val_zz) \
    01393   (dy_origvars[(zz_vndx_zz)] = (zz_val_zz))
    01394
    01395
    01396 /*
    01397   dy_logchn             i/o id for the execution log file
    01398   dy_gtxecho            controls echoing of generated text to stdout
    01399 */
    01400
    01401 extern ioid dy_logchn ;
    01402 extern bool dy_gtxecho ;
    01403
    01404
    01405 /*
    01406   lp_struct
    01407
    01408   This structure is the control structure for an LP problem within dylp.
    01409
    01410   Field         Definition
    01411   -----         ----------
    01412   phase         Current phase of the dynamic simplex algorithm.
    01413   lpret         Return code from the most recent simplex execution.
    01414
    01415   z             Value of the objective function (includes inactzcorr).
    01416   inactzcorr    Correction to the objective function due to inactive variables
    01417                 with non-zero values.
    01418
    01419   simplex       Simplex algorithm status and control
    01420     active        currently active or most recently completed
    01421     next          currently active or to be started
    01422     init_pse      TRUE if the PSE structures need to be reinitialised,
    01423                   FALSE otherwise
    01424     init_dse      TRUE if the DSE structures need to be reinitialised,
    01425                   FALSE otherwise
    01426                 These fields are used to determine when to update or
    01427                 reinitialise the PSE and DSE data structures. Active and next
    01428                 must be valid during the purge/gen/add variable/constraint
    01429                 cycles.
    01430
    01431                 A word on infeas and infeascnt: They are guaranteed accurate
    01432                 only immediately after initialisation and following a primal
    01433                 feasibility check.
    01434
    01435   infeas        Total infeasibility = SUM{j} max(0,x<j>-ub<j>,lb<j>-x<j>)
    01436   infeascnt     The number of infeasible variables; refreshed when dy_accchk
    01437                 is asked to do a primal feasibility check.
    01438
    01439   ubnd          Substructure for information on unbounded or pseudo-unbounded
    01440                 problems.
    01441     ndx           The index of the variable fingered for causing unboundedness
    01442                   or pseudo-unboundedness (swing).
    01443     ratio         The growth ratio.
    01444
    01445   p1obj         The following fields relate to handling of the phase I
    01446                 objective function.
    01447     installed   TRUE if the phase I objective is currently installed
    01448     infcnt      Tracks the number of variables incorporated in p1obj which
    01449                 remain infeasible.
    01450     infvars_sze Allocated size of the infvars vector.
    01451     infvars     Vector of indices of infeasible variables incorporated in the
    01452                 phase I objective.
    01453     p1obj       Pointer to the phase I objective (temporary storage while
    01454                 the phase II objective is installed).
    01455     p2obj       Pointer to the phase II objective (temporary storage while
    01456                 the phase I objective is installed).
    01457
    01458                 A word on pivot and iteration counts: Iteration counts tally
    01459                 iterations of the pivoting loop, successful or not. Pivot
    01460                 counts tally successful bound-to-bound or change-of-basis
    01461                 pivots. Pretty much all messages will give tot.iters, so that
    01462                 it's possible to track the progress of an LP. Iterf has an
    01463                 entirely different function -- it's tracking the accumulation
    01464                 of eta matrices in the basis representation.
    01465
    01466   sys           Substructure for dynamic system modification status.
    01467     forcedfull    Set to TRUE if the full system has been forced in state
    01468                   dyFORCEFULL. This should happen at most once, so if we
    01469                   enter dyFORCEFULL and forcedfull == TRUE, it's fatal.
    01470     cons
    01471       loadable    Count of constraints which could be activated
    01472       unloadable  Count of constraints which are ineligible for activation
    01473                   (empty constraints and nonbinding rows)
    01474     vars
    01475       loadable    Count of variables which could be activated
    01476       unloadable  Count of variables which are ineligible for activation
    01477                   (nonbasic fixed)
    01478
    01479   tot           Total simplex iterations and pivots, all phases
    01480     iters
    01481     pivs
    01482   p1            Primal phase I iterations and pivots.
    01483     iters
    01484     pivs
    01485   p2            Primal phase II iterations and pivots.
    01486     iters
    01487     pivs
    01488   d2            Dual phase II iterations and pivots.
    01489     iters
    01490     pivs
    01491
    01492   pivok         Set to TRUE in dy_{primal|dual}pivot if the current iteration
    01493                 is a  successful pivot. Cleared to FALSE at the head of
    01494                 dy_duenna.
    01495   prev_pivok    Set to pivok at head of dy_duenna. Provides status of just
    01496                 completed pivot for post-Duenna decisions.
    01497
    01498   basis         Various fields related to basis change, refactoring, etc.
    01499
    01500     etas        The number of basis changes (hence eta matrices) since the
    01501                 the basis was last factored. Used to schedule periodic
    01502                 factoring of the basis. Reset to 0 each time the basis is
    01503                 factored.
    01504     pivs        The number of basis pivots since entry into a primal or dual
    01505                 simplex phase (excludes bound-to-bound simplex `pivots').
    01506                 Used when deciding whether to remove variables from the pivot
    01507                 reject list, and whether to pop out of a simplex phase due to
    01508                 excessive swing.
    01509     dinf        Number of successive refactors with dual infeasibility.
    01510                 Cleared at the start of a simplex phase.
    01511                 Incremented/cleared in dy_accchk iff a dual feasibility check
    01512                 is performed.
    01513
    01514   degen         Activation level of antidegeneracy algorithm. Held at 0 when
    01515                 the antidegeneracy algorithm is not active. Incremented each
    01516                 time a restricted subproblem is formed, and decremented when
    01517                 the restriction is backed out. (Values > 1 indicate that
    01518                 degeneracy recurred while working on a restricted subproblem,
    01519                 resulting in further restriction.)
    01520   degenpivcnt   The number of successive degenerate pivots.
    01521
    01522   idlecnt       The number of cycles since the objective has changed.
    01523
    01524   lastz         Previous objective value for various activities; used to
    01525                 detect and suppress loops.
    01526     piv           Objective at last pivot (detects stalling)
    01527     cd            Objective at last entry into constraint deactivation
    01528                   (dyPURGECON) (detects constraint activate/deactivate loops)
    01529     vd            Objective at last entry into variable deactivation
    01530                   (dyPURGEVAR) (detects variable activate/deactivate loops)
    01531     fp            Objective at last entry into force primal (dyFORCEPRIMAL)
    01532                   (detects constraint activate/deactivate loops)
    01533     fd            Objective at last entry into force dual (dyFORCEDUAL)
    01534                   (detects variable activate/deactivate loops)
    01535
    01536   prim          Primal variable information
    01537     norm1         1-norm of basic primal variables inv(B)b
    01538     norm2         2-norm of basic primal variables
    01539     max           inf-norm (max) of basic primal variables
    01540     maxndx        index of max primal variable
    01541
    01542   dual          Dual variable information
    01543     norm1         1-norm of dual variables c<B>inv(B)
    01544     norm2         2-norm of dual variables
    01545     max           inf-norm (max) of dual variables
    01546     maxndx        index of max dual variable
    01547
    01548 */
    01549
    01550 typedef struct
    01551 { dyphase_enum phase ;
    01552   lpret_enum lpret ;
    01553   double z ;
    01554   double inactzcorr ;
    01555   struct { dyphase_enum active ;
    01556            dyphase_enum next ;
    01557            bool init_pse ;
    01558            bool init_dse ; } simplex ;
    01559   double infeas ;
    01560   int infeascnt ;
    01561   struct { int ndx ;
    01562            double ratio ; } ubnd ;
    01563   struct { bool installed ;
    01564            int infcnt ;
    01565            int infvars_sze ;
    01566            int *infvars ;
    01567            double *p1obj ;
    01568            double *p2obj ; } p1obj ;
    01569   struct { struct { int loadable ;
    01570                     int unloadable ; } cons ;
    01571            struct { int loadable ;
    01572                     int unloadable ; } vars ;
    01573            bool forcedfull ; } sys ;
    01574   struct { int iters ;
    01575            int pivs ; } tot ;
    01576   struct { int iters ;
    01577            int pivs ; } p1 ;
    01578   struct { int iters ;
    01579            int pivs ; } p2 ;
    01580   struct { int iters ;
    01581            int pivs ; } d2 ;
    01582   bool pivok ;
    01583   bool prev_pivok ;
    01584   struct { int etas ;
    01585            int pivs ;
    01586            int dinf ; } basis ;
    01587   int degen ;
    01588   int degenpivcnt ;
    01589   int idlecnt ;
    01590   struct { double piv ;
    01591            double cd ;
    01592            double vd ;
    01593            double fp ;
    01594            double fd ; } lastz ;
    01595   struct { double norm1 ;
    01596            double norm2 ;
    01597            double max ;
    01598            int maxndx ; } prim ;
    01599   struct { double norm1 ;
    01600            double norm2 ;
    01601            double max ;
    01602            int maxndx ; } dual ;
    01603   } lp_struct ;
    01604
    01605
    01606 /*
    01607   Declarations global to the dylp implementation but not visible outside of
    01608   it. With this we can avoid passing huge numbers of parameters and/or
    01609   unpacking a structure on a regular basis. Unless otherwise indicated, indices
    01610   are in the dy_sys (active system) frame of reference.
    01611
    01612   dy_owner      Null if there's no active problem. Contains the ID of the
    01613                 current owner if there's an active problem. Passed in as
    01614                 part of the lpprob_struct.
    01615
    01616   Main structures
    01617   ---------------
    01618   dy_lp:        The lp control structure for dylp.
    01619   dy_sys:       The active constraint system; initialised in dylp:startup
    01620   dy_tols:      Tolerances in effect for dylp; initialised in
    01621                 dylp:dylp from orig_tols.
    01622   dy_opts:      Options in effect for dylp; initialised in
    01623                 dylp:dylp to point to same structure as orig_opts.
    01624   dy_stats      Statistics structure for dylp; initialised in dylp:dylp to
    01625                 point ot the same structure as orig_stats.
    01626
    01627   Constraint & Variable Management
    01628   --------------------------------
    01629   dy_actvars:   The active variables. Indexed in dy_sys frame, contains
    01630                 indices in orig_sys frame. Attached to dy_sys.
    01631                 Entries for logical variables (1 <= j <= concnt) are
    01632                 meaningless.
    01633   dy_actcons:   The active constraints. Indexed in dy_sys frame, contains
    01634                 indices in orig_sys frame. Attached to dy_sys.
    01635   dy_origvars:  Status of the original architectural variables.
    01636                  * A value of 0 indicates the entry hasn't been processed.
    01637                    Should never happen.
    01638                  * If the variable is active, the entry contains the index
    01639                    of the variable in the dy_sys frame.
    01640                  * If the variable is inactive, the coding is the negative of
    01641                    the vstat flags, limited to the nonbasic status values
    01642                    vstatNBFR, vstatNBFX, vstatNBLB, or vstatNBUB, and the
    01643                    qualifier vstatNOLOAD.
    01644                 Indexed in orig_sys frame. Attached to orig_sys.
    01645   dy_origcons:  Status of the original constraints.
    01646                  * If the constraint is active, the entry contains the index
    01647                    of the constraint in the dy_sys frame.
    01648                  * If the constraint is inactive, contains 0.
    01649                  * If the constraint cannot be activated, contains a negative
    01650                    value.
    01651                 Indexed in orig_sys frame. Attached to orig_sys.
    01652
    01653   Note that there are macros defined to test whether a variable or constraint
    01654   is inactive, and whether it's eligible for activation. Use them!
    01655
    01656   Basis Management
    01657   ----------------
    01658   dy_basis:     The basis vector. Indexed by basis position, attached to
    01659                 dy_sys.
    01660   dy_var2basis: Translates a variable index to a basis pos'n. Indexed by
    01661                 column, attached to dy_sys. Entries for nonbasic variables
    01662                 must be kept at 0.
    01663   dy_status:    The status vector. Indexed by column, attached to dy_sys.
    01664
    01665   Primal and Dual Variables
    01666   -------------------------
    01667   dy_x:         The values of all primal variables. Indexed by column,
    01668                 attached to dy_sys. Values of nonbasic variables must always
    01669                 be correct (to allow uniform handling of normal nonbasic
    01670                 variables and superbasic variables). Values of basic
    01671                 variables will retain unperturbed values while the
    01672                 antidegeneracy mechanism is active -- this allows the
    01673                 perturbation to be quickly backed out.
    01674   dy_xbasic:    The values of the basic variables. Indexed by basis pos'n,
    01675                 attached to dy_sys.
    01676   dy_y:         The dual variables. Indexed by basis pos'n, attached to
    01677                 dy_sys.
    01678
    01679   Projected Steepest Edge (PSE) Pricing
    01680   -------------------------------------
    01681   dy_cbar:      Iteratively updated vector of reduced costs. Indexed by column,
    01682                 attached to dy_sys.
    01683   dy_gamma:     Iteratively updated vector of column norms ||abar<j>||^2.
    01684                 Indexed by column, attached to dy_sys.
    01685   dy_frame:     Boolean vector which indicates if a given variable is in the
    01686                 current frame of reference. Indexed by column, attached to
    01687                 dy_sys.
    01688
    01689   Dual Steepest Edge (DSE) Pricing
    01690   --------------------------------
    01691   dy_rho:       Iteratively updated vector of row norms ||beta<i>||^2.
    01692                 Indexed by basis position, attached to dy_sys.
    01693
    01694   DSE pricing also makes use of dy_xbasic (the reduced costs of the dual
    01695   variables), and maintains dy_cbar.
    01696
    01697   Antidegeneracy
    01698   --------------
    01699   dy_brkout:    Specifies the direction a variable needs to move to escape
    01700                 from a degenerate vertex.  Indexed by basis pos'n, attached
    01701                 to dy_sys.
    01702   dy_degenset:  Specifies the set of constraints (equivalently, basic
    01703                 variables) perturbed at each level of the antidegeneracy
    01704                 algorithm. Indexed by basis pos'n, attached to dy_sys.  The
    01705                 entry for a constraint is the highest level of degenerate set
    01706                 which includes the constraint. If the entry is 0, the
    01707                 constraint is not involved in degeneracy.
    01708   dy_ddegenset: Specifies the set of dual constraints (equivalently, reduced
    01709                 costs) perturbed at each level of the antidegeneracy
    01710                 algorithm. Indexed by variable index, attached to dy_sys.
    01711                 The entry for a dual constraint is the highest level of
    01712                 degenerate set which includes the constraint. If the entry is
    01713                 0, the constraint is not involved in degeneracy.
    01714 */
    01715
    01716 extern void *dy_owner ;
    01717
    01718 extern lp_struct *dy_lp ;
    01719 extern consys_struct *dy_sys ;
    01720 extern lptols_struct *dy_tols ;
    01721 extern lpopts_struct *dy_opts ;
    01722 extern int *dy_actvars,*dy_actcons,*dy_origvars,*dy_origcons,
    01723            *dy_basis,*dy_var2basis,
    01724            *dy_brkout,*dy_degenset,*dy_ddegenset ;
    01725 extern flags *dy_status ;
    01726 extern double *dy_x,*dy_xbasic,*dy_y,*dy_cbar,*dy_gamma,*dy_rho ;
    01727 extern bool *dy_frame ;
    01728
    01729 extern lpstats_struct *dy_stats ;
    01730
    01731 /*
    01732   dy_scaling.c
    01733 */
    01734
    01735 extern bool dy_initlclsystem(lpprob_struct *orig_lp, bool hotstart) ;
    01736 extern void dy_freelclsystem(lpprob_struct *orig_lp, bool freesys) ;
    01737 extern bool dy_isscaled(void) ;
    01738 extern void dy_scaling_vectors(const double **rscale, const double **cscale) ;
    01739 extern consys_struct *dy_scaled_origsys() ;
    01740
    01741 /*
    01742   dy_coldstart.c
    01743 */
    01744
    01745 extern dyret_enum dy_coldstart(consys_struct *orig_sys),
    01746                   dy_crash(void) ;
    01747
    01748 /*
    01749   dy_warmstart.c
    01750 */
    01751
    01752 extern dyret_enum dy_warmstart(lpprob_struct *orig_lp) ;
    01753
    01754 /*
    01755   dy_hotstart.c
    01756 */
    01757
    01758 extern dyret_enum dy_hotstart(lpprob_struct *orig_lp) ;
    01759
    01760 /*
    01761   dy_basis.c
    01762 */
    01763
    01764 extern dyret_enum dy_factor(flags *calcflgs),
    01765                   dy_pivot(int xipos, double abarij, double maxabarj) ;
    01766 extern double dy_chkpiv(double abarij, double maxabarj) ;
    01767 extern void dy_btran(double *col), dy_ftran(double *col, bool save) ;
    01768 extern bool dy_setpivparms(int curdelta, int mindelta) ;
    01769 extern char *dy_prtpivparms(int lvl) ;
    01770
    01771 /*
    01772   dy_bound.c
    01773 */
    01774
    01775 extern int dy_activateBndCons(consys_struct *orig_sys) ;
    01776 extern int dy_dualaddvars(consys_struct *orig_sys) ;
    01777
    01778 /*
    01779   dy_conmgmt.c
    01780 */
    01781
    01782 extern bool dy_loadcon(consys_struct *orig_sys, int orig_ndx,
    01783                        bool genvars, int *inactndxs) ;
    01784 extern bool dy_deactNBLogPrimCon(consys_struct *orig_sys, int i),
    01785             dy_deactBLogPrimCon(consys_struct *orig_sys, int i),
    01786             dy_actBLogPrimCon(consys_struct *orig_sys, int i,
    01787                               int *inactvars),
    01788             dy_actBLogPrimConList(consys_struct *orig_sys,
    01789                                   int cnt, int *ocndxs, int **inactvars) ;
    01790 extern int dy_deactivateCons(consys_struct *orig_sys),
    01791            dy_activateCons(consys_struct *orig_sys, bool with_vars) ;
    01792
    01793 /*
    01794   dy_varmgmt.c
    01795 */
    01796
    01797 extern bool dy_actNBPrimArch(consys_struct *orig_sys, int ovndx),
    01798             dy_actNBPrimArchList(consys_struct *orig_sys,
    01799                                  int cnt, int *ovndxs),
    01800             dy_deactBPrimArch(consys_struct *orig_sys, int ovndx),
    01801             dy_deactNBPrimArch(consys_struct *orig_sys, int ovndx) ;
    01802 extern int dy_deactivateVars(consys_struct *orig_sys),
    01803            dy_activateVars(consys_struct *orig_sys, int *candidates) ;
    01804
    01805 /*
    01806   dy_primalpivot.c
    01807 */
    01808
    01809 extern dyret_enum dy_primalin(int initcol, int scan, int *xjndx, int *nextcol),
    01810                   dy_primalpivot(int xjndx, int indir, int *xindx, int *outdir,
    01811                                  double *abarij, double *delta, int *xjcand),
    01812                   dy_degenout(int level) ;
    01813
    01814 /*
    01815   dy_duenna.c
    01816 */
    01817
    01818 extern dyret_enum dy_duenna(dyret_enum pivresult, int xjndx, int xindx,
    01819                             int xjcand, int xicand),
    01820                   dy_accchk(flags *checks) ;
    01821
    01822 /*
    01823   dy_pivreject.c
    01824 */
    01825
    01826 extern dyret_enum dy_addtopivrej(int xkndx, dyret_enum why,
    01827                                  double abarij, double maxabarij),
    01828                   dy_dealWithPunt(void) ;
    01829 extern bool dy_clrpivrej(int *entries) ;
    01830 extern void dy_checkpivtol(void) ;
    01831 extern void dy_initpivrej(int sze), dy_freepivrej(void) ;
    01832
    01833
    01834 /*
    01835   dy_primal.c
    01836 */
    01837
    01838 extern lpret_enum dy_primal(void) ;
    01839 extern bool dy_initp1obj(void),dy_swapobjs(dyphase_enum phase) ;
    01840
    01841 /*
    01842   dy_dualpivot.c
    01843 */
    01844
    01845 extern dyret_enum
    01846   dy_dualout(int *xindx),
    01847   dy_dualpivot(int xindx, int outdir,
    01848                int *p_xjndx, int *p_indir, double *p_cbarj,
    01849                double *p_abarij, double *p_delta, int *xicand),
    01850   dy_dualdegenout(int level) ;
    01851
    01852 /*
    01853   dy_dual.c
    01854 */
    01855
    01856 extern lpret_enum dy_dual(void) ;
    01857
    01858 #endif /* DYLP_INTERNAL */
    01859
    01860 /*
    01861   dy_setup.c
    01862 */
    01863
    01864 extern void dy_defaults(lpopts_struct **opts, lptols_struct **tols),
    01865             dy_checkdefaults(consys_struct *sys,
    01866                              lpopts_struct *opts, lptols_struct *tols),
    01867             dy_setprintopts(int lvl, lpopts_struct *opts) ;
    01868
    01869
    01870 /*
    01871   dylp.c
    01872 */
    01873
    01874 extern lpret_enum dylp(lpprob_struct *orig_lp, lpopts_struct *orig_opts,
    01875                        lptols_struct *orig_tols, lpstats_struct *orig_stats) ;
    01876 extern void *dy_getOwner() ;
    01877
    01878 /*
    01879   dylp_utils.c
    01880 */
    01881
    01882 #ifdef DYLP_INTERNAL
    01883
    01884 extern lpret_enum dyret2lpret(dyret_enum dyret) ;
    01885 extern dyret_enum dy_updateprimals(int j, double deltaj, double *p_abarj) ;
    01886 extern bool dy_reducerhs(double *rhs, bool init),
    01887             dy_calcprimals(void),dy_calccbar(void) ;
    01888 extern void dy_calcduals(void),dy_setbasicstatus(void),
    01889             dy_dseinit(void),dy_pseinit(void) ;
    01890 extern double dy_calcobj(void),dy_calcdualobj(void),dy_calcpinfeas(void) ;
    01891 extern void dy_finishup(lpprob_struct *orig_lp, dyphase_enum phase) ;
    01892
    01893 #ifdef DYLP_PARANOIA
    01894
    01895 extern bool dy_chkstatus(int vndx),
    01896             dy_chkdysys(consys_struct *orig_sys) ;
    01897 extern void dy_chkdual(int lvl) ;
    01898
    01899 #endif
    01900
    01901 #endif /* DYLP_INTERNAL */
    01902
    01903 extern bool dy_dupbasis(int dst_basissze, basis_struct **p_dst_basis,
    01904                         basis_struct *src_basis, int dst_statussze,
    01905                         flags **p_dst_status,
    01906                         int src_statuslen, flags *src_status) ;
    01907 extern void dy_freesoln(lpprob_struct *lpprob) ;
    01908
    01909 /*
    01910   dy_penalty.c
    01911 */
    01912
    01913 extern bool dy_pricenbvars(lpprob_struct *orig_lp, flags priceme,
    01914                            double **p_ocbar, int *p_nbcnt, int **p_nbvars),
    01915             dy_pricedualpiv(lpprob_struct *orig_lp, int oxindx,
    01916                             double nubi, double xi, double nlbi,
    01917                             int nbcnt, int *nbvars,
    01918                             double *cbar, double *p_upeni, double *p_dpeni) ;
    01919
    01920 /*
    01921   dy_tableau.c
    01922 */
    01923
    01924 extern bool dy_abarj(lpprob_struct *orig_lp, int tgt_j, double **p_abarj) ;
    01925 extern bool dy_betaj(lpprob_struct *orig_lp, int tgt_j, double **p_betaj) ;
    01926 extern bool dy_betak(lpprob_struct *orig_lp, int col_k, double **p_betaj) ;
    01927 extern bool dy_betai(lpprob_struct *orig_lp, int tgt_i, double **p_betai) ;
    01928 extern bool dy_abari(lpprob_struct *orig_lp, int tgt_i, double **p_abari,
    01929                      double **p_betai) ;
    01930
    01931 /*
    01932   dy_rays.c
    01933 */
    01934
    01935 extern bool dy_primalRays(lpprob_struct *orig_lp,
    01936                           int *p_numRays, double ***p_rays) ;
    01937 extern bool dy_dualRays(lpprob_struct *orig_lp, bool fullRay,
    01938                         int *p_numRays, double ***p_rays, bool trueDuals) ;
    01939
    01940 /*
    01941   dy_solutions.c
    01942 */
    01943
    01944 extern void dy_colDuals(lpprob_struct *orig_lp, double **p_cbar,
    01945                         bool trueDuals) ;
    01946 extern void dy_rowDuals(lpprob_struct *orig_lp, double **p_y,
    01947                         bool trueDuals) ;
    01948 extern void dy_rowDualsGivenC(lpprob_struct *orig_lp, double **p_y,
    01949                               const double *c, bool trueDuals) ;
    01950
    01951 extern void dy_colPrimals(lpprob_struct *orig_lp, double **p_x) ;
    01952 extern void dy_rowPrimals(lpprob_struct *orig_lp,
    01953                           double **p_xB, int **p_indB) ;
    01954 extern void dy_logPrimals(lpprob_struct *orig_lp, double **p_logx) ;
    01955
    01956 extern void dy_colStatus(lpprob_struct *orig_lp, flags **p_colstat) ;
    01957 extern void dy_logStatus(lpprob_struct *orig_lp, flags **p_logstat) ;
    01958
    01959 extern bool dy_expandxopt(lpprob_struct *lp, double **p_xopt) ;
    01960
    01961 /*
    01962   dylp_io.c
    01963 */
    01964
    01965 #include <dylib_io.h>
    01966
    01967 #ifdef DYLP_INTERNAL
    01968
    01969 extern void dy_logpivot(dyret_enum result, int xjndx, int indir, double cbarj,
    01970                         int xindx, int outdir, double abarij, double delta) ;
    01971 extern const char *dy_prtdyret(dyret_enum retcode) ;
    01972
    01973 #endif /* DYLP_INTERNAL */
    01974
    01975 extern const char *dy_prtlpret(lpret_enum lpret),
    01976                   *dy_prtlpphase(dyphase_enum phase, bool abbrv) ;
    01977 extern char *dy_prtvstat(flags status) ;
    01978 extern bool dy_dumpcompact(ioid chn, bool echo, lpprob_struct *soln,
    01979                            bool nbzeros) ;
    01980 extern void dy_setlogchn (ioid chn) ;
    01981 extern void dy_setgtxecho (bool echo) ;
    01982
    01983 /*
    01984   dy_statistics.c
    01985
    01986   These routines are compiled unconditionally, but note that the compile-time
    01987   symbol DYLP_STATISTICS must be defined before dylp will actually take the
    01988   time to collect detailed statistics. See dy_statistics.c for additional
    01989   instructions.
    01990 */
    01991
    01992 extern void dy_initstats(lpstats_struct **p_lpstats, consys_struct *orig_sys),
    01993             dy_dumpstats(ioid chn, bool echo, lpstats_struct *lpstats,
    01994                          consys_struct *orig_sys),
    01995             dy_freestats(lpstats_struct **p_lpstats) ;
    01996
    01997 #ifdef DYLP_INTERNAL
    01998
    01999 extern void dy_finalstats(lpstats_struct *lpstats) ;
    02000
    02001 #endif /* DYLP_INTERNAL */
    02002
    02003
    02004 #endif /* _DYLP_H */

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines