1/* $Id: CoinPresolveIsolated.cpp 1373 2011-01-03 23:57:44Z lou $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include <stdio.h>
7#include <math.h>
8
9#include "CoinPresolveMatrix.hpp"
10#include "CoinPresolveIsolated.hpp"
11#include "CoinHelperFunctions.hpp"
12
13#if PRESOLVE_DEBUG || PRESOLVE_CONSISTENCY
14#include "CoinPresolvePsdebug.hpp"
15#endif
16
17// Rarely, there may a constraint whose variables only
18// occur in that constraint.
19// In this case it is a completely independent problem.
20// We should be able to solve it right now.
21// Since that is actually not trivial, I'm just going to ignore
22// them and stick them back in at postsolve.
23const CoinPresolveAction *isolated_constraint_action::presolve(CoinPresolveMatrix *prob,
24 int irow,
25 const CoinPresolveAction *next)
26{
27 int *hincol = prob->hincol_;
28 const CoinBigIndex *mcstrt = prob->mcstrt_;
29 int *hrow = prob->hrow_;
30 double *colels = prob->colels_;
31
32 double *clo = prob->clo_;
33 double *cup = prob->cup_;
34
35 const double *rowels = prob->rowels_;
36 const int *hcol = prob->hcol_;
37 const CoinBigIndex *mrstrt = prob->mrstrt_;
38
39 // may be written by useless constraint
40 int *hinrow = prob->hinrow_;
41
42 double *rlo = prob->rlo_;
43 double *rup = prob->rup_;
44
45 CoinBigIndex krs = mrstrt[irow];
46 CoinBigIndex kre = krs + hinrow[irow];
47
48 double *dcost = prob->cost_;
49 const double maxmin = prob->maxmin_;
50
51# if PRESOLVE_DEBUG
52 {
53 printf("ISOLATED: %d - ", irow);
54 CoinBigIndex k;
55 for ( k = krs; k<kre; ++k)
56 printf("%d ", hcol[k]);
57 printf("\n");
58 }
59# endif
60
61 if (rlo[irow] != 0.0 || rup[irow] != 0.0) {
62# if PRESOLVE_DEBUG
63 printf("can't handle non-trivial isolated constraints for now\n");
64# endif
65 return NULL;
66 }
67 CoinBigIndex k;
68 for ( k = krs; k<kre; ++k) {
69 int jcol = hcol[k];
70 if ((clo[jcol] != 0.0 && cup[jcol] != 0.0)||
71 (maxmin*dcost[jcol] > 0.0 && clo[jcol] != 0.0) ||
72 (maxmin*dcost[jcol] < 0.0 && cup[jcol] != 0.0) ){
73# if PRESOLVE_DEBUG
74 printf("can't handle non-trivial isolated constraints for now\n");
75# endif
76 return NULL;
77 }
78 }
79
80 int nc = hinrow[irow];
81
82#if 0
83 double tableau = new double[nc];
84 double sol = new double[nc];
85 double clo = new double[nc];
86 double cup = new double[nc];
87
88
89 for (int i=0; i<nc; ++i) {
90 int col = hcol[krs+1];
91 tableau[i] = rowels[krs+i];
92 clo[i] = prob->clo[krs+i];
93 cup[i] = prob->cup[krs+i];
94
95 sol[i] = clo[i];
96 }
97#endif
98
99 // HACK - set costs to 0.0 so empty.cpp doesn't complain
100 double *costs = new double[nc];
101 for (k = krs; k<kre; ++k) {
102 costs[k-krs] = dcost[hcol[k]];
103 dcost[hcol[k]] = 0.0;
104 }
105
106 next = new isolated_constraint_action(rlo[irow], rup[irow],
107 irow, nc,
108 CoinCopyOfArray(&hcol[krs], nc),
109 CoinCopyOfArray(&rowels[krs], nc),
110 costs,
111 next);
112
113 for ( k=krs; k<kre; k++)
114 { presolve_delete_from_col(irow,hcol[k],mcstrt,hincol,hrow,colels) ;
115 if (hincol[hcol[k]] == 0)
116 { PRESOLVE_REMOVE_LINK(prob->clink_,hcol[k]) ; } }
117 hinrow[irow] = 0 ;
118 PRESOLVE_REMOVE_LINK(prob->rlink_,irow) ;
119
120 // just to make things squeeky
121 rlo[irow] = 0.0;
122 rup[irow] = 0.0;
123
124# if CHECK_CONSISTENCY
125 presolve_links_ok(prob) ;
126 presolve_consistent(prob);
127# endif
128
129 return (next);
130}
131
132const char *isolated_constraint_action::name() const
133{
134 return ("isolated_constraint_action");
135}
136
137void isolated_constraint_action::postsolve(CoinPostsolveMatrix *prob) const
138{
139 double *colels = prob->colels_;
140 int *hrow = prob->hrow_;
141 CoinBigIndex *mcstrt = prob->mcstrt_;
142 int *link = prob->link_;
143 int *hincol = prob->hincol_;
144
145 double *rowduals = prob->rowduals_;
146 double *rowacts = prob->acts_;
147 double *sol = prob->sol_;
148
149 CoinBigIndex &free_list = prob->free_list_;
150
151
152 // hides fields
153 double *rlo = prob->rlo_;
154 double *rup = prob->rup_;
155
156 double rowact = 0.0;
157
158 int irow = this->row_;
159
160 rup[irow] = this->rup_;
161 rlo[irow] = this->rlo_;
162 int k;
163
164 for (k=0; k<this->ninrow_; k++) {
165 int jcol = this->rowcols_[k];
166
167 sol[jcol] = 0.0; // ONLY ACCEPTED SUCH CONSTRAINTS
168
169 CoinBigIndex kk = free_list;
170 assert(kk >= 0 && kk < prob->bulk0_) ;
171 free_list = link[free_list];
172
173 mcstrt[jcol] = kk;
174
175 //rowact += rowels[k] * sol[jcol];
176
177 colels[kk] = this->rowels_[k];
178 hrow[kk] = irow;
179 link[kk] = NO_LINK ;
180
181 hincol[jcol] = 1;
182 }
183
184# if PRESOLVE_CONSISTENCY
185 presolve_check_free_list(prob) ;
186# endif
187
188 // ???
189 prob->setRowStatus(irow,CoinPrePostsolveMatrix::basic);
190 rowduals[irow] = 0.0;
191
192 rowacts[irow] = rowact;
193
194 // leave until desctructor
195 // deleteAction(rowcols_,int *);
196 // deleteAction(rowels_,double *);
197 // deleteAction(costs_,double *);
198}
199
200isolated_constraint_action::~isolated_constraint_action()
201{
202 deleteAction(rowcols_,int *);
203 deleteAction(rowels_,double *);
204 deleteAction(costs_,double *);
205}
206