source: trunk/PresolveSingleton.cpp @ 56

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

Idiot and modifications for Visual C++

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.8 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 "CoinHelperFunctions.hpp"
8#include "PresolveMatrix.hpp"
9
10#include "PresolveEmpty.hpp"    // for DROP_COL/DROP_ROW
11#include "PresolveFixed.hpp"
12#include "PresolveSingleton.hpp"
13#include "ClpMessage.hpp"
14
15/*
16 * Transfers singleton row bound information to the corresponding column bounds.
17 * What I refer to as a row singleton would be called a doubleton
18 * in the paper, since my terminology doesn't refer to the slacks.
19 * In terms of the paper, we transfer the bounds of the slack onto
20 * the variable (vii) and then "substitute" the slack out of the problem
21 * (which is a noop).
22 */
23const PresolveAction *
24slack_doubleton_action::presolve(PresolveMatrix *prob,
25                                 const PresolveAction *next,
26                                 bool & notFinished)
27{
28  double *colels        = prob->colels_;
29  int *hrow             = prob->hrow_;
30  CoinBigIndex *mcstrt          = prob->mcstrt_;
31  int *hincol           = prob->hincol_;
32  int ncols             = prob->ncols_;
33
34  double *clo           = prob->clo_;
35  double *cup           = prob->cup_;
36
37  double *rowels        = prob->rowels_;
38  const int *hcol       = prob->hcol_;
39  const CoinBigIndex *mrstrt    = prob->mrstrt_;
40  int *hinrow           = prob->hinrow_;
41  //  int nrows         = prob->nrows_;
42
43  double *rlo           = prob->rlo_;
44  double *rup           = prob->rup_;
45
46  // If rowstat exists then all do
47  unsigned char *rowstat        = prob->rowstat_;
48  //  double *acts      = prob->acts_;
49  double * sol = prob->sol_;
50  //  unsigned char * colstat = prob->colstat_;
51
52  //  const char *integerType = prob->integerType_;
53
54  const double ztolzb   = prob->ztolzb_;
55
56  int numberLook = prob->numberRowsToDo_;
57  int iLook;
58  int * look = prob->rowsToDo_;
59
60  action actions[MAX_SLACK_DOUBLETONS];
61  int nactions = 0;
62  notFinished = false;
63
64  int * fixed_cols = new int [ncols];
65  int nfixed_cols       = 0;
66
67  // this loop can apparently create new singleton rows;
68  // I haven't bothered to detect this.
69  // wasfor (int irow=0; irow<nrows; irow++)
70  for (iLook=0;iLook<numberLook;iLook++) {
71    int irow = look[iLook];
72    if (hinrow[irow] == 1) {
73      int jcol = hcol[mrstrt[irow]];
74      double coeff = rowels[mrstrt[irow]];
75      double lo = rlo[irow];
76      double up = rup[irow];
77      double acoeff = fabs(coeff);
78      //      const bool singleton_col = (hincol[jcol] == 1);
79
80      if (acoeff < ZTOLDP)
81        continue;
82
83      // don't bother with fixed cols
84      if (fabs(cup[jcol] - clo[jcol]) < ztolzb)
85        continue;
86
87      {
88        // put column on stack of things to do next time
89        prob->addCol(jcol);
90        action *s = &actions[nactions];
91        nactions++;
92
93        s->col = jcol;
94        s->clo = clo[jcol];
95        s->cup = cup[jcol];
96
97        s->row = irow;
98        s->rlo = rlo[irow];
99        s->rup = rup[irow];
100
101        s->coeff = coeff;
102      }
103
104      if (coeff < 0.0) {
105        swap(lo, up);
106        lo = -lo;
107        up = -up;
108      }
109     
110      if (lo <= -PRESOLVE_INF)
111        lo = -PRESOLVE_INF;
112      else {
113        lo /= acoeff;
114        if (lo <= -PRESOLVE_INF)
115          lo = -PRESOLVE_INF;
116      }
117
118      if (up > PRESOLVE_INF)
119        up = PRESOLVE_INF;
120      else {
121        up /= acoeff;
122        if (up > PRESOLVE_INF)
123          up = PRESOLVE_INF;
124      }
125     
126      if (clo[jcol] < lo)
127        clo[jcol] = lo;
128       
129      if (cup[jcol] > up) 
130        cup[jcol] = up;
131
132      if (fabs(cup[jcol] - clo[jcol]) < ZTOLDP) {
133        fixed_cols[nfixed_cols++] = jcol;
134      }
135
136      if (lo > up) {
137        if (lo <= up + prob->feasibilityTolerance_) {
138          // If close to integer then go there
139          double nearest = floor(lo+0.5);
140          if (fabs(nearest-lo)<2.0*prob->feasibilityTolerance_) {
141            lo = nearest;
142            up = nearest;
143          } else {
144            lo = up;
145          }
146          clo[jcol] = lo;
147          cup[jcol] = up;
148        } else {
149          prob->status_ |= 1;
150          prob->messageHandler()->message(CLP_PRESOLVE_COLINFEAS,
151                                             prob->messages())
152                                               <<jcol
153                                               <<lo
154                                               <<up
155                                               <<CoinMessageEol;
156          break;
157        }
158      }
159
160#if     DEBUG_PRESOLVE
161      printf("SINGLETON R-%d C-%d\n", irow, jcol);
162#endif
163
164      // eliminate the row entirely from the row rep
165      // rlinks don't seem to be used PRESOLVE_REMOVE_LINK(rlink, irow);
166      hinrow[irow] = 0;
167
168      // just to make things squeeky
169      rlo[irow] = 0.0;
170      rup[irow] = 0.0;
171
172      if (rowstat) {
173        // update solution and basis
174        int basisChoice=0;
175        int numberBasic=0;
176        if (prob->columnIsBasic(jcol))
177          numberBasic++;
178        if (prob->rowIsBasic(irow))
179          numberBasic++;
180        if (sol[jcol]<=clo[jcol]+ztolzb) {
181          sol[jcol] =clo[jcol];
182          prob->setColumnStatus(jcol,PrePostsolveMatrix::atLowerBound);
183        } else if (sol[jcol]>=cup[jcol]-ztolzb) {
184          sol[jcol] =cup[jcol];
185          prob->setColumnStatus(jcol,PrePostsolveMatrix::atUpperBound);
186        } else {
187          basisChoice=1;
188        }
189        if (numberBasic>1||basisChoice)
190          prob->setColumnStatus(jcol,PrePostsolveMatrix::basic);
191      }
192
193      // remove the row from this col in the col rep
194      presolve_delete_from_row(jcol, irow, mcstrt, hincol, hrow, colels);
195
196      if (nactions >= MAX_SLACK_DOUBLETONS) {
197        notFinished=true;
198        break;
199      }
200    }
201  }
202
203  if (nactions) {
204#if     PRESOLVE_SUMMARY
205    printf("SINGLETON ROWS:  %d\n", nactions);
206#endif
207    action *save_actions = new action[nactions];
208    ClpDisjointCopyN(actions, nactions, save_actions);
209    next = new slack_doubleton_action(nactions, save_actions, next);
210
211    if (nfixed_cols)
212      next = make_fixed_action::presolve(prob, fixed_cols, nfixed_cols,
213                                         true, // arbitrary
214                                         next);
215  }
216  delete [] fixed_cols;
217  return (next);
218}
219
220void slack_doubleton_action::postsolve(PostsolveMatrix *prob) const
221{
222  const action *const actions = actions_;
223  const int nactions = nactions_;
224
225  double *colels        = prob->colels_;
226  int *hrow             = prob->hrow_;
227  CoinBigIndex *mcstrt          = prob->mcstrt_;
228  int *hincol           = prob->hincol_;
229  int *link             = prob->link_;
230  //  int ncols         = prob->ncols_;
231
232  double *clo           = prob->clo_;
233  double *cup           = prob->cup_;
234
235  double *rlo           = prob->rlo_;
236  double *rup           = prob->rup_;
237
238  double *sol           = prob->sol_;
239  double *rcosts        = prob->rcosts_;
240
241  double *acts          = prob->acts_;
242  double *rowduals      = prob->rowduals_;
243
244  unsigned char *colstat                = prob->colstat_;
245  //  unsigned char *rowstat            = prob->rowstat_;
246
247  //  char *cdone               = prob->cdone_;
248  char *rdone           = prob->rdone_;
249  CoinBigIndex free_list                = prob->free_list_;
250
251  const double ztolzb   = prob->ztolzb_;
252
253  for (const action *f = &actions[nactions-1]; actions<=f; f--) {
254    int irow = f->row;
255    double lo0 = f->clo;
256    double up0 = f->cup;
257    double coeff = f->coeff;
258    int jcol = f->col;
259
260    rlo[irow] = f->rlo;
261    rup[irow] = f->rup;
262
263    clo[jcol] = lo0;
264    cup[jcol] = up0;
265
266    acts[irow] = coeff * sol[jcol];
267
268    // copy col to end to make room for new element
269    {
270      CoinBigIndex k = free_list;
271      free_list = link[free_list];
272
273      check_free_list(free_list);
274
275      hrow[k] = irow;
276      colels[k] = coeff;
277      link[k] = mcstrt[jcol];
278      mcstrt[jcol] = k;
279    }
280    hincol[jcol]++;     // right?
281
282    /*
283     * Have to compute rowstat and rowduals, since we are adding the row.
284     * that satisfy complentarity slackness.
285     *
286     * We may also have to modify colstat and rcosts if bounds
287     * have been relaxed.
288     */
289    if (!colstat) {
290      // ????
291      rowduals[irow] = 0.0;
292    } else {
293      if (prob->columnIsBasic(jcol)) {
294        /* variable is already basic, so slack in this row must be basic */
295        prob->setRowStatus(irow,PrePostsolveMatrix::basic);
296       
297        rowduals[irow] = 0.0;
298        /* hence no reduced costs change */
299        /* since the column was basic, it doesn't matter if it is now
300           away from its bounds. */
301        /* the slack is basic and its reduced cost is 0 */
302      } else if ((fabs(sol[jcol] - lo0) <= ztolzb &&
303                  rcosts[jcol] >= 0) ||
304                 
305                 (fabs(sol[jcol] - up0) <= ztolzb &&
306                  rcosts[jcol] <= 0)) {
307        /* up against its bound but the rcost is still ok */
308        prob->setRowStatus(irow,PrePostsolveMatrix::basic);
309       
310        rowduals[irow] = 0.0;
311        /* hence no reduced costs change */
312      } else if (! (fabs(sol[jcol] - lo0) <= ztolzb) &&
313                 ! (fabs(sol[jcol] - up0) <= ztolzb)) {
314        /* variable not marked basic,
315         * so was at a bound in the reduced problem,
316         * but its bounds were tighter in the reduced problem,
317         * so now it has to be made basic.
318         */
319        prob->setColumnStatus(jcol,PrePostsolveMatrix::basic);
320        prob->setRowStatusUsingValue(irow);
321
322        /* choose a value for rowduals[irow] that forces rcosts[jcol] to 0.0 */
323        /* new reduced cost = 0 = old reduced cost - new dual * coeff */
324        rowduals[irow] = rcosts[jcol] / coeff;
325        rcosts[jcol] = 0.0;
326
327        /* this value is provably of the right sign for the slack */
328        /* SHOULD SHOW THIS */
329      } else {
330        /* the solution is at a bound, but the rcost is wrong */
331
332        prob->setColumnStatus(jcol,PrePostsolveMatrix::basic);
333        prob->setRowStatusUsingValue(irow);
334
335        /* choose a value for rowduals[irow] that forcesd rcosts[jcol] to 0.0 */
336        rowduals[irow] = rcosts[jcol] / coeff;
337        rcosts[jcol] = 0.0;
338
339        /* this value is provably of the right sign for the slack */
340        /*rcosts[irow] = -rowduals[irow];*/
341      }
342    }
343
344    rdone[irow] = SLACK_DOUBLETON;
345  }
346  prob->free_list_ = free_list;
347}
348
Note: See TracBrowser for help on using the repository browser.