source: branches/devel-1/PresolveZeros.cpp @ 2351

Last change on this file since 2351 was 49, checked in by ladanyi, 17 years ago

everything compiles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.1 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 "CoinHelperFunctions.hpp"
9#include "PresolveMatrix.hpp"
10#include "PresolveZeros.hpp"
11
12inline double min(double x, double y)
13{
14  return (x < y) ? x : y;
15}
16
17// searches the cols in checkcols for zero entries.
18// creates a dropped_zero entry for each one; doesn't check for out-of-memory.
19// returns number of zeros found.
20static int drop_col_zeros(int ncheckcols, int *checkcols,
21                           const CoinBigIndex *mcstrt, double *colels, int *hrow,
22                           int *hincol,
23                           dropped_zero *actions)
24{
25  typedef dropped_zero action;
26  int nactions = 0;
27
28  for (int i=0; i<ncheckcols; i++) {
29    int col = checkcols[i];
30    CoinBigIndex kcs = mcstrt[col];
31    CoinBigIndex kce = mcstrt[col] + hincol[col];
32    CoinBigIndex k;
33
34    for (k=kcs; k<kce; ++k) {
35      if (fabs(colels[k]) < ZTOLDP) {
36        actions[nactions].col = col;
37        actions[nactions].row = hrow[k];
38        nactions++;
39
40#if     DEBUG_PRESOLVE
41        if (nactions == 1)
42          printf("ZEROS:  ");
43        printf("(%d,%d) ", hrow[k], col);
44#endif
45
46        colels[k] = colels[kce-1];
47        hrow[k]   = hrow[kce-1];
48        kce--;
49        hincol[col]--;
50
51        --k;    // redo this position
52      }
53    }
54  }
55
56#if     DEBUG_PRESOLVE
57  if (nactions)
58    printf("\n");
59#endif
60
61  return (nactions);
62}
63
64// very similar to col, but without the buffer and reads zeros
65// didn't bother to change the param names
66void drop_row_zeros(int nzeros, const dropped_zero *zeros,
67                    const CoinBigIndex *mcstrt, double *colels, int *hrow,
68                    int *hincol)
69{
70  for (int i=0; i<nzeros; i++) {
71    int col = zeros[i].row;
72    CoinBigIndex kcs = mcstrt[col];
73    CoinBigIndex kce = mcstrt[col] + hincol[col];
74    CoinBigIndex k;
75
76    for (k=kcs; k<kce; k++) {
77      if (fabs(colels[k]) < ZTOLDP) {
78        colels[k] = colels[kce-1];
79        hrow[k]   = hrow[kce-1];
80        kce--;
81        hincol[col]--;
82
83        --k;    // redo this position
84      }
85    }
86  }
87}
88
89
90const PresolveAction *drop_zero_coefficients_action::presolve(PresolveMatrix *prob,
91                                                               int *checkcols,
92                                                               int ncheckcols,
93                                                               const PresolveAction *next)
94{
95  double *colels        = prob->colels_;
96  int *hrow             = prob->hrow_;
97  CoinBigIndex *mcstrt          = prob->mcstrt_;
98  int *hincol           = prob->hincol_;
99  int ncols             = prob->ncols_;
100
101  //  int i;
102  dropped_zero * zeros = new dropped_zero[ncols];
103
104  int nzeros = drop_col_zeros(ncheckcols, checkcols,
105                              mcstrt, colels, hrow, hincol,
106                              zeros);
107
108  if (nzeros == 0) {
109    delete [] zeros;
110    return (next);
111  } else {
112    double *rowels      = prob->rowels_;
113    int *hcol           = prob->hcol_;
114    CoinBigIndex *mrstrt                = prob->mrstrt_;
115    int *hinrow         = prob->hinrow_;
116    //    int nrows             = prob->nrows_;
117
118#if     PRESOLVE_SUMMARY
119    printf("NZEROS:  %d\n", nzeros);
120#endif
121
122    // make the row rep consistent
123    drop_row_zeros(nzeros, zeros, mrstrt, rowels, hcol, hinrow);
124
125    dropped_zero *zeros1 = new dropped_zero[nzeros];
126    ClpDisjointCopyN(zeros, nzeros, zeros1);
127
128    delete [] zeros;
129    return (new drop_zero_coefficients_action(nzeros, zeros1, next));
130  }
131}
132
133
134const PresolveAction *drop_zero_coefficients(PresolveMatrix *prob,
135                                              const PresolveAction *next)
136{
137  int ncols             = prob->ncols_;
138  int *checkcols        = new int[ncols];
139
140  for (int i=0; i<ncols; i++)
141    checkcols[i] = i;
142
143  const PresolveAction *retval = drop_zero_coefficients_action::presolve(prob,
144                                                         checkcols, ncols,
145                                                         next);
146  delete[]checkcols;
147  return (retval);
148}
149
150void drop_zero_coefficients_action::postsolve(PostsolveMatrix *prob) const
151{
152  const int nzeros      = nzeros_;
153  const dropped_zero *const zeros = zeros_;
154
155  double *colels        = prob->colels_;
156  int *hrow             = prob->hrow_;
157  CoinBigIndex *mcstrt          = prob->mcstrt_;
158  int *hincol           = prob->hincol_;
159  int *link             = prob->link_;
160  CoinBigIndex free_list                = prob->free_list_;
161
162  for (const dropped_zero *z = &zeros[nzeros-1]; zeros<=z; z--) {
163    int irow    = z->row;
164    int jcol    = z->col;
165
166    {
167      CoinBigIndex k = free_list;
168      free_list = link[free_list];
169      check_free_list(free_list);
170
171      hrow[k] = irow;
172      colels[k] = 0.0;
173      link[k] = mcstrt[jcol];
174      mcstrt[jcol] = k;
175    }
176   
177    hincol[jcol]++;
178  }
179
180  prob->free_list_ = free_list;
181} 
Note: See TracBrowser for help on using the repository browser.