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   	void SPxParMultPR<R>::setType(typename SPxSolverBase<R>::Type tp)
35   	{
36   	   if(tp == SPxSolverBase<R>::ENTER)
37   	   {
38   	      used = 0;
39   	      this->thesolver->setPricing(SPxSolverBase<R>::PARTIAL);
40   	   }
41   	   else
42   	   {
43   	      this->thesolver->setPricing(SPxSolverBase<R>::FULL);
44   	   }
45   	
46   	   this->thesolver->weights.reDim(0);
47   	   this->thesolver->coWeights.reDim(0);
48   	   this->thesolver->weightsAreSetup = false;
49   	
50   	   last = 0;
51   	   min = partialSize / 2;
52   	}
53   	
54   	template <class R>
55   	void SPxParMultPR<R>::load(SPxSolverBase<R>* p_solver)
56   	{
57   	   this->thesolver = p_solver;
58   	   multiParts = (this->thesolver->dim() + this->thesolver->coDim()) / partialSize + 1;
59   	   pricSet.reSize(10 * partialSize);
60   	}
61   	
62   	template <class R>
63   	SPxId SPxParMultPR<R>::selectEnter()
64   	{
65   	   SPxId id;
66   	   R x;
67   	   int i;
68   	   int best = -1;
69   	   //    const SPxBasisBase<R>::Desc& ds   = this->thesolver->basis().desc();
70   	
71   	   assert(this->thesolver != 0);
72   	   int lastlast = -1;
73   	
74   	   if(this->thesolver->pricing() == SPxSolverBase<R>::PARTIAL)
75   	   {
76   	      R val;
77   	      R tol = -this->thetolerance;
78   	      lastlast = last;
79   	
80   	      for(i = used - 1; i >= 0; --i)
81   	      {
82   	         int n = this->thesolver->number(pricSet[i].id);
83   	
84   	         if(this->thesolver->isId(pricSet[i].id))
85   	         {
86   	            this->thesolver->computePvec(n);
87   	            pricSet[i].test = val = this->thesolver->computeTest(n);
88   	         }
89   	         else
90   	            pricSet[i].test = val = this->thesolver->coTest()[n];
91   	
92   	         if(val >= tol)
93   	            pricSet[i] = pricSet[--used];
94   	      }
95   	
96   	      while(pricSet.size() - used < partialSize)
97   	      {
98   	         best = 0;
99   	
100  	         for(i = 1; i < used; ++i)
101  	         {
102  	            if(pricSet[i].test > pricSet[best].test)
103  	               best = i;
104  	         }
105  	
106  	         pricSet[best] = pricSet[--used];
107  	      }
108  	
109  	      do
110  	      {
111  	         last = (last + 1) % multiParts;
112  	
113  	         for(i = this->thesolver->coDim() - last - 1;
114  	               i >= 0; i -= multiParts)
115  	         {
116  	            this->thesolver->computePvec(i);
117  	            x = this->thesolver->computeTest(i);
118  	
119  	            if(x < tol)
120  	            {
121  	               pricSet[used].id = this->thesolver->id(i);
122  	               pricSet[used].test = x;
123  	               used++;
124  	            }
125  	         }
126  	
127  	         for(i = this->thesolver->dim() - last - 1;
128  	               i >= 0; i -= multiParts)
129  	         {
130  	            x = this->thesolver->coTest()[i];
131  	
132  	            if(x < tol)
133  	            {
134  	               pricSet[used].id = this->thesolver->coId(i);
135  	               pricSet[used].test = x;
136  	               used++;
137  	            }
138  	         }
139  	
140  	         assert(used < pricSet.size());
141  	      }
142  	      while(used < min && last != lastlast);
143  	
144  	      if(used > 0)
145  	      {
146  	         min = (used + 1);
147  	
148  	         if(min < 1)
149  	            min = 1;
150  	
151  	         if(min > partialSize)
152  	            min = partialSize;
153  	
154  	         best = 0;
155  	
156  	         for(i = 1; i < used; ++i)
157  	         {
158  	            if(pricSet[i].test < pricSet[best].test)
159  	               best = i;
160  	         }
161  	
162  	         id = pricSet[best].id;
163  	      }
164  	
165  	      return id;
166  	   }
167  	
168  	   else
169  	   {
170  	      assert(this->thesolver->pricing() == SPxSolverBase<R>::FULL);
171  	      R bestx = -this->thetolerance;
172  	
173  	      for(i = this->thesolver->dim() - 1; i >= 0; --i)
174  	      {
175  	         x = this->thesolver->coTest()[i];
176  	
177  	         // x *= EQ_PREF * (1 + (ds.coStatus(i) == SPxBasisBase<R>::Desc::P_FREE
178  	         //                || ds.coStatus(i) == SPxBasisBase<R>::Desc::D_FREE));
179  	         if(x < bestx)
180  	         {
181  	            id = this->thesolver->coId(i);
182  	            bestx = this->thesolver->coTest()[i];
183  	         }
184  	      }
185  	
186  	      for(i = this->thesolver->coDim() - 1; i >= 0; --i)
187  	      {
188  	         x = this->thesolver->test()[i];
189  	
190  	         // x *= EQ_PREF * (1 + (ds.status(i) == SPxBasisBase<R>::Desc::P_FREE
191  	         //                || ds.status(i) == SPxBasisBase<R>::Desc::D_FREE));
192  	         if(x < bestx)
193  	         {
194  	            id = this->thesolver->id(i);
195  	            bestx = this->thesolver->test()[i];
196  	         }
197  	      }
198  	
199  	      return id;
200  	   }
201  	}
202  	
203  	template <class R>
204  	int SPxParMultPR<R>::selectLeave()
205  	{
206  	   int i, n;
207  	   R x;
208  	   R best = -this->thetolerance;
209  	   //    const R* up  = this->thesolver->ubBound();
210  	   //    const R* low = this->thesolver->lbBound();
211  	
212  	   assert(this->thesolver != 0);
213  	   n = -1;
214  	
215  	   for(i = this->thesolver->dim() - 1; i >= 0; --i)
216  	   {
217  	      x = this->thesolver->fTest()[i];
218  	
219  	      // x *= EQ_PREF * (1 + (up[i] == low[i]));
220  	      if(x < best)
221  	      {
222  	         n = i;
223  	         best = this->thesolver->fTest()[i];
224  	      }
225  	   }
226  	
227  	   return n;
228  	}
229  	} // namespace soplex
230