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