source: trunk/PresolveFixed.cpp @ 144

Last change on this file since 144 was 144, checked in by forrest, 17 years ago

Allow for nonlinear variables in presolve

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