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