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