source: branches/devel-1/PresolveUseless.cpp @ 36

Last change on this file since 36 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: 3.6 KB
Line 
1#include <stdio.h>
2#include <math.h>
3#include <strings.h>
4#include "PresolveMatrix.hpp"
5#include "PresolveUseless.hpp"
6
7
8// WHAT HAPPENS IF COLS ARE DROPPED AS A RESULT??
9// should be like do_tighten.
10// not really - one could fix costed variables to appropriate bound.
11// ok, don't bother about it.  If it is costed, it will be checked
12// when it is eliminated as an empty col; if it is costed in the
13// wrong direction, the problem is unbounded, otherwise it is pegged
14// at its bound.  no special action need be taken here.
15const PresolveAction *useless_constraint_action::presolve(PresolveMatrix * prob,
16                                                                  const int *useless_rows,
17                                                                  int nuseless_rows,
18                                       const PresolveAction *next)
19{
20  // may be modified by useless constraint
21  double *colels        = prob->colels_;
22
23  // may be modified by useless constraint
24        int *hrow       = prob->hrow_;
25
26  const int *mcstrt     = prob->mcstrt_;
27
28  // may be modified by useless constraint
29        int *hincol     = prob->hincol_;
30
31  double *clo   = prob->clo_;
32  double *cup   = prob->cup_;
33
34  const double *rowels  = prob->rowels_;
35  const int *hcol       = prob->hcol_;
36  const int *mrstrt     = prob->mrstrt_;
37
38  // may be written by useless constraint
39        int *hinrow     = prob->hinrow_;
40  const int nrows       = prob->nrows_;
41
42  double *rlo   = prob->rlo_;
43  double *rup   = prob->rup_;
44
45  action *actions       = new action [nuseless_rows];
46
47#if     PRESOLVE_SUMMARY
48    printf("NUSELESS ROWS:  %d\n", nuseless_rows);
49#endif
50
51  for (int i=0; i<nuseless_rows; ++i) {
52    int irow = useless_rows[i];
53    int krs = mrstrt[irow];
54    int kre = krs + hinrow[irow];
55
56    action *f = &actions[i];
57
58    f->row = irow;
59    f->ninrow = hinrow[irow];
60    f->rlo = rlo[irow];
61    f->rup = rup[irow];
62    f->rowcols = copyOfArray(&hcol[krs], hinrow[irow]);
63    f->rowels  = copyOfArray(&rowels[krs], hinrow[irow]);
64
65    for (int k=krs; k<kre; k++)
66      presolve_delete_from_row(hcol[k], irow, mcstrt, hincol, hrow, colels);
67    hinrow[irow] = 0;
68
69    // just to make things squeeky
70    rlo[irow] = 0.0;
71    rup[irow] = 0.0;
72  }
73
74
75  next = new useless_constraint_action(nuseless_rows, actions, next);
76
77  return (next);
78}
79
80const char *useless_constraint_action::name() const
81{
82  return ("useless_constraint_action");
83}
84
85void useless_constraint_action::postsolve(PostsolveMatrix *prob) const
86{
87  const action *const actions = actions_;
88  const int nactions = nactions_;
89
90  double *colels        = prob->colels_;
91  int *hrow             = prob->hrow_;
92  int *mcstrt           = prob->mcstrt_;
93  int *link             = prob->link_;
94  int *hincol           = prob->hincol_;
95 
96  double *rowduals      = prob->rowduals_;
97  double *rowacts       = prob->acts_;
98  const double *sol     = prob->sol_;
99
100
101  int free_list         = prob->free_list_;
102
103  double *rlo   = prob->rlo_;
104  double *rup   = prob->rup_;
105
106  for (const action *f = &actions[nactions-1]; actions<=f; f--) {
107
108    int irow    = f->row;
109    int ninrow  = f->ninrow;
110    const int *rowcols  = f->rowcols;
111    const double *rowels = f->rowels;
112    double rowact = 0.0;
113
114    rup[irow] = f->rup;
115    rlo[irow] = f->rlo;
116
117    for (int k=0; k<ninrow; k++) {
118      int jcol = rowcols[k];
119      int kk = mcstrt[jcol];
120
121      // append deleted row element to each col
122      {
123        int kk = free_list;
124        free_list = link[free_list];
125
126        check_free_list(free_list);
127
128        hrow[kk] = irow;
129        colels[kk] = rowels[k];
130        link[kk] = mcstrt[jcol];
131        mcstrt[jcol] = kk;
132      }
133     
134      rowact += rowels[k] * sol[jcol];
135      hincol[jcol]++;
136    }
137   
138    // I don't know if this is always true
139    PRESOLVEASSERT(prob->getRowStatus(irow)==PrePostsolveMatrix::basic);
140    PRESOLVEASSERT(rowduals[irow] == 0.0);   
141    // rcosts are unaffected since rowdual is 0
142
143    rowacts[irow] = rowact;
144  }
145  prob->free_list_ = free_list;
146}
147
148
Note: See TracBrowser for help on using the repository browser.