1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the class library                   */
4    	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SoPlex; see the file LICENSE. If not email to soplex@zib.de.  */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	#include <assert.h>
26   	#include <iostream>
27   	
28   	#include "soplex/spxdefines.h"
29   	
30   	namespace soplex
31   	{
32   	
33   	template <class R>
34   	int SPxDantzigPR<R>::selectLeave()
35   	{
36   	   assert(this->thesolver != 0);
37   	
38   	   if(this->thesolver->sparsePricingLeave)
39   	      return selectLeaveSparse();
40   	
41   	   //    const R* up  = this->thesolver->ubBound();
42   	   //    const R* low = this->thesolver->lbBound();
43   	
44   	   R best = -this->thetolerance;
45   	   int  n    = -1;
46   	
47   	   for(int i = this->thesolver->dim() - 1; i >= 0; --i)
48   	   {
49   	      R x = this->thesolver->fTest()[i];
50   	
51   	      if(x < -this->thetolerance)
52   	      {
53   	         if(x < best)
54   	         {
55   	            n    = i;
56   	            best = x;
57   	         }
58   	      }
59   	   }
60   	
61   	   return n;
62   	}
63   	
64   	template <class R>
65   	int SPxDantzigPR<R>::selectLeaveSparse()
66   	{
67   	   assert(this->thesolver != 0);
68   	
69   	   R best   = -this->thetolerance;
70   	   R x;
71   	   int  n      = -1;
72   	   int  index;
73   	
74   	   for(int i = this->thesolver->infeasibilities.size() - 1; i >= 0; --i)
75   	   {
76   	      index = this->thesolver->infeasibilities.index(i);
77   	      x = this->thesolver->fTest()[index];
78   	
79   	      if(x < -this->thetolerance)
80   	      {
81   	         if(x < best)
82   	         {
83   	            n    = index;
84   	            best = x;
85   	         }
86   	      }
87   	      else
88   	      {
89   	         this->thesolver->infeasibilities.remove(i);
90   	         assert(this->thesolver->isInfeasible[index] > 0);
91   	         this->thesolver->isInfeasible[index] = 0;
92   	      }
93   	   }
94   	
95   	   return n;
96   	}
97   	
98   	template <class R>
99   	SPxId SPxDantzigPR<R>::selectEnter()
100  	{
101  	   assert(this->thesolver != 0);
102  	
103  	   // const SPxBasisBase<R>::Desc&    ds   = this->thesolver->basis().desc();
104  	
105  	   SPxId enterId;
106  	   enterId = selectEnterX();
107  	
108  	   return enterId;
109  	}
110  	
111  	template <class R>
112  	SPxId SPxDantzigPR<R>::selectEnterX()
113  	{
114  	   SPxId enterId;
115  	   SPxId enterIdCo;
116  	   R best;
117  	   R bestCo;
118  	
119  	   best = -this->thetolerance;
120  	   bestCo = -this->thetolerance;
121  	   enterId = (this->thesolver->sparsePricingEnter) ? selectEnterSparseDim(best,
122  	             enterId) : selectEnterDenseDim(best, enterId);
123  	   enterIdCo = (this->thesolver->sparsePricingEnterCo) ? selectEnterSparseCoDim(bestCo,
124  	               enterId) : selectEnterDenseCoDim(bestCo, enterId);
125  	
126  	   // prefer slack indices to reduce nonzeros in basis matrix
127  	   if(enterId.isValid() && (best > SOPLEX_SPARSITY_TRADEOFF * bestCo || !enterIdCo.isValid()))
128  	      return enterId;
129  	   else
130  	      return enterIdCo;
131  	}
132  	
133  	
134  	template <class R>
135  	SPxId SPxDantzigPR<R>::selectEnterSparseDim(R& best, SPxId& enterId)
136  	{
137  	   assert(this->thesolver != 0);
138  	
139  	   int idx;
140  	   R x;
141  	
142  	   for(int i = this->thesolver->infeasibilities.size() - 1; i >= 0; --i)
143  	   {
144  	      idx = this->thesolver->infeasibilities.index(i);
145  	      x = this->thesolver->coTest()[idx];
146  	
147  	      if(x < -this->thetolerance)
148  	      {
149  	         if(x < best)
150  	         {
151  	            enterId = this->thesolver->coId(idx);
152  	            best = x;
153  	         }
154  	      }
155  	      else
156  	      {
157  	         this->thesolver->infeasibilities.remove(i);
158  	
159  	         assert(this->thesolver->isInfeasible[idx]);
160  	         this->thesolver->isInfeasible[idx] = 0;
161  	      }
162  	   }
163  	
164  	   return enterId;
165  	}
166  	
167  	template <class R>
168  	SPxId SPxDantzigPR<R>::selectEnterSparseCoDim(R& best, SPxId& enterId)
169  	{
170  	   assert(this->thesolver != 0);
171  	
172  	   int idx;
173  	   R x;
174  	
175  	   for(int i = this->thesolver->infeasibilitiesCo.size() - 1; i >= 0; --i)
176  	   {
177  	      idx = this->thesolver->infeasibilitiesCo.index(i);
178  	      x = this->thesolver->test()[idx];
179  	
180  	      if(x < -this->thetolerance)
181  	      {
182  	         if(x < best)
183  	         {
184  	            enterId = this->thesolver->id(idx);
185  	            best = x;
186  	         }
187  	      }
188  	      else
189  	      {
190  	         this->thesolver->infeasibilitiesCo.remove(i);
191  	         assert(this->thesolver->isInfeasibleCo[idx] > 0);
192  	         this->thesolver->isInfeasibleCo[idx] = 0;
193  	      }
194  	   }
195  	
196  	   return enterId;
197  	}
198  	
199  	template <class R>
200  	SPxId SPxDantzigPR<R>::selectEnterDenseDim(R& best, SPxId& enterId)
201  	{
202  	   assert(this->thesolver != 0);
203  	
204  	   R x;
205  	
206  	   for(int i = this->thesolver->dim() - 1; i >= 0; --i)
207  	   {
208  	      x = this->thesolver->coTest()[i];
209  	
210  	      if(x < -this->thetolerance)
211  	      {
212  	         if(x < best)
213  	         {
214  	            enterId   = this->thesolver->coId(i);
215  	            best = x;
216  	         }
217  	      }
218  	   }
219  	
220  	   return enterId;
221  	}
222  	
223  	template <class R>
224  	SPxId SPxDantzigPR<R>::selectEnterDenseCoDim(R& best, SPxId& enterId)
225  	{
226  	   assert(this->thesolver != 0);
227  	
228  	   R x;
229  	
230  	   for(int i = this->thesolver->coDim() - 1; i >= 0; --i)
231  	   {
232  	      x = this->thesolver->test()[i];
233  	
234  	      if(x < -this->thetolerance)
235  	      {
236  	         if(x < best)
237  	         {
238  	            enterId   = this->thesolver->id(i);
239  	            best = x;
240  	         }
241  	      }
242  	   }
243  	
244  	   return enterId;
245  	}
246  	
247  	} // namespace soplex
248