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