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