1
2 /* Routines located in lp_BFP1.cpp; common for all factorization engines */
3 /* Cfr. lp_BFP.h for definitions */
4 /* ---------------------------------------------------------------------------------- */
5 /* Changes: */
6 /* 29 May 2004 Corrected calculation of bfp_efficiency(), which required */
7 /* modifying the max_Bsize to include slack variables. KE. */
8 /* 16 June 2004 Make the symbolic minimum degree ordering routine available */
9 /* to BFPs as a routine internal to the library. KE */
10 /* 1 July 2004 Change due to change in MDO naming. */
11 /* ---------------------------------------------------------------------------------- */
12
13
14 /* MUST MODIFY */
bfp_compatible(lprec * lp,int bfpversion,int lpversion,int sizeofvar)15 MYBOOL BFP_CALLMODEL bfp_compatible(lprec *lp, int bfpversion, int lpversion, int sizeofvar)
16 {
17 MYBOOL status = FALSE;
18
19 if((lp != NULL) && (bfpversion == BFPVERSION) && (sizeof(REAL) == sizeofvar)) {
20 #if 0
21 if(lpversion == MAJORVERSION) /* Forces BFP renewal at lp_solve major version changes */
22 #endif
23 status = TRUE;
24 }
25 return( status );
26 }
27
28 /* DON'T MODIFY */
bfp_status(lprec * lp)29 int BFP_CALLMODEL bfp_status(lprec *lp)
30 {
31 return(lp->invB->status);
32 }
33
34 /* DON'T MODIFY */
bfp_indexbase(lprec * lp)35 int BFP_CALLMODEL bfp_indexbase(lprec *lp)
36 {
37 return( MATINDEXBASE );
38 }
39
40 /* DON'T MODIFY */
bfp_rowoffset(lprec * lp)41 int BFP_CALLMODEL bfp_rowoffset(lprec *lp)
42 {
43 if(lp->obj_in_basis)
44 return( 1 );
45 else
46 return( 0 );
47 }
48
49 /* DON'T MODIFY */
bfp_pivotmax(lprec * lp)50 int BFP_CALLMODEL bfp_pivotmax(lprec *lp)
51 {
52 if(lp->max_pivots > 0)
53 return( lp->max_pivots );
54 else
55 return( DEF_MAXPIVOT );
56 }
57
58 /* DON'T MODIFY */
bfp_pivotvector(lprec * lp)59 REAL * BFP_CALLMODEL bfp_pivotvector(lprec *lp)
60 {
61 return( lp->invB->pcol );
62 }
63
64 /* DON'T MODIFY */
bfp_efficiency(lprec * lp)65 REAL BFP_CALLMODEL bfp_efficiency(lprec *lp)
66 {
67 REAL hold;
68
69 hold = lp->bfp_nonzeros(lp, AUTOMATIC);
70 if(hold == 0)
71 hold = 1 + lp->rows;
72 hold = lp->bfp_nonzeros(lp, TRUE)/hold;
73
74 return(hold);
75 }
76
77 /* DON'T MODIFY */
bfp_pivotcount(lprec * lp)78 int BFP_CALLMODEL bfp_pivotcount(lprec *lp)
79 {
80 return(lp->invB->num_pivots);
81 }
82
83
84 /* DON'T MODIFY */
bfp_refactcount(lprec * lp,int kind)85 int BFP_CALLMODEL bfp_refactcount(lprec *lp, int kind)
86 {
87 if(kind == BFP_STAT_REFACT_TOTAL)
88 return(lp->invB->num_refact);
89 else if(kind == BFP_STAT_REFACT_TIMED)
90 return(lp->invB->num_timed_refact);
91 else if(kind == BFP_STAT_REFACT_DENSE)
92 return(lp->invB->num_dense_refact);
93 else
94 return( BFP_STAT_ERROR );
95 }
96
97 /* DON'T MODIFY */
bfp_mustrefactorize(lprec * lp)98 MYBOOL BFP_CALLMODEL bfp_mustrefactorize(lprec *lp)
99 {
100 MYBOOL test = lp->is_action(lp->spx_action, ACTION_REINVERT | ACTION_TIMEDREINVERT);
101 if(!test) {
102 REAL f;
103 INVrec *lu = lp->invB;
104
105 if(lu->num_pivots > 0)
106 f = (timeNow()-lu->time_refactstart) / (REAL) lu->num_pivots;
107 else
108 f = 0;
109
110 /* Always refactorize if we are above the set pivot limit */
111 if(lu->force_refact ||
112 (lu->num_pivots >= lp->bfp_pivotmax(lp)))
113 lp->set_action(&lp->spx_action, ACTION_REINVERT);
114
115 /* Check if we should do an optimal time-based refactorization */
116 else if(lu->timed_refact && (lu->num_pivots > 1) &&
117 (f > MIN_TIMEPIVOT) && (f > lu->time_refactnext)) {
118 /* If we have excessive time usage in automatic mode then
119 treat as untimed case and update optimal time metric, ... */
120 if((lu->timed_refact == AUTOMATIC) &&
121 (lu->num_pivots < 0.4*lp->bfp_pivotmax(lp)))
122 lu->time_refactnext = f;
123 /* ... otherwise set flag for the optimal time-based refactorization */
124 else
125 lp->set_action(&lp->spx_action, ACTION_TIMEDREINVERT);
126 }
127
128 /* Otherwise simply update the optimal time metric */
129 else
130 lu->time_refactnext = f;
131 #if 0
132 if(lu->num_pivots % 10 == 0)
133 lp->report(lp, NORMAL, "bfp pivot %d - start %f - timestat %f",
134 lu->num_pivots, lu->time_refactstart, f);
135 #endif
136 }
137
138 test = lp->is_action(lp->spx_action, ACTION_REINVERT | ACTION_TIMEDREINVERT);
139 return(test);
140 }
141
142 /* DON'T MODIFY */
bfp_isSetI(lprec * lp)143 MYBOOL BFP_CALLMODEL bfp_isSetI(lprec *lp)
144 {
145 return( (MYBOOL) lp->invB->set_Bidentity );
146 }
147
148 /* DON'T MODIFY */
bfp_createMDO(lprec * lp,MYBOOL * usedpos,int count,MYBOOL doMDO)149 int *bfp_createMDO(lprec *lp, MYBOOL *usedpos, int count, MYBOOL doMDO)
150 {
151 int *mdo, i, j, kk;
152
153 mdo = (int *) malloc((count + 1)*sizeof(*mdo));
154 /* allocINT(lp, &mdo, count + 1, FALSE); */
155
156 /* Fill the mdo[] array with remaining full-pivot basic user variables */
157 kk = 0;
158 for(j = 1; j <= lp->columns; j++) {
159 i = lp->rows + j;
160 if(usedpos[i] == TRUE) {
161 kk++;
162 mdo[kk] = i;
163 }
164 }
165 mdo[0] = kk;
166 if(kk == 0)
167 goto Process;
168
169 /* Calculate the approximate minimum degree column ordering */
170 if(doMDO) {
171 i = lp->getMDO(lp, usedpos, mdo, NULL, FALSE);
172 if(i != 0) {
173 lp->report(lp, CRITICAL, "bfp_createMDO: Internal error %d in minimum degree ordering routine", i);
174 FREE(mdo);
175 }
176 }
177 Process:
178 return( mdo );
179 }
bfp_updaterefactstats(lprec * lp)180 void BFP_CALLMODEL bfp_updaterefactstats(lprec *lp)
181 {
182 INVrec *lu = lp->invB;
183
184 /* Signal that we are refactorizing */
185 lu->is_dirty = AUTOMATIC;
186
187 /* Set time of start of current refactorization cycle */
188 lu->time_refactstart = timeNow();
189 lu->time_refactnext = 0;
190 lu->user_colcount = 0;
191
192 /* Do the numbers */
193 if(lu->force_refact)
194 lu->num_dense_refact++;
195 else if(lu->timed_refact && lp->is_action(lp->spx_action, ACTION_TIMEDREINVERT))
196 lu->num_timed_refact++;
197 lu->num_refact++;
198 }
199
bfp_rowextra(lprec * lp)200 int BFP_CALLMODEL bfp_rowextra(lprec *lp)
201 {
202 if(lp->is_obj_in_basis(lp))
203 return( 1 );
204 else
205 return( 0 );
206 }
207