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