• Main Page
  • Classes
  • Files
  • File List
  • File Members

/build/buildd/coinor-dylp-1.6.0/DyLP/src/Dylp/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 Common Public License (CPL).
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 299 2009-08-28 01:35:28Z 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   ctlopts       Control and status flags.               
00538   phase         (i) If set to dyDONE, dylp will free any retained data
00539                     structures and return. Any other value is ignored.
00540                 (o) Termination phase of the dynamic simplex algorithm;
00541                     should be dyDONE unless something screws up, in which
00542                     case it'll be dyINV.
00543   lpret         Return code from the simplex routine.
00544   obj           For lpOPTIMAL, the value of the objective function.
00545                 For lpINFEAS, the total infeasibility.
00546                 For lpUNBOUNDED, the index of the unbounded variable, negated
00547                   if the variable can decrease without bound, positive if it
00548                   can increase without bound. The logical for constraint i
00549                   is represented as n+i.
00550                 Otherwise, undefined.
00551   iters         The number of simplex iterations.
00552   consys        The constraint system.
00553   basis         (i) Initial basis.
00554                 (o) Final basis.
00555   status        (i) Initial status vector.
00556                 (o) Final status vector.
00557   x             (i) No values used, but a vector can be supplied.
00558                 (o) The values of the basic variables (indexed by basis
00559                     position).
00560   y             (i) No values used, but a vector can be supplied.
00561                 (o) The values of the dual variables (indexed by basis
00562                     position).
00563   actvars       There is one entry for each variable, coded TRUE if the
00564                 variable is active, FALSE otherwise. The vector supplied on
00565                 input will be overwritten on output.
00566                 (i) Variables to be activated at startup. Used only for a
00567                     warm start. Validity is indicated by the lpctlACTVARSIN
00568                     flag. A vector can be supplied strictly for output use.
00569                 (o) The current active variables. Will be returned only if
00570                     requested by the lpctlACTVARSOUT flag. If the vector is
00571                     valid on return, lpctlACTVARSOUT will remain set,
00572                     otherwise it will be reset.
00573 
00574   colsze        Allocated column capacity (length of status vector).
00575   rowsze        Allocated row capacity (length of basis, x, and y vectors).
00576 
00577   
00578   Note that dylp will reallocate status, basis->el, actvars, x, and y, if the
00579   vectors supplied at startup are too small to report the solution. Don't set
00580   colsze or rowsze to nonzero values without actually allocating space.
00581 */
00582 
00583 typedef struct
00584 { flags ctlopts ;
00585   dyphase_enum phase ;
00586   lpret_enum lpret ;
00587   double obj ;
00588   int iters ;
00589   consys_struct *consys ;
00590   basis_struct *basis ;
00591   flags *status ;
00592   double *x ;
00593   double *y ;
00594   bool *actvars ;
00595   int colsze ;
00596   int rowsze ; } lpprob_struct ;
00597 
00598 
00599 
00600 /*
00601   lptols_struct
00602 
00603   This structure contains phase and tolerance information for the lp algorithm.
00604 
00605   The philosophy with respect to the separate zero and feasibility tolerances
00606   for primal and dual variables is that dylp uses the zero tolerance when
00607   calculating primal or dual variables, and the feasibility tolerance when
00608   checking for feasibility. This allows us to keep small values for accuracy
00609   in computation, but not be so fussy when it comes to feasibility.
00610 
00611   Field         Definition
00612   -----         ----------
00613   inf           Infinity. dylp uses IEEE FP infinity, but be careful not to
00614                 pass it to the basis package.
00615   zero          Zero tolerance for primal variables, and also the generic
00616                 zero tolerance for constraint coefficients, right-hand-side
00617                 values, etc.
00618   pchk          Primal accuracy check tolerance.
00619   pfeas         Primal feasibility check tolerance; dynamically scaled from
00620                 zero in proportion to the 1-norm of the primal basic variables.
00621   pfeas_scale   Primal feasibility check tolerance multiplier. This provides
00622                 some user-controllable decoupling of zero and pfeas.
00623   cost          Base zero tolerance for checks involving objective function
00624                 coefficients, reduced costs, and related values.
00625   dchk          Dual accuracy check tolerance. Also used by dy_duenna to
00626                 test for improvement in the objective.
00627   dfeas         Dual feasbility check tolerance; dynamically scaled from cost
00628                 in proportion to the 1-norm of the dual variables. Acts as the
00629                 zero tolerance for reduced costs.
00630   dfeas_scale   Dual feasibility check tolerance multiplier. This provides
00631                 some user-controllable decoupling of cost and dfeas.
00632   pivot         Simplex pivot selection tolerance, expressed as a multiplier
00633                 for the pivot selection tolerance used by the basis package
00634                 when factoring the basis. (I.e., the actual pivot selection
00635                 criteria will be to accept a simplex pivot a<i,j> if
00636                 |a<i,j>| > lptols.pivot*basis.pivot*MAX{i}|a<i,j>|.)
00637   bogus         Multiplier used to identify 'bogus' values, in the range
00638                 tol < |val| < bogus*tol for the appropriate tolerance.
00639   swing         Ratio used to identify excessive growth in primal variables
00640                 (pseudo-unboundedness).
00641   toobig        Absolute value of primal variables which will cause dual
00642                 multipivoting to consider primal infeasibility when selecting
00643                 a flip/pivot sequence.
00644   purge         Percentage change in objective function required before
00645                 constraint or variable purging is attempted.
00646   purgevar      Percentage of maximum reduced cost used to determine the
00647                 variable purge threshold; nonbasic architectural variables
00648                 at their optimum bound whose reduced cost exceeds
00649                 purgevar*MAX{j}cbar<j> are purged.
00650 
00651   reframe       Multiplier used to trigger a reference framework reset in
00652                 PSE pricing; reset occurs if
00653                   |gamma<j> - ||abar<j>||^2| > reframe*||abar<j>||^2.
00654                 The check is made in pseupdate.
00655                 Also used to trigger recalculation of the basis inverse row
00656                 norms used in DSE pricing; reset occurs if
00657                   |rho<i> - ||beta<i>||^2| > reframe*||beta<i>||^2.
00658                 The check is made in dseupdate.
00659 */
00660 
00661 typedef struct
00662 { double inf ;
00663   double zero ;
00664   double pchk ;
00665   double pfeas ;
00666   double pfeas_scale ;
00667   double cost ;
00668   double dchk ;
00669   double dfeas ;
00670   double dfeas_scale ;
00671   double pivot ;
00672   double bogus ;
00673   double swing ;
00674   double toobig ;
00675   double purge ;
00676   double purgevar ;
00677   double reframe ; } lptols_struct ;
00678 
00679 #if defined(DYLP_INTERNAL) || defined(BONSAIG)
00680 /*
00681   A few handy macros for testing values against tolerances.
00682 */
00683 #ifdef DYLP_INTERNAL
00684 #  ifdef BND_TOLER
00685 #    undef BND_TOLER
00686 #  endif
00687 #  define BND_TOLER dy_tols->pfeas
00688 #  ifdef INF_TOLER
00689 #    undef INF_TOLER
00690 #  endif
00691 #  define INF_TOLER dy_tols->inf
00692 #endif
00693 
00694 #define withintol(zz_val_zz,zz_tgt_zz,zz_tol_zz) \
00695   (fabs((zz_val_zz)-(zz_tgt_zz)) <= zz_tol_zz)
00696 
00697 #define setcleanzero(zz_val_zz,zz_tol_zz) \
00698   if (fabs(zz_val_zz) < zz_tol_zz) zz_val_zz = 0
00699 
00700 #define atbnd(zz_val_zz,zz_bnd_zz) \
00701   ((fabs(zz_bnd_zz) < INF_TOLER) && \
00702    (fabs((zz_val_zz)-(zz_bnd_zz)) < BND_TOLER*(1.0+fabs(zz_bnd_zz))))
00703 
00704 #define belowbnd(zz_val_zz,zz_bnd_zz) \
00705   ((fabs(zz_bnd_zz) < INF_TOLER) ? \
00706    (((zz_bnd_zz)-(zz_val_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
00707    (zz_val_zz < zz_bnd_zz))
00708 
00709 #define abovebnd(zz_val_zz,zz_bnd_zz) \
00710   ((fabs(zz_bnd_zz) < INF_TOLER) ? \
00711    (((zz_val_zz)-(zz_bnd_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
00712    (zz_val_zz > zz_bnd_zz))
00713 
00714 #define withinbnds(zz_lb_zz,zz_val_zz,zz_ub_zz) \
00715   (!abovebnd(zz_val_zz,zz_ub_zz) && !belowbnd(zz_val_zz,zz_lb_zz))
00716 
00717 #endif /* DYLP_INTERNAL || BONSAIG */
00718 
00719 #ifdef DYLP_INTERNAL
00720 /*
00721   Finally, a macro to decide if we should snap to a value. The notion here is
00722   that the accuracy with which one can hit a target value depends on both the
00723   magnitude of the target and the distance travelled to get there. On a
00724   64-bit machine, IEEE FP has about 15 decimal digits of accuracy. For
00725   example, if we're travelling 1.0e7 and trying to hit zero, we only have 8
00726   decimal places of accuracy remaining. If we're within 1.0e-8, might as well
00727   snap to 0. In practice, there's already a bit of roundoff in any nontrivial
00728   calculation, so we start with the zero tolerance and scale from there.
00729   
00730   In some cases, we only know the target, so the best we can do is
00731   scale to it.
00732 
00733   The utility of this idea is highly questionable.
00734 */
00735 
00736 #define snaptol1(zz_tgt_zz) (dy_tols->zero*(1.0+(zz_tgt_zz)))
00737 
00738 #define snaptol2(zz_tgt_zz,zz_dst_zz) \
00739   (dy_tols->zero*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
00740 
00741 #define snaptol3(zz_tol_zz,zz_tgt_zz,zz_dst_zz) \
00742   ((zz_tol_zz)*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))
00743 
00744 #endif /* DYLP_INTERNAL */
00745 
00746 
00747 
00748 /*
00749   Enum for initial basis type.
00750 
00751   This determines the criteria used to select the initial set of basic
00752   variables during a cold start.
00753 
00754   ibINV         invalid
00755   ibLOGICAL     Use only logical (slack and artificial) variables
00756   ibSLACK       Use slack variables for inequalities. Prefer architectural
00757                 over artificial variables for equalities.
00758   ibARCH        Prefer architectural variables over logical variables.
00759 */
00760 
00761 typedef enum { ibINV = 0, ibLOGICAL, ibSLACK, ibARCH } ibtype_enum ;
00762 
00763 /*
00764   Enum for calling context.
00765 
00766   As dylp evolves, it may well prove useful to know the context of the
00767   call. Consider this an experiment. The default context is INITIALLP.
00768 
00769   cxINV         invalid (context is unknown)
00770   cxSINGLELP    This is a one-off call to solve a single LP from scratch.
00771   cxINITIALLP   This is a call to solve a single LP from scratch, but will
00772                 likely be followed by calls to reoptimise.
00773   cxBANDC       This call is made in the context of a branch-and-cut
00774                 algorithm.
00775 */
00776 
00777 typedef enum { cxINV = 0, cxSINGLELP, cxINITIALLP, cxBANDC } cxtype_enum ;
00778 
00779 /*
00780   lpopts_struct
00781 
00782   This structure is used to pass option settings to dylp. Default values are
00783   declared at the beginning of dy_setup.c.
00784 
00785   Field         Definition
00786   -----         ----------
00787   context       The context in which dylp is being called. See comments
00788                 above for cxtype_enum.
00789   forcecold     TRUE to force a cold start, FALSE otherwise. If set to TRUE,
00790                 dominates warm and hot start.
00791   forcewarm     TRUE to force a warm start, FALSE otherwise. If set to TRUE,
00792                 dominates hot start.
00793   fullsys       Forces the use of the full constraint system at all times. The
00794                 full constraint system is loaded on startup, and all constraint
00795                 and variable deactivation/activation is skipped. (But see the
00796                 finpurge option below.) (Also, this will not prevent dylp
00797                 from resorting to forced phase transitions, which typically
00798                 involve deactivation of constraints or variables. Arguably
00799                 this is a bad thing, and may change in the future.)
00800   active        Used to estimate the initial size of the dylp constraint
00801                 system relative to the original system.
00802     vars          Fraction of original variables expected to be active at
00803                   any time.
00804     cons          Fraction of original inequalities expected to be active at
00805                   any time.
00806   initcons      Specifies how inequalities will be selected to initialize the
00807                 active system. See extensive comments in dy_coldstart.c.
00808     frac          Fraction of inequalities to be used.
00809     i1l           Lower bound on angle to objective, first interval
00810     i1lopen       TRUE if the bound is open.
00811     i1u           Upper bound on angle to objective, first interval
00812     i1uopen       TRUE if the bound is open.
00813     i2valid       TRUE if the second interval is specified
00814     i2l           Lower bound on angle to objective, second interval
00815     i2lopen       TRUE if the bound is open.
00816     i2u           Upper bound on angle to objective, second interval
00817     i2uopen       TRUE if the bound is open.
00818   coldbasis     Code specifying the kind of basis built for a cold start. See
00819                 comments for ibtype_enum and comments in dy_coldstart.c
00820   finpurge      Controls whether dylp does a final deactivation of constraints
00821                 and/or variables. This will occur only an optimal solution is
00822                 found, and is not suppressed by fullsys.
00823     cons          TRUE to purge constraints
00824     vars          TRUE to purge variables
00825   heroics       Controls behaviour during forced primal <-> dual transitions
00826     d2p           TRUE to allow deactivation of basic architecturals, FALSE
00827                   to disallow. FALSE is recommended, and the default.
00828     p2d           TRUE to allow deactivation of tight constraints, FALSE
00829                   to disallow. FALSE is recommended, and the default.
00830     flip          TRUE to allow flips to regain dual feasibility, FALSE to
00831                   disallow. Tends to cycle; default is false.
00832   coldvars      If the number of active variables exceeds this value after
00833                 a cold start, dylp will attempt to purge variables prior to
00834                 the initial primal simplex run.
00835   con           Options related to constraint activation/deactivation
00836     actlvl        The constraint activation strategy
00837                     0: (strict) activate violated constraints,
00838                        lhs < rhslow or lhs > rhs
00839                     1: (tight) activate tight or violated constraints,
00840                        lhs <= rhslow or lhs >= rhs
00841     actlim        If non-zero, limits the number of constraints that can be
00842                   activated in any one call to a constraint activation
00843                   routine.
00844     deactlvl    The constraint deactivation strategy:
00845                   0: (normal) deactivate only inequalities i which are
00846                      strictly loose (i.e., slk<i> basic, not at bound).
00847                   1: (aggressive) normal plus inequalities which are tight
00848                      with y<i> = 0.
00849                   2: (fanatic) aggressive plus equalities with y<i> = 0
00850   usedual       TRUE if dual phase II is to be used to regain feasibility after
00851                 adding constraints, FALSE to force use of primal phase I.
00852   addvar        If non-zero, at most this many variables will be added in
00853                 any one pass through phase dyADDVAR.
00854   dualadd       Controls the types of activation allowed when adding variables
00855                 during dual simplex.
00856                   0:    variable activation is disallowed
00857                   1:    type 1 activation (variables that will be dual feasible
00858                         when activated into the nonbasic partition)
00859                   2:    type 2 activation (variables which can be activated
00860                         if immediately pivoted into the basis)
00861                   3:    type 3 activation (activate with bound-to-bound pivot)
00862                 See dy_dualaddvars for more extensive comments.
00863   scan          Partial pricing parameter. Controls the number of columns to
00864                 be scanned for a new candidate entering variable when the
00865                 candidate selected during PSE update is rejected.
00866   iterlim       The per phase pivot limit for the code; if set to 0, no
00867                 limit is enforced.
00868   idlelim       The number of iterations without change in the objective
00869                 function before the code declares the problem is stalled or
00870                 cycling.
00871   dpsel         Options to control dual pivoting. Selection of the leaving
00872                 variable is always handled by DSE.
00873     strat:        The strategy used to select the entering variable:
00874                     0: standard ratio test; may use anti-degen lite
00875                     1: multipivoting, selecting for maximum dual objective
00876                        improvement.
00877                     2: multipivoting, select for minimum predicted
00878                        infeasibility.
00879                     3: multipivoting, select infeasibility reduction if
00880                        possible, otherwise maximum dual objective improvement.
00881     flex          If TRUE, dylp will switch between strategies 1 and 3, using
00882                   strategy 1 unless primal magnitudes become too large.
00883     allownopiv    If TRUE, sequences of flips with no finishing pivot will be
00884                   allowed. Defaults to false, very prone to cycling.
00885   ppsel         Options to control primal pivoting. Selection of the entering
00886                 variable is always handled by PSE.
00887     strat:        The strategy used to select the leaving variable:
00888                     0: standard ratio test; may use anti-degen lite
00889                     1: multipivoting
00890   factor        The LP basis will be refactored every factor iterations, in
00891                 the absence of some compelling reason (typically error
00892                 recovery) that forces it to occur sooner.
00893   check         An accuracy check will be forced every check iterations, in
00894                 the absence of some compelling reason to do it earlier.
00895   groom         Controls the action taken by the basis grooming routine
00896                 when it makes a nontrivial status correction:
00897                   0:    catatonic
00898                   1:    issue a warning
00899                   2:    issue an error message and force an abort
00900                 Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
00901   degen         TRUE to allow creation of restricted subproblems to deal with
00902                 degeneracy, FALSE to disallow it.
00903   degenpivlim   The number of successive degenerate pivots required before
00904                 creating a restricted subproblem.
00905   degenlite     Controls secondary antidegeneracy --- `antidegen lite'
00906                   0: (pivotabort) break ties using |abar<kj>| and abort when
00907                      delta<j> = 0
00908                   1: (pivot) break ties using |abar<kj>| but always scan the
00909                      full basis
00910                   2: (alignobj) break ties by examining the alignment of the
00911                      hyperplane which will become tight on the pivot; choose
00912                      so that movement in the direction of the objective most
00913                      nearly lies in the hyperplane
00914                   3: (alignedge) break ties by examining the alignment of the
00915                      hyperplane which will become tight on the pivot; choose
00916                      so that the direction of motion defined by the entering
00917                      variable most nearly lies in the hyperplane.
00918                   4: (perpobj) break ties by examining the alignment of the
00919                      hyperplane which will become tight on the pivot; choose
00920                      so that the normal of the hyperplane is most nearly
00921                      aligned with the normal of the objective
00922                   5: (perpedge) break ties by examining the alignment of the
00923                      hyperplane which will become tight on the pivot; choose
00924                      so that the normal of the hyperplane is most nearly
00925                      aligned with the direction of motion
00926                 Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
00927   patch         TRUE to allow the code to patch a singular basis, FALSE to
00928                 prevent patching.
00929   copyorigsys   Controls whether dylp makes a local copy of the original
00930                 system. If set to TRUE, dylp will always make a local copy.
00931                 If set to FALSE, a copy will be made only if necessary.
00932                 Scaling will trigger a local copy.
00933   scaling       Controls whether dylp attempts to scale the original constraint
00934                 system for numeric stability.
00935                   0: scaling is forbidden
00936                   1: scale the original constraint system using numeric
00937                      scaling vectors attached to the system
00938                   2: evaluate the original constraint system and scale it if
00939                      necessary
00940                 Note that even if scaling = 0, dylp may install +/-1.0 scaling
00941                 vectors in order to flip >= constraints to <= constraints. See
00942                 comments in dy_scaling.c
00943   print         Substructure for picky printing control. For all print options,
00944                 a value of 0 suppresses all information messages.
00945     major         Controls printing of major phase information.
00946                   1: a message at each phase transition.
00947     scaling       Controls print level during initial evaluation and scaling of
00948                   the original constraint system.
00949                   1: start and finish messages
00950                   2: stability measures for original and scaled matrices;
00951                      adjustments to tolerances.
00952     setup         Controls print level while creating the initial constraint
00953                   system for dylp.
00954                   1: start and finish messages.
00955                   2: summary information about activated constraints
00956                   3: messages about each constraint included in the initial
00957                      system.
00958                   4: messages about each constraint processed for the initial
00959                      system
00960                   5: messages about each variable included in the initial
00961                      system.
00962                   6: lists value and status of inactive variables with
00963                      nonzero values
00964     crash         Controls print level while crashing the basis.
00965                   1: start & finish messages
00966                   2: summary counts for logicals, architecturals, artificials
00967                   3: a dump of the completed basis
00968                   4: detailed info on the selection of each architectural
00969                      and artificial variable
00970     pricing       Controls print level for pricing of columns (rows) in primal
00971                   (dual) simplex.
00972                   1: summary messages
00973                   2: lists candidate list and primal variable selected for
00974                      entry (exit) at each pivot
00975                   3: lists each variable as it's added to the candidate list
00976                      and again when reconsidered for pivoting
00977     pivoting      Controls print level for selection of the leaving (entering)
00978                   primal variable in primal (dual) simplex and updating of
00979                   variables.
00980                   1: prints result of leaving (entering) variable selection
00981                   2: information about the selection of the leaving (entering)
00982                      variable.
00983                   3: more information about the selection of the leaving
00984                      (entering) variable.
00985                   4: prints the pivot column (row) before and after
00986                      multiplication by the basis inverse, and yet more
00987                      pivot selection information.
00988                   5: prints a line for every candidate evaluated
00989     pivreject     Controls print level for information related to the operation
00990                   of the pivot rejection mechanism.
00991                   1: Prints a message for each row/column added to the pivot
00992                      rejection list, plus other major events.
00993                   2: Prints a message for each row/column removed from the
00994                      pivot rejection list.
00995     degen         Controls print level for information related to the operation
00996                   of the antidegeneracy mechanism.
00997                   1: prints a message each time the antidegeneracy level
00998                      changes
00999                   2: prints a message when a true degenerate pivot is taken
01000                      under duress
01001                   3: prints a message when a degenerate pivot is taken
01002                   4: prints anomalies as each degenerate set is formed and
01003                      backed out
01004                   5: prints details of each degenerate set as it's formed and
01005                      backed out
01006     phase1        Controls general print level for phase 1 of primal simplex.
01007                   1: messages about extraordinary events -- problem pivots, etc.
01008                   2: messages about 'routine' but infrequent events --
01009                      termination conditions, refactoring, unboundedness, etc.
01010                   3: messages with additional details of problems encountered
01011                   4: a one line log message is printed for each pivot
01012                   5: summary information about infeasible variables and phase
01013                      I objective coefficients; information about primal
01014                      variables updated at each pivot.
01015                   6: prints the primal variables after each pivot; prints
01016                      infeasible variables during phase I objective construction
01017                   7: prints the dual variables after each pivot; prints
01018                      infeasible variables during phase I objective modification
01019     phase2        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: prints the updated basic primal variables after each pivot
01026                   6: prints all basic primal variables after each pivot
01027                   7: prints the dual variables after each pivot.
01028     dual          Controls general print level for the dual simplex. As
01029                   phase2.
01030     basis         Controls print level in routines working with the basis.
01031                   1: summary warnings about problems: empty rows, singularity,
01032                      numerical instability, etc.
01033                   2: information about factoring failures and recovery actions
01034                   3: warnings about individual empty rows, details of column
01035                      replacement when patching a singular basis, pivot
01036                      tolerance adjustments; information about pivoting failures
01037                      and recovery actions
01038                   4: basis stability after factoring
01039                   5: basis stability after pivoting
01040     conmgmt       Controls print level while dylp is in the purge/generate/
01041                   activate constraint phases.
01042                   1: prints the number of constraints purged, generated,
01043                      & activated, and new size of constraint system.
01044                   2: prints a message for each constraint purged or activated.
01045                      (The cut generation routine is responsible for
01046                      handling this function when it generates cuts.)
01047                   3: additional details about refactoring and new values
01048                      of primal and dual variables.
01049                   4: prints a message about any variables affected as a side
01050                      effect of constraint changes, constraints processed
01051                      but not activated, and information about direction of
01052                      recession and relative angle of constraints when adding
01053                      constraints to an unbounded problem.
01054                   5: prints a running commentary on constraint and variable
01055                      shifts, inactive variables.
01056     varmgmt       Controls print level while dylp is in the purge/generate/
01057                   activate variable phases.
01058                   1: prints the number of variables purged, generated,
01059                      & activated, and new size of constraint system.
01060                   2: prints a message for each variable purged & activated.
01061                      (The column generation routine is responsible for
01062                      handling this function when it generates new variables).
01063                   3: prints a message about any constraints affected as a side
01064                      effect of variable changes, variables processed but not
01065                      activated, and information about direction of recession
01066                      and relative angle of dual constraints when adding
01067                      variables to an unbounded dual.
01068                   4: prints a running commentary on constraint and variable
01069                      shifts.
01070     force         Controls print level when dylp is attempting to force a
01071                   transition (primal -> dual, dual -> primal) or force the
01072                   use of the full constraint system.
01073                   1: prints a summary message giving the result of the
01074                      transition attempt
01075                   2: prints messages about actions taken for individual
01076                      constraints and variables.
01077                   3: additional information about variables and constraints
01078                      examined.
01079     tableau       Controls print level for routines that generate tableau
01080                   vectors (beta<i>, beta<j>, abar<i>, abar<j>) for use by
01081                   external clients.
01082                   1: prints summary messages about the circumstances
01083                   4: prints nonzeros in the final vector.
01084                   5: prints nonzeros in intermediate vectors and (dy_betaj,
01085                      dy_abarj only) inactive rows
01086                   6: prints nonzeros of active portion in internal reference
01087                      frame (dy_betaj only)
01088     rays          Controls print level for routines that generate primal
01089                   and dual rays for use by external clients.
01090                   1: prints summary messages about vectors found.
01091                   3: print information about columns / rows examined.
01092                   4: print information about why a column or row was rejected.
01093                   5: print nonzeros for each ray
01094     soln          Controls print level for routines that generate primal and
01095                   dual solutions for use by external clients.
01096                   1: prints summary messages about the circumstances
01097                   3: prints nonzeros in the final vector
01098                   4: prints nonzeros in intermediate vectors
01099 */
01100 
01101 typedef struct
01102 { cxtype_enum context ;
01103   int scan ;
01104   int iterlim ;
01105   int idlelim ;
01106   struct { int strat ;
01107            bool flex ;
01108            bool allownopiv ; } dpsel ;
01109   struct { int strat ; } ppsel ;
01110   int factor ;
01111   int check ;
01112   int groom ;
01113   struct { int actlvl ;
01114            int actlim ;
01115            int deactlvl ; } con ;
01116   int addvar ;
01117   int dualadd ;
01118   int coldvars ;
01119   bool forcecold ;
01120   bool forcewarm ;
01121   bool usedual ;
01122   bool degen ;
01123   int degenpivlim ;
01124   int degenlite ;
01125   bool patch ;
01126   bool fullsys ;
01127   bool copyorigsys ;
01128   int scaling ;
01129   struct { float vars ;
01130            float cons ; } active ;
01131   struct { double frac ;
01132            bool i1lopen ;
01133            double i1l ;
01134            bool i1uopen ;
01135            double i1u ;
01136            bool i2valid ;
01137            bool i2lopen ;
01138            double i2l ;
01139            bool i2uopen ;
01140            double i2u ; } initcons ;
01141   ibtype_enum coldbasis ;
01142   struct { bool cons ;
01143            bool vars ; } finpurge ;
01144   struct { bool d2p ;
01145            bool p2d ;
01146            bool flips ; } heroics ;
01147   struct { int major ;
01148            int scaling ;
01149            int setup ;
01150            int crash ;
01151            int pricing ;
01152            int pivoting ;
01153            int pivreject ;
01154            int degen ;
01155            int phase1 ;
01156            int phase2 ;
01157            int dual ;
01158            int basis ;
01159            int conmgmt ;
01160            int varmgmt ;
01161            int force ;
01162            int tableau ;
01163            int rays ;
01164            int soln ; } print ; } lpopts_struct ;
01165 
01166 
01167 
01168 
01169 /*
01170   Statistics structure, used to collect information about aspects of dylp
01171   operation beyond simple pivot counts. The data structure definition is
01172   always present, but to fill it you have to define DYLP_STATISTICS.
01173 
01174   Field         Definition
01175   -----         ----------
01176   phasecnts[dyDONE] Array with counts for number of times each phase is
01177                 executed.
01178   ini_simplex   The initial simplex phase
01179   cons          A set of arrays with data about individual constraints.
01180     sze           Allocated capacity of the arrays.
01181     angle         Angle to the objective function.
01182     actcnt        Number of times constraint is activated.
01183     deactcnt      Number of times constraint is deactivated.
01184     init          True if constraint is active in initial system.
01185     fin           True if constraint is active in final system.
01186   vars          A set of arrays with data about individual variables.
01187     sze           Allocated capacity of the arrays.
01188     actcnt        Number of times variable is activated.
01189     deactcnt      Number of times variable is deactivated.
01190   angle
01191     max         Maximum angle to the objective function over all constraints.
01192     min         Minimum angle to the objective function over all constraints.
01193     hist[*]     Histogram of angles of constraints to the objective function.
01194                 There are DYSTATS_HISTBINS bins. Currently, 37 bins: 36 bins
01195                 spanning 5 degrees of angle, and a dedicated 90 degree bin.
01196   
01197   factor        Tracks how well we're doing with respect to refactoring the
01198                 basis.
01199     cnt         Number of time the basis has been refactored.
01200     prevpiv     Pivot count at last refactorisation.
01201     avgpivs     Average number of pivots between basis refactorisations.
01202     maxpivs     Maximum number of pivots between basis refactorisations.
01203 
01204   pivrej        Statistics about the pivot rejection list and punts.
01205     max           maximum number of entries on the pivot rejection list
01206     mad           total number of entries attributed to mad pivots
01207     sing          total number of entries attributed to singular pivots
01208     pivtol_red    total number of times the pivot tolerance was reduced
01209     min_pivtol    the minimum pivot tolerance used
01210     puntcall      total number of calls to dealWithPunt
01211     puntret       total number of dyrPUNT returns recommended
01212 
01213   dmulti        Tracks the dual multipivot algorithm. All fields except cnt are
01214                 totals; divide by cnt to get averages.
01215     flippable     Number of flippable variables in the constraint system.
01216     cnt           Total calls to dualmultiin
01217     cands         Number of candidates queued for evaluation for entry
01218     promote       Number of calls that resulted in promoting a sane pivot
01219                   over an unstable pivot.
01220     nontrivial    Number of times that the initial scan and sort left
01221                   multiple candidates for further evaluation.
01222     evals         Actual number of candidates evaluated (ftran'd column)
01223     flips         Number of bound-to-bound flips performed
01224     pivrnk        Index in the list of candidates of the candidate finally
01225                   selected for pivoting.
01226     maxrnk        Maximum index selected for pivoting.
01227 
01228   pmulti        Tracks the primal multipivot algorithm.
01229     cnt           Total calls to primalmultiin
01230     cands         Number of candidates queued for evaluation to leave
01231     nontrivial    Number of times that the candidate list was sorted
01232     promote       Number of calls that resulted in promoting a sane pivot
01233                   over an unstable pivot.
01234   
01235   infeas        Statistics on resolution of infeasibility in primal phase I.
01236                 Basically, what we're interested in tracking is the number
01237                 of infeasible variables and the number of pivots between a
01238                 change in the number of infeasible variables. We're interested
01239                 in separating the case of 1 variable from 2 or more, because
01240                 the latter requires vastly more calculation. A little care
01241                 is required because phase I can run many times.
01242 
01243     prevpiv     The pivot count (tot.iters) at the previous change.
01244     maxcnt      The maximum number of infeasible variables encountered (this
01245                 is not strictly monotonic, as dylp may enter phase I many
01246                 times due to activating violated constraints).
01247     totpivs     The total number of pivots expended in phase I.
01248     maxpivs     The maximum number of pivots with no change in the number of
01249                 feasible variables.
01250     chgcnt1     The number of times that the number of infeasible variables
01251                 changed and reduced costs did not have to be recalculated
01252                 (specifically, exactly one variable became feasible, and it
01253                 left the basis as it did so).
01254     chgcnt2     The number of times that the number of infeasible variables
01255                 changed in such a way as to require recalculation of the
01256                 reduced costs.
01257 
01258   [dp]degen[*]  Array of stats for each restricted subproblem nesting level,
01259                 with separate arrays for dual (ddegen) and primal (pdegen).
01260                 degen[0].cnt is used to hold the maximum nesting level.
01261     cnt         Number of times this nesting level was entered.
01262     avgsiz      The average number of variables in a restricted subproblem.
01263                 Kept by iterative update, as avg<k+1> = (avg<k>*k+size)/(k+1).
01264                 Suffers from cumulative loss of accuracy, but it'll do for
01265                 our purposes.
01266     maxsiz      The maximum number of variables in a restricted subproblem.
01267     totpivs     Total number of pivots at or above this nesting level.
01268     avgpivs     Average number of pivots at or above this nesting level.
01269     maxpivs     Maximum number of pivots for any one instance at or above
01270                 this nesting level.
01271 
01272   tot, p1, p2, d2       Iteration and pivot counts, total and for each
01273                         individual phase. These are copied over from
01274                         dy_lp (lp_struct) at the end of the run, so that
01275                         they can be printed by dumpstats.
01276   
01277   DYSTATS_MAXDEGEN is the maximum number of levels of nesting accommodated by
01278   antidegeneracy statistics and debugging structures. The actual algorithm
01279   has no inherent limitation.
01280 
01281   DYSTATS_HISTBINS is the number of bins for constraint angles. It should be an
01282   odd number. Each bin will span 180/(DYSTATS_HISTBINS-1) degrees, with the
01283   final bin reserved for constraints at 90 degrees. For example, a value of 37
01284   gives 180/(37-1) = 5 degrees per bin.
01285 */
01286 
01287 #define DYSTATS_MAXDEGEN 25
01288 #define DYSTATS_HISTBINS 37
01289 
01290 typedef struct {
01291   int phasecnts[dyDONE+1] ;
01292   dyphase_enum ini_simplex ;
01293   struct { int sze ;
01294            double *angle ;
01295            int *actcnt ;
01296            int *deactcnt ;
01297            bool *init ;
01298            bool *fin ; } cons ;
01299   struct { int sze ;
01300            int *actcnt ;
01301            int *deactcnt ; } vars ;
01302   struct { float max ;
01303            float min ;
01304            int hist[DYSTATS_HISTBINS] ; } angle ;
01305   struct { int cnt ;
01306            int prevpiv ;
01307            float avgpivs ;
01308            int maxpivs ; } factor ;
01309   struct { int max ;
01310            int mad ;
01311            int sing ;
01312            int pivtol_red ;
01313            double min_pivtol ;
01314            int puntcall ;
01315            int puntret ; } pivrej ;
01316   struct { int flippable ;
01317            int cnt ;
01318            int cands ;
01319            int promote ;
01320            int nontrivial ;
01321            int evals ;
01322            int flips ;
01323            int pivrnks ;
01324            int maxrnk ; } dmulti ;
01325   struct { int cnt ;
01326            int cands ;
01327            int nontrivial ;
01328            int promote ; } pmulti ;
01329   struct { int prevpiv ;
01330            int maxcnt ;
01331            int totpivs ;
01332            int maxpivs ;
01333            int chgcnt1 ;
01334            int chgcnt2 ; } infeas ;
01335   struct { int cnt ;
01336            float avgsiz ;
01337            int maxsiz ;
01338            int totpivs ;
01339            float avgpivs ;
01340            int maxpivs ; } pdegen[DYSTATS_MAXDEGEN] ;
01341   struct { int cnt ;
01342            float avgsiz ;
01343            int maxsiz ;
01344            int totpivs ;
01345            float avgpivs ;
01346            int maxpivs ; } ddegen[DYSTATS_MAXDEGEN] ;
01347   struct { int iters ;
01348            int pivs ; } tot ;
01349   struct { int iters ;
01350            int pivs ; } p1 ;
01351   struct { int iters ;
01352            int pivs ; } p2 ;
01353   struct { int iters ;
01354            int pivs ; } d2 ; } lpstats_struct ;
01355 
01356 
01357 
01358 #ifdef DYLP_INTERNAL
01359 
01360 /*
01361   Macros to determine whether a constraint or variable is active, and whether
01362   it's eligible for activation. Coding is explained below for dy_origcons and
01363   dy_origvars. The main purpose served by these macros is to make it easy to
01364   find activiation/deactivation points in the code, should the conventions ever
01365   change.
01366 */
01367 
01368 #define ACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] > 0)
01369 #define INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] <= 0)
01370 #define LOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] == 0)
01371 #define MARK_UNLOADABLE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = -1)
01372 #define MARK_INACTIVE_CON(zz_cndx_zz) (dy_origcons[(zz_cndx_zz)] = 0)
01373 
01374 #define ACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] > 0)
01375 #define INACTIVE_VAR(zz_vndx_zz) (dy_origvars[(zz_vndx_zz)] <= 0)
01376 #define LOADABLE_VAR(zz_vndx_zz) \
01377   ((dy_origvars[(zz_vndx_zz)] < 0) && \
01378    flgoff(((flags) -dy_origvars[(zz_vndx_zz)]),vstatNOLOAD|vstatNBFX))
01379 #define MARK_INACTIVE_VAR(zz_vndx_zz,zz_val_zz) \
01380   (dy_origvars[(zz_vndx_zz)] = (zz_val_zz))
01381 
01382 
01383 /*
01384   dy_logchn             i/o id for the execution log file
01385   dy_gtxecho            controls echoing of generated text to stdout
01386 */
01387 
01388 extern ioid dy_logchn ;
01389 extern bool dy_gtxecho ;
01390 
01391 
01392 /*
01393   lp_struct
01394 
01395   This structure is the control structure for an LP problem within dylp.
01396 
01397   Field         Definition
01398   -----         ----------
01399   phase         Current phase of the dynamic simplex algorithm.
01400   lpret         Return code from the most recent simplex execution.
01401 
01402   z             Value of the objective function (includes inactzcorr).
01403   inactzcorr    Correction to the objective function due to inactive variables
01404                 with non-zero values.
01405 
01406   simplex       Simplex algorithm status and control
01407     active        currently active or most recently completed
01408     next          currently active or to be started
01409     init_pse      TRUE if the PSE structures need to be reinitialised,
01410                   FALSE otherwise
01411     init_dse      TRUE if the DSE structures need to be reinitialised,
01412                   FALSE otherwise
01413                 These fields are used to determine when to update or
01414                 reinitialise the PSE and DSE data structures. Active and next
01415                 must be valid during the purge/gen/add variable/constraint
01416                 cycles.
01417 
01418                 A word on infeas and infeascnt: They are guaranteed accurate
01419                 only immediately after initialisation and following a primal
01420                 feasibility check.
01421 
01422   infeas        Total infeasibility = SUM{j} max(0,x<j>-ub<j>,lb<j>-x<j>)
01423   infeascnt     The number of infeasible variables; refreshed when dy_accchk
01424                 is asked to do a primal feasibility check.
01425 
01426   ubnd          Substructure for information on unbounded or pseudo-unbounded
01427                 problems.
01428     ndx           The index of the variable fingered for causing unboundedness
01429                   or pseudo-unboundedness (swing).
01430     ratio         The growth ratio.
01431 
01432   p1obj         The following fields relate to handling of the phase I
01433                 objective function.
01434     installed   TRUE if the phase I objective is currently installed
01435     infcnt      Tracks the number of variables incorporated in p1obj which
01436                 remain infeasible.
01437     infvars_sze Allocated size of the infvars vector.
01438     infvars     Vector of indices of infeasible variables incorporated in the
01439                 phase I objective.
01440     p1obj       Pointer to the phase I objective (temporary storage while
01441                 the phase II objective is installed).
01442     p2obj       Pointer to the phase II objective (temporary storage while
01443                 the phase I objective is installed).
01444   
01445                 A word on pivot and iteration counts: Iteration counts tally
01446                 iterations of the pivoting loop, successful or not. Pivot
01447                 counts tally successful bound-to-bound or change-of-basis
01448                 pivots. Pretty much all messages will give tot.iters, so that
01449                 it's possible to track the progress of an LP. Iterf has an
01450                 entirely different function -- it's tracking the accumulation
01451                 of eta matrices in the basis representation.
01452 
01453   sys           Substructure for dynamic system modification status.
01454     forcedfull    Set to TRUE if the full system has been forced in state
01455                   dyFORCEFULL. This should happen at most once, so if we
01456                   enter dyFORCEFULL and forcedfull == TRUE, it's fatal.
01457     cons
01458       loadable    Count of constraints which could be activated
01459       unloadable  Count of constraints which are ineligible for activation
01460                   (empty constraints and nonbinding rows)
01461     vars
01462       loadable    Count of variables which could be activated
01463       unloadable  Count of variables which are ineligible for activation
01464                   (nonbasic fixed)
01465 
01466   tot           Total simplex iterations and pivots, all phases
01467     iters
01468     pivs
01469   p1            Primal phase I iterations and pivots.
01470     iters
01471     pivs
01472   p2            Primal phase II iterations and pivots.
01473     iters
01474     pivs
01475   d2            Dual phase II iterations and pivots.
01476     iters
01477     pivs
01478 
01479   pivok         Set to TRUE in dy_{primal|dual}pivot if the current iteration
01480                 is a  successful pivot. Cleared to FALSE at the head of
01481                 dy_duenna.
01482   prev_pivok    Set to pivok at head of dy_duenna. Provides status of just
01483                 completed pivot for post-Duenna decisions.
01484 
01485   basis         Various fields related to basis change, refactoring, etc.
01486 
01487     etas        The number of basis changes (hence eta matrices) since the
01488                 the basis was last factored. Used to schedule periodic
01489                 factoring of the basis. Reset to 0 each time the basis is
01490                 factored.
01491     pivs        The number of basis pivots since entry into a primal or dual
01492                 simplex phase (excludes bound-to-bound simplex `pivots').
01493                 Used when deciding whether to remove variables from the pivot
01494                 reject list, and whether to pop out of a simplex phase due to
01495                 excessive swing.
01496     dinf        Number of successive refactors with dual infeasibility.
01497                 Cleared at the start of a simplex phase.
01498                 Incremented/cleared in dy_accchk iff a dual feasibility check
01499                 is performed.
01500 
01501   degen         Activation level of antidegeneracy algorithm. Held at 0 when
01502                 the antidegeneracy algorithm is not active. Incremented each
01503                 time a restricted subproblem is formed, and decremented when
01504                 the restriction is backed out. (Values > 1 indicate that
01505                 degeneracy recurred while working on a restricted subproblem,
01506                 resulting in further restriction.)
01507   degenpivcnt   The number of successive degenerate pivots.
01508 
01509   idlecnt       The number of cycles since the objective has changed.
01510 
01511   lastz         Previous objective value for various activities; used to
01512                 detect and suppress loops.
01513     piv           Objective at last pivot (detects stalling)
01514     cd            Objective at last entry into constraint deactivation
01515                   (dyPURGECON) (detects constraint activate/deactivate loops)
01516     vd            Objective at last entry into variable deactivation
01517                   (dyPURGEVAR) (detects variable activate/deactivate loops)
01518     fp            Objective at last entry into force primal (dyFORCEPRIMAL)
01519                   (detects constraint activate/deactivate loops)
01520     fd            Objective at last entry into force dual (dyFORCEDUAL)
01521                   (detects variable activate/deactivate loops)
01522 
01523   prim          Primal variable information
01524     norm1         1-norm of basic primal variables inv(B)b
01525     norm2         2-norm of basic primal variables
01526     max           inf-norm (max) of basic primal variables
01527     maxndx        index of max primal variable
01528 
01529   dual          Dual variable information
01530     norm1         1-norm of dual variables c<B>inv(B)
01531     norm2         2-norm of dual variables
01532     max           inf-norm (max) of dual variables
01533     maxndx        index of max dual variable
01534 
01535 */
01536 
01537 typedef struct
01538 { dyphase_enum phase ;
01539   lpret_enum lpret ;
01540   double z ;
01541   double inactzcorr ;
01542   struct { dyphase_enum active ;
01543            dyphase_enum next ;
01544            bool init_pse ;
01545            bool init_dse ; } simplex ;
01546   double infeas ;
01547   int infeascnt ;
01548   struct { int ndx ;
01549            double ratio ; } ubnd ;
01550   struct { bool installed ;
01551            int infcnt ;
01552            int infvars_sze ;
01553            int *infvars ;
01554            double *p1obj ;
01555            double *p2obj ; } p1obj ;
01556   struct { struct { int loadable ;
01557                     int unloadable ; } cons ;
01558            struct { int loadable ;
01559                     int unloadable ; } vars ;
01560            bool forcedfull ; } sys ;
01561   struct { int iters ;
01562            int pivs ; } tot ;
01563   struct { int iters ;
01564            int pivs ; } p1 ;
01565   struct { int iters ;
01566            int pivs ; } p2 ;
01567   struct { int iters ;
01568            int pivs ; } d2 ;
01569   bool pivok ;
01570   bool prev_pivok ;
01571   struct { int etas ;
01572            int pivs ;
01573            int dinf ; } basis ;
01574   int degen ;
01575   int degenpivcnt ;
01576   int idlecnt ;
01577   struct { double piv ;
01578            double cd ;
01579            double vd ;
01580            double fp ;
01581            double fd ; } lastz ;
01582   struct { double norm1 ;
01583            double norm2 ;
01584            double max ;
01585            int maxndx ; } prim ;
01586   struct { double norm1 ;
01587            double norm2 ;
01588            double max ;
01589            int maxndx ; } dual ;
01590   } lp_struct ;
01591 
01592 
01593 /*
01594   Declarations global to the dylp implementation but not visible outside of
01595   it. With this we can avoid passing huge numbers of parameters and/or
01596   unpacking a structure on a regular basis. Unless otherwise indicated, indices
01597   are in the dy_sys (active system) frame of reference.
01598 
01599   dy_retained   TRUE if dylp thinks that the structures below are valid, FALSE
01600                 otherwise.
01601 
01602   Main structures
01603   ---------------
01604   dy_lp:        The lp control structure for dylp.
01605   dy_sys:       The active constraint system; initialised in dylp:startup
01606   dy_tols:      Tolerances in effect for dylp; initialised in
01607                 dylp:dylp from orig_tols.
01608   dy_opts:      Options in effect for dylp; initialised in
01609                 dylp:dylp to point to same structure as orig_opts.
01610   dy_stats      Statistics structure for dylp; initialised in dylp:dylp to
01611                 point ot the same structure as orig_stats.
01612 
01613   Constraint & Variable Management
01614   --------------------------------
01615   dy_actvars:   The active variables. Indexed in dy_sys frame, contains
01616                 indices in orig_sys frame. Attached to dy_sys.
01617                 Entries for logical variables (1 <= j <= concnt) are
01618                 meaningless.
01619   dy_actcons:   The active constraints. Indexed in dy_sys frame, contains
01620                 indices in orig_sys frame. Attached to dy_sys.
01621   dy_origvars:  Status of the original architectural variables.
01622                  * A value of 0 indicates the entry hasn't been processed.
01623                    Should never happen.
01624                  * If the variable is active, the entry contains the index
01625                    of the variable in the dy_sys frame.
01626                  * If the variable is inactive, the coding is the negative of
01627                    the vstat flags, limited to the nonbasic status values
01628                    vstatNBFR, vstatNBFX, vstatNBLB, or vstatNBUB, and the
01629                    qualifier vstatNOLOAD.
01630                 Indexed in orig_sys frame. Attached to orig_sys.
01631   dy_origcons:  Status of the original constraints.
01632                  * If the constraint is active, the entry contains the index
01633                    of the constraint in the dy_sys frame.
01634                  * If the constraint is inactive, contains 0.
01635                  * If the constraint cannot be activated, contains a negative
01636                    value.
01637                 Indexed in orig_sys frame. Attached to orig_sys.
01638 
01639   Note that there are macros defined to test whether a variable or constraint
01640   is inactive, and whether it's eligible for activation. Use them!
01641   
01642   Basis Management
01643   ----------------
01644   dy_basis:     The basis vector. Indexed by basis position, attached to
01645                 dy_sys.
01646   dy_var2basis: Translates a variable index to a basis pos'n. Indexed by
01647                 column, attached to dy_sys. Entries for nonbasic variables
01648                 must be kept at 0.
01649   dy_status:    The status vector. Indexed by column, attached to dy_sys.
01650   
01651   Primal and Dual Variables
01652   -------------------------
01653   dy_x:         The values of all primal variables. Indexed by column,
01654                 attached to dy_sys. Values of nonbasic variables must always
01655                 be correct (to allow uniform handling of normal nonbasic
01656                 variables and superbasic variables). Values of basic
01657                 variables will retain unperturbed values while the
01658                 antidegeneracy mechanism is active -- this allows the
01659                 perturbation to be quickly backed out.
01660   dy_xbasic:    The values of the basic variables. Indexed by basis pos'n,
01661                 attached to dy_sys.
01662   dy_y:         The dual variables. Indexed by basis pos'n, attached to
01663                 dy_sys.
01664 
01665   Projected Steepest Edge (PSE) Pricing
01666   -------------------------------------
01667   dy_cbar:      Iteratively updated vector of reduced costs. Indexed by column,
01668                 attached to dy_sys.
01669   dy_gamma:     Iteratively updated vector of column norms ||abar<j>||^2.
01670                 Indexed by column, attached to dy_sys.
01671   dy_frame:     Boolean vector which indicates if a given variable is in the
01672                 current frame of reference. Indexed by column, attached to
01673                 dy_sys.
01674   
01675   Dual Steepest Edge (DSE) Pricing
01676   --------------------------------
01677   dy_rho:       Iteratively updated vector of row norms ||beta<i>||^2.
01678                 Indexed by basis position, attached to dy_sys.
01679 
01680   DSE pricing also makes use of dy_xbasic (the reduced costs of the dual
01681   variables), and maintains dy_cbar.
01682   
01683   Antidegeneracy
01684   --------------
01685   dy_brkout:    Specifies the direction a variable needs to move to escape
01686                 from a degenerate vertex.  Indexed by basis pos'n, attached
01687                 to dy_sys.
01688   dy_degenset:  Specifies the set of constraints (equivalently, basic
01689                 variables) perturbed at each level of the antidegeneracy
01690                 algorithm. Indexed by basis pos'n, attached to dy_sys.  The
01691                 entry for a constraint is the highest level of degenerate set
01692                 which includes the constraint. If the entry is 0, the
01693                 constraint is not involved in degeneracy.
01694   dy_ddegenset: Specifies the set of dual constraints (equivalently, reduced
01695                 costs) perturbed at each level of the antidegeneracy
01696                 algorithm. Indexed by variable index, attached to dy_sys.
01697                 The entry for a dual constraint is the highest level of
01698                 degenerate set which includes the constraint. If the entry is
01699                 0, the constraint is not involved in degeneracy.
01700 */
01701 
01702 extern bool dy_retained ;
01703 
01704 extern lp_struct *dy_lp ;
01705 extern consys_struct *dy_sys ;
01706 extern lptols_struct *dy_tols ;
01707 extern lpopts_struct *dy_opts ;
01708 extern int *dy_actvars,*dy_actcons,*dy_origvars,*dy_origcons,
01709            *dy_basis,*dy_var2basis,
01710            *dy_brkout,*dy_degenset,*dy_ddegenset ;
01711 extern flags *dy_status ;
01712 extern double *dy_x,*dy_xbasic,*dy_y,*dy_cbar,*dy_gamma,*dy_rho ;
01713 extern bool *dy_frame ;
01714 
01715 extern lpstats_struct *dy_stats ;
01716 
01717 /*
01718   dy_scaling.c
01719 */
01720 
01721 extern bool dy_initlclsystem(lpprob_struct *orig_lp, bool hotstart) ;
01722 extern void dy_freelclsystem(lpprob_struct *orig_lp, bool freesys) ;
01723 extern bool dy_isscaled(void) ;
01724 extern void dy_scaling_vectors(const double **rscale, const double **cscale) ;
01725 extern consys_struct *dy_scaled_origsys() ;
01726 
01727 /*
01728   dy_coldstart.c
01729 */
01730 
01731 extern dyret_enum dy_coldstart(consys_struct *orig_sys),
01732                   dy_crash(void) ;
01733 
01734 /*
01735   dy_warmstart.c
01736 */
01737 
01738 extern dyret_enum dy_warmstart(lpprob_struct *orig_lp) ;
01739 
01740 /*
01741   dy_hotstart.c
01742 */
01743 
01744 extern dyret_enum dy_hotstart(lpprob_struct *orig_lp) ;
01745 
01746 /*
01747   dy_basis.c
01748 */
01749 
01750 extern dyret_enum dy_factor(flags *calcflgs),
01751                   dy_pivot(int xipos, double abarij, double maxabarj) ;
01752 extern double dy_chkpiv(double abarij, double maxabarj) ;
01753 extern void dy_btran(double *col), dy_ftran(double *col, bool save) ;
01754 extern bool dy_setpivparms(int curdelta, int mindelta) ;
01755 extern char *dy_prtpivparms(int lvl) ;
01756 
01757 /*
01758   dy_bound.c
01759 */
01760 
01761 extern int dy_activateBndCons(consys_struct *orig_sys) ;
01762 extern int dy_dualaddvars(consys_struct *orig_sys) ;
01763 
01764 /*
01765   dy_conmgmt.c
01766 */
01767 
01768 extern bool dy_loadcon(consys_struct *orig_sys, int orig_ndx,
01769                        bool genvars, int *inactndxs) ;
01770 extern bool dy_deactNBLogPrimCon(consys_struct *orig_sys, int i),
01771             dy_deactBLogPrimCon(consys_struct *orig_sys, int i),
01772             dy_actBLogPrimCon(consys_struct *orig_sys, int i,
01773                               int *inactvars),
01774             dy_actBLogPrimConList(consys_struct *orig_sys,
01775                                   int cnt, int *ocndxs, int **inactvars) ;
01776 extern int dy_deactivateCons(consys_struct *orig_sys),
01777            dy_activateCons(consys_struct *orig_sys, bool with_vars) ;
01778 
01779 /*
01780   dy_varmgmt.c
01781 */
01782 
01783 extern bool dy_actNBPrimArch(consys_struct *orig_sys, int ovndx),
01784             dy_actNBPrimArchList(consys_struct *orig_sys,
01785                                  int cnt, int *ovndxs),
01786             dy_deactBPrimArch(consys_struct *orig_sys, int ovndx),
01787             dy_deactNBPrimArch(consys_struct *orig_sys, int ovndx) ;
01788 extern int dy_deactivateVars(consys_struct *orig_sys),
01789            dy_activateVars(consys_struct *orig_sys, int *candidates) ;
01790 
01791 /*
01792   dy_primalpivot.c
01793 */
01794 
01795 extern dyret_enum dy_primalin(int initcol, int scan, int *xjndx, int *nextcol),
01796                   dy_primalpivot(int xjndx, int indir, int *xindx, int *outdir,
01797                                  double *abarij, double *delta, int *xjcand),
01798                   dy_degenout(int level) ;
01799 
01800 /*
01801   dy_duenna.c
01802 */
01803 
01804 extern dyret_enum dy_duenna(dyret_enum pivresult, int xjndx, int xindx,
01805                             int xjcand, int xicand),
01806                   dy_accchk(flags *checks) ;
01807 
01808 /*
01809   dy_pivreject.c
01810 */
01811 
01812 extern dyret_enum dy_addtopivrej(int xkndx, dyret_enum why,
01813                                  double abarij, double maxabarij),
01814                   dy_dealWithPunt(void) ;
01815 extern bool dy_clrpivrej(int *entries) ;
01816 extern void dy_checkpivtol(void) ;
01817 extern void dy_initpivrej(int sze), dy_freepivrej(void) ;
01818 
01819 
01820 /*
01821   dy_primal.c
01822 */
01823 
01824 extern lpret_enum dy_primal(void) ;
01825 extern bool dy_initp1obj(void),dy_swapobjs(dyphase_enum phase) ; 
01826 
01827 /*
01828   dy_dualpivot.c
01829 */
01830 
01831 extern dyret_enum
01832   dy_dualout(int *xindx),
01833   dy_dualpivot(int xindx, int outdir,
01834                int *p_xjndx, int *p_indir, double *p_cbarj,
01835                double *p_abarij, double *p_delta, int *xicand),
01836   dy_dualdegenout(int level) ;
01837 
01838 /*
01839   dy_dual.c
01840 */
01841 
01842 extern lpret_enum dy_dual(void) ;
01843 
01844 #endif /* DYLP_INTERNAL */
01845 
01846 /*
01847   dy_setup.c
01848 */
01849 
01850 extern void dy_defaults(lpopts_struct **opts, lptols_struct **tols),
01851             dy_checkdefaults(consys_struct *sys,
01852                              lpopts_struct *opts, lptols_struct *tols),
01853             dy_setprintopts(int lvl, lpopts_struct *opts) ;
01854 
01855 
01856 /*
01857   dylp.c
01858 */
01859 
01860 extern lpret_enum dylp(lpprob_struct *orig_lp, lpopts_struct *orig_opts,
01861                        lptols_struct *orig_tols, lpstats_struct *orig_stats) ;
01862 
01863 /*
01864   dylp_utils.c
01865 */
01866 
01867 #ifdef DYLP_INTERNAL
01868 
01869 extern lpret_enum dyret2lpret(dyret_enum dyret) ;
01870 extern dyret_enum dy_updateprimals(int j, double deltaj, double *p_abarj) ;
01871 extern bool dy_reducerhs(double *rhs, bool init),
01872             dy_calcprimals(void),dy_calccbar(void) ;
01873 extern void dy_calcduals(void),dy_setbasicstatus(void),
01874             dy_dseinit(void),dy_pseinit(void) ;
01875 extern double dy_calcobj(void),dy_calcdualobj(void),dy_calcpinfeas(void) ;
01876 extern void dy_finishup(lpprob_struct *orig_lp, dyphase_enum phase) ;
01877 
01878 #ifdef DYLP_PARANOIA
01879 
01880 extern bool dy_chkstatus(int vndx),
01881             dy_chkdysys(consys_struct *orig_sys) ;
01882 extern void dy_chkdual(int lvl) ;
01883 
01884 #endif
01885 
01886 #endif /* DYLP_INTERNAL */
01887 
01888 extern bool dy_dupbasis(int dst_basissze, basis_struct **p_dst_basis,
01889                         basis_struct *src_basis, int dst_statussze,
01890                         flags **p_dst_status,
01891                         int src_statuslen, flags *src_status) ;
01892 extern void dy_freesoln(lpprob_struct *lpprob) ;
01893 
01894 /*
01895   dy_penalty.c
01896 */
01897 
01898 extern bool dy_pricenbvars(lpprob_struct *orig_lp, flags priceme,
01899                            double **p_ocbar, int *p_nbcnt, int **p_nbvars),
01900             dy_pricedualpiv(lpprob_struct *orig_lp, int oxindx,
01901                             double nubi, double xi, double nlbi,
01902                             int nbcnt, int *nbvars,
01903                             double *cbar, double *p_upeni, double *p_dpeni) ;
01904 
01905 /*
01906   dy_tableau.c
01907 */
01908 
01909 extern bool dy_abarj(lpprob_struct *orig_lp, int tgt_j, double **p_abarj) ;
01910 extern bool dy_betaj(lpprob_struct *orig_lp, int tgt_j, double **p_betaj) ;
01911 extern bool dy_betai(lpprob_struct *orig_lp, int tgt_i, double **p_betai) ;
01912 extern bool dy_abari(lpprob_struct *orig_lp, int tgt_i, double **p_abari,
01913                      double **p_betai) ;
01914 
01915 /*
01916   dy_rays.c
01917 */
01918 
01919 extern bool dy_primalRays(lpprob_struct *orig_lp,
01920                           int *p_numRays, double ***p_rays) ;
01921 extern bool dy_dualRays(lpprob_struct *orig_lp, bool fullRay,
01922                         int *p_numRays, double ***p_rays, bool trueDuals) ;
01923 
01924 /*
01925   dy_solutions.c
01926 */
01927 
01928 extern void dy_colDuals(lpprob_struct *orig_lp, double **p_cbar,
01929                         bool trueDuals) ;
01930 extern void dy_rowDuals(lpprob_struct *orig_lp, double **p_y,
01931                         bool trueDuals) ;
01932 
01933 extern void dy_colPrimals(lpprob_struct *orig_lp, double **p_x) ;
01934 extern void dy_rowPrimals(lpprob_struct *orig_lp,
01935                           double **p_xB, int **p_indB) ;
01936 extern void dy_logPrimals(lpprob_struct *orig_lp, double **p_logx) ;
01937 
01938 extern void dy_colStatus(lpprob_struct *orig_lp, flags **p_colstat) ;
01939 extern void dy_logStatus(lpprob_struct *orig_lp, flags **p_logstat) ;
01940 
01941 extern bool dy_expandxopt(lpprob_struct *lp, double **p_xopt) ;
01942 
01943 /*
01944   dylp_io.c
01945 */
01946 
01947 #include <dylib_io.h>
01948 
01949 #ifdef DYLP_INTERNAL
01950 
01951 extern void dy_logpivot(dyret_enum result, int xjndx, int indir, double cbarj,
01952                         int xindx, int outdir, double abarij, double delta) ;
01953 extern const char *dy_prtdyret(dyret_enum retcode) ;
01954 
01955 #endif /* DYLP_INTERNAL */
01956 
01957 extern const char *dy_prtlpret(lpret_enum lpret),
01958                   *dy_prtlpphase(dyphase_enum phase, bool abbrv) ;
01959 extern char *dy_prtvstat(flags status) ;
01960 extern bool dy_dumpcompact(ioid chn, bool echo, lpprob_struct *soln,
01961                            bool nbzeros) ;
01962 
01963 /*
01964   dy_statistics.c
01965 
01966   These routines are compiled unconditionally, but note that the compile-time
01967   symbol DYLP_STATISTICS must be defined before dylp will actually take the
01968   time to collect detailed statistics. See dy_statistics.c for additional
01969   instructions.
01970 */
01971 
01972 extern void dy_initstats(lpstats_struct **p_lpstats, consys_struct *orig_sys),
01973             dy_dumpstats(ioid chn, bool echo, lpstats_struct *lpstats,
01974                          consys_struct *orig_sys),
01975             dy_freestats(lpstats_struct **p_lpstats) ;
01976 
01977 #ifdef DYLP_INTERNAL
01978 
01979 extern void dy_finalstats(lpstats_struct *lpstats) ;
01980 
01981 #endif /* DYLP_INTERNAL */
01982 
01983 
01984 #endif /* _DYLP_H */

Generated on Sat Oct 16 2010 02:43:37 by  doxygen 1.7.1