source: branches/devel-1/PresolveFixed.cpp @ 29

Last change on this file since 29 was 29, checked in by forrest, 18 years ago

Presolve (no changes to Makefile)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.4 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3
4#include <stdio.h>
5#include <math.h>
6#include <strings.h>
7
8#include "PresolveMatrix.hpp"
9#include "PresolveFixed.hpp"
10
11const char *remove_fixed_action::name() const
12{
13  return ("remove_fixed_action");
14}
15
16/*
17 * invariant:  both reps are loosely packed.
18 * coefficients of both reps remain consistent.
19 *
20 * Note that this concerns variables whose column bounds determine that
21 * they are slack; this does NOT concern singleton row constraints that
22 * determine that the relevant variable is slack.
23 *
24 * Invariant:  col and row rep are consistent
25 */
26const remove_fixed_action *remove_fixed_action::presolve(PresolveMatrix *prob,
27                                                     int *fcols,
28                                                     int nfcols,
29                                                     const PresolveAction *next)
30{
31  double *colels        = prob->colels_;
32  int *hrow             = prob->hrow_;
33  int *mcstrt           = prob->mcstrt_;
34  int *hincol           = prob->hincol_;
35
36  double *rowels        = prob->rowels_;
37  int *hcol             = prob->hcol_;
38  int *mrstrt           = prob->mrstrt_;
39  int *hinrow           = prob->hinrow_;
40  int nrows             = prob->nrows_;
41
42  double *clo   = prob->clo_;
43  double *cup   = prob->cup_;
44  double *rlo   = prob->rlo_;
45  double *rup   = prob->rup_;
46
47  double *dcost = prob->cost_;
48
49  presolvehlink *clink = prob->clink_;
50
51  action *actions       = new  action[nfcols];
52
53  for (int ckc=0; ckc<nfcols; ckc++) {
54    int j = fcols[ckc];
55
56    PRESOLVEASSERT(/*hincol[j] > 0 &&*/ cup[j] == clo[j]);
57
58    double sol = clo[j];
59    int kcs = mcstrt[j];
60    int kce = kcs + hincol[j];
61    int k;
62
63    {
64      action &f = actions[ckc];
65     
66      f.col = j;
67      f.sol = sol;
68
69      f.nincol = hincol[j];
70      f.colels = presolve_duparray(&colels[kcs], hincol[j]); // inefficient
71      f.colrows = presolve_duparray(&hrow[kcs], hincol[j]);  // inefficient
72    }
73    // the bias is updated when the empty column is removed
74    //prob->change_bias(sol * dcost[j]);
75
76    for (k=kcs; k<kce; k++) {
77      int row = hrow[k];
78      double coeff = colels[k];
79
80      rlo[row] -= sol * coeff;
81      rup[row] -= sol * coeff;
82
83      // remove this column from all rows it occurs in in the row rep
84      presolve_delete_from_row(row, j, mrstrt, hinrow, hcol, rowels);
85
86      // mark
87      prob->addRow(row);
88      int krs = mrstrt[row];
89      int kre = krs + hinrow[row];
90      for (int k=krs; k<kre; k++) {
91        int jcol = hcol[k];
92        prob->addCol(jcol);
93      }
94      // remove the column entirely from the col rep
95      PRESOLVE_REMOVE_LINK(clink, j);
96      hincol[j] = 0;
97    }
98  }
99#if     PRESOLVE_SUMMARY
100  printf("NFIXED:  %d\n", nfcols);
101#endif
102
103#if 0
104  remove_fixed_action * nextAction =  new
105    remove_fixed_action(nfcols, actions, next);
106  delete [] actions;
107  return nextAction;
108#else
109  return (new remove_fixed_action(nfcols, actions, next));
110#endif
111}
112
113remove_fixed_action::remove_fixed_action(int nactions,
114                                         const action *actions,
115                                         const PresolveAction *next) :
116  PresolveAction(next),
117  nactions_(nactions),
118  actions_(actions)
119{
120}
121remove_fixed_action::~remove_fixed_action()
122{
123  for (int i=nactions_-1; i>=0; i--) {
124    delete[]actions_[i].colrows;
125    delete[]actions_[i].colels;
126  }
127  delete[]actions_;
128}
129
130/*
131 * Say we determined that cup - clo <= ztolzb, so we fixed sol at clo.
132 * This involved subtracting clo*coeff from ub/lb for each row the
133 * variable occurred in.
134 * Now when we put the variable back in, by construction the variable
135 * is within tolerance, the non-slacks are unchanged, and the
136 * distances of the affected slacks from their bounds should remain
137 * unchanged (ignoring roundoff errors).
138 * It may be that by adding the term back in, the affected constraints
139 * now aren't as accurate due to round-off errors; this could happen
140 * if only one summand and the slack in the original formulation were large
141 * (and naturally had opposite signs), and the new term in the constraint
142 * is about the size of the old slack, so the new slack becomes about 0.
143 * It may be that there is catastrophic cancellation in the summation,
144 * so it might not compute to 0.
145 */
146void remove_fixed_action::postsolve(PostsolveMatrix *prob) const
147{
148  const action *const actions = actions_;
149  const int nactions    = nactions_;
150
151  double *colels        = prob->colels_;
152  int *hrow             = prob->hrow_;
153  int *mcstrt           = prob->mcstrt_;
154  int *hincol           = prob->hincol_;
155  int *link             = prob->link_;
156  int ncols             = prob->ncols_;
157  int free_list         = prob->free_list_;
158
159  double *clo   = prob->clo_;
160  double *cup   = prob->cup_;
161  double *rlo   = prob->rlo_;
162  double *rup   = prob->rup_;
163
164  double *sol   = prob->sol_;
165  double *dcost = prob->cost_;
166  double *rcosts        = prob->rcosts_;
167
168  double *acts  = prob->acts_;
169  double *rowduals = prob->rowduals_;
170
171  unsigned char *colstat        = prob->colstat_;
172  unsigned char *rowstat        = prob->rowstat_;
173
174  const double maxmin   = prob->maxmin_;
175
176  char *cdone   = prob->cdone_;
177  char *rdone   = prob->rdone_;
178
179  for (const action *f = &actions[nactions-1]; actions<=f; f--) {
180    int icol = f->col;
181    const double thesol = f->sol;
182
183    cdone[icol] = FIXED_VARIABLE;
184
185    sol[icol] = thesol;
186    clo[icol] = thesol;
187    cup[icol] = thesol;
188
189    {
190      int cs = -11111;
191      int nc = f->nincol;
192      double dj = maxmin * dcost[icol];
193
194      for (int i=0; i<nc; ++i) {
195        int row = f->colrows[i];
196        double coeff = f->colels[i];
197
198        // pop free_list
199        int k = free_list;
200        free_list = link[free_list];
201       
202        check_free_list(free_list);
203
204        // restore
205        hrow[k] = row;
206        colels[k] = coeff;
207        link[k] = cs;
208        cs = k;
209
210        PRESOLVEASSERT(rdone[row]);
211
212        if (-PRESOLVE_INF < rlo[row])
213          rlo[row] += coeff * thesol;
214        if (rup[row] < PRESOLVE_INF)
215          rup[row] += coeff * thesol;
216        acts[row] += coeff * thesol;
217
218        dj -= rowduals[row] * coeff;
219      }
220      mcstrt[icol] = cs;
221
222      rcosts[icol] = dj;
223    }
224    hincol[icol] = f->nincol;
225
226    /* the bounds in the reduced problem were tightened.
227     * that means that this variable may not have been basic
228     * because it didn't have to be,
229     * but now it may have to.
230     * no - the bounds aren't changed by this operation.
231     */
232    if (colstat)
233      prob->setColumnStatus(icol,PrePostsolveMatrix::atUpperBound);
234  }
235
236  prob->free_list_ = free_list;
237}
238
239
240const PresolveAction *remove_fixed(PresolveMatrix *prob,
241                                    const PresolveAction *next)
242{
243  int ncols     = prob->ncols_;
244  int *fcols    = new int[ncols];
245  int nfcols    = 0;
246
247  int *hincol           = prob->hincol_;
248
249  double *clo   = prob->clo_;
250  double *cup   = prob->cup_;
251
252  for (int i=0; i<ncols; i++)
253    if (hincol[i] > 0 && clo[i] == cup[i])
254      fcols[nfcols++] = i;
255
256  next = remove_fixed_action::presolve(prob, fcols, nfcols, next);
257  delete[]fcols;
258  return (next);
259}
260
261
262
263const char *make_fixed_action::name() const
264{
265  return ("make_fixed_action");
266}
267
268const PresolveAction *make_fixed_action::presolve(PresolveMatrix *prob,
269                                                     int *fcols,
270                                                     int nfcols,
271                                                   bool fix_to_lower,
272                                                   const PresolveAction *next)
273{
274  double *clo   = prob->clo_;
275  double *cup   = prob->cup_;
276
277  action *actions       = new  action[nfcols];
278
279  for (int ckc=0; ckc<nfcols; ckc++) {
280    int j = fcols[ckc];
281
282    action &f = actions[ckc];
283     
284    if (fix_to_lower) {
285      f.bound = cup[j];
286      cup[j] = clo[j];
287    } else {
288      f.bound = clo[j];
289      clo[j] = cup[j];
290    }
291  }
292
293  // this is unusual in that the make_fixed_action transform
294  // contains within it a remove_fixed_action transform
295  // bad idea?
296  return (new make_fixed_action(nfcols, actions, fix_to_lower,
297                                remove_fixed_action::presolve(prob,
298                                                              fcols, nfcols,
299                                                              0),
300                                next));
301}
302
303void make_fixed_action::postsolve(PostsolveMatrix *prob) const
304{
305  const action *const actions = actions_;
306  const int nactions    = nactions_;
307  const bool fix_to_lower       = fix_to_lower_;
308
309  double *clo   = prob->clo_;
310  double *cup   = prob->cup_;
311
312  faction_->postsolve(prob);
313
314  for (int cnt = faction_->nactions_-1; cnt>=0; cnt--) {
315    const action *f = &actions[cnt];
316    const remove_fixed_action::action *f1 = &faction_->actions_[cnt];
317
318    int icol = f1->col;
319    if (fix_to_lower) {
320      cup[icol] = f->bound;
321    } else {
322      clo[icol] = f->bound;
323    }
324  }
325}
326
327
328const PresolveAction *make_fixed(PresolveMatrix *prob,
329                                  const PresolveAction *next)
330{
331  int ncols     = prob->ncols_;
332  int *fcols    = new int[ncols];
333  int nfcols    = 0;
334
335  int *hincol           = prob->hincol_;
336
337  double *clo   = prob->clo_;
338  double *cup   = prob->cup_;
339
340  for (int i=0; i<ncols; i++)
341    if (hincol[i] > 0 && fabs(cup[i] - clo[i]) < ZTOLDP) 
342      fcols[nfcols++] = i;
343
344  next = make_fixed_action::presolve(prob, fcols, nfcols,
345                                     true, // arbitrary
346                                     next);
347  delete[]fcols;
348  return (next);
349}
350
351
Note: See TracBrowser for help on using the repository browser.