SoPlex
Loading...
Searching...
No Matches
spxsolver.h
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the class library */
4/* SoPlex --- the Sequential object-oriented simPlex. */
5/* */
6/* Copyright (c) 1996-2025 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/**@file spxsolver.h
26 * @brief main LP solver class
27 */
28#ifndef _SPXSOLVER_H_
29#define _SPXSOLVER_H_
30
31#include <assert.h>
32#include <iostream>
33#include <iomanip>
34#include <sstream>
35
36#include "soplex/spxdefines.h"
37#include "soplex/timer.h"
38#include "soplex/timerfactory.h"
39#include "soplex/spxlp.h"
40#include "soplex/spxbasis.h"
41#include "soplex/array.h"
42#include "soplex/random.h"
43#include "soplex/unitvector.h"
44#include "soplex/updatevector.h"
45#include "soplex/stablesum.h"
46
47#include "soplex/spxlpbase.h"
48
49#define SOPLEX_HYPERPRICINGTHRESHOLD 5000 /**< do (auto) hyper pricing only if problem size (cols+rows) is larger than SOPLEX_HYPERPRICINGTHRESHOLD */
50#define SOPLEX_HYPERPRICINGSIZE 100 /**< size of initial candidate list for hyper pricing */
51#define SOPLEX_SPARSITYFACTOR 0.6 /**< percentage of infeasibilities that is considered sparse */
52#define SOPLEX_DENSEROUNDS 5 /**< number of refactorizations until sparsity is tested again */
53#define SOPLEX_SPARSITY_TRADEOFF 0.8 /**< threshold to decide whether Ids or coIds are preferred to enter the basis;
54 // * coIds are more likely to enter if SOPLEX_SPARSITY_TRADEOFF is close to 0
55 // */
56#define SOPLEX_MAXNCLCKSKIPS 32 /**< maximum number of clock skips (iterations without time measuring) */
57#define SOPLEX_SAFETYFACTOR 1e-2 /**< the probability to skip the clock when the time limit has been reached */
58#define SOPLEX_NINITCALLS 200 /**< the number of clock updates in isTimelimitReached() before clock skipping starts */
59namespace soplex
60{
61template <class R>
62class SPxPricer;
63template <class R>
64class SPxRatioTester;
65template <class R>
66class SPxStarter;
67template <class R>
68class SPxFastRT;
69template <class R>
70class SPxBoundFlippingRT;
71
72/**@brief Sequential object-oriented SimPlex.
73 @ingroup Algo
74
75 SPxSolverBase is an LP solver class using the revised Simplex algorithm. It
76 provides two basis representations, namely a column basis and a row basis
77 (see #Representation). For both representations, a primal and
78 dual algorithm is available (see \ref Type).
79
80 In addition, SPxSolverBase can be customized with various respects:
81 - pricing algorithms using SPxPricer
82 - ratio test using class SPxRatioTester
83 - computation of a start basis using class SPxStarter
84 - preprocessing of the LP using class SPxSimplifier
85 - termination criteria by overriding
86
87 SPxSolverBase is derived from SPxLPBase<R> that is used to store the LP to be solved.
88 Hence, the LPs solved with SPxSolverBase have the general format
89
90 \f[
91 \begin{array}{rl}
92 \hbox{max} & \mbox{maxObj}^T x \\
93 \hbox{s.t.} & \mbox{lhs} \le Ax \le \mbox{rhs} \\
94 & \mbox{low} \le x \le \mbox{up}
95 \end{array}
96 \f]
97
98 Also, SPxLPBase<R> provide all manipulation methods for the LP. They allow
99 SPxSolverBase to be used within cutting plane algorithms.
100*/
101
102template <class R>
103class SPxSolverBase : public SPxLPBase<R>, protected SPxBasisBase<R>
104{
107
108public:
109
110 //-----------------------------
111 /**@name Data Types */
112 ///@{
113 /// LP basis representation.
114 /** Solving LPs with the Simplex algorithm requires the definition of a
115 * \em basis. A basis can be defined as a set of column vectors or a
116 * set of row vectors building a nonsingular matrix. We will refer to
117 * the first case as the \em columnwise representation and the latter
118 * case will be called the \em rowwise representation.
119 *
120 * Type Representation determines the representation of SPxSolverBase, i.e.
121 * a columnwise (#COLUMN == 1) or rowwise (#ROW == -1) one.
122 */
124 {
125 ROW = -1, ///< rowwise representation.
126 COLUMN = 1 ///< columnwise representation.
127 };
128
129 /// Algorithmic type.
130 /** SPxSolverBase uses the reviesed Simplex algorithm to solve LPs.
131 * Mathematically, one distinguishes the \em primal from the
132 * \em dual algorihm. Algorithmically, these relate to the two
133 * types #ENTER or #LEAVE. How they relate, depends on the chosen
134 * basis representation. This is desribed by the following table:
135 *
136 * <TABLE>
137 * <TR><TD>&nbsp;</TD><TD>ENTER </TD><TD>LEAVE </TD></TR>
138 * <TR><TD>ROW </TD><TD>DUAL </TD><TD>PRIMAL</TD></TR>
139 * <TR><TD>COLUMN</TD><TD>PRIMAL</TD><TD>DUAL </TD></TR>
140 * </TABLE>
141 */
142 enum Type
143 {
144 /// Entering Simplex.
145 /** The Simplex loop for the entering Simplex can be sketched
146 * as follows:
147 * - \em Pricing : Select a variable to #ENTER the basis.
148 * - \em Ratio-Test : Select variable to #LEAVE the
149 * basis such that the basis remains feasible.
150 * - Perform the basis update.
151 */
152 ENTER = -1,
153 /// Leaving Simplex.
154 /** The Simplex loop for the leaving Simplex can be sketched
155 * as follows:
156 * - \em Pricing: Select a variable to #LEAVE the basis.
157 * - \em Ratio-Test: Select variable to #ENTER the
158 * basis such that the basis remains priced.
159 * - Perform the basis update.
160 */
162 };
163
164 /// Pricing type.
165 /** In case of the #ENTER%ing Simplex algorithm, for performance
166 * reasons it may be advisable not to compute and maintain up to
167 * date vectors #pVec() and #test() and instead compute only some
168 * of its elements explicitely. This is controled by the #Pricing type.
169 */
171 {
172 /// Full pricing.
173 /** If #FULL pricing in selected for the #ENTER%ing Simplex,
174 * vectors #pVec() and #test() are kept up to date by
175 * SPxSolverBase. An SPxPricer only needs to select an Id such
176 * that the #test() or #coTest() value is < 0.
177 */
179 /// Partial pricing.
180 /** When #PARTIAL pricing in selected for the #ENTER%ing
181 * Simplex, vectors #pVec() and #test() are not set up and
182 * updated by SPxSolverBase. However, vectors #coPvec() and
183 * #coTest() are still kept up to date by SPxSolverBase.
184 * An SPxPricer object needs to compute the values for
185 * #pVec() and #test() itself in order to select an
186 * appropriate pivot with #test() < 0. Methods \ref computePvec(int)
187 * "computePvec(i)" and \ref computeTest(int) "computeTest(i)"
188 * will assist the used to do so. Note
189 * that it may be feasible for a pricer to return an Id with
190 * #test() > 0; such will be rejected by SPxSolverBase.
191 */
193 };
194
196 {
197 ON_UPPER, ///< variable set to its upper bound.
198 ON_LOWER, ///< variable set to its lower bound.
199 FIXED, ///< variable fixed to identical bounds.
200 ZERO, ///< free variable fixed to zero.
201 BASIC, ///< variable is basic.
202 UNDEFINED ///< nothing known about basis status (possibly due to a singular basis in transformed problem)
203 };
204
205 /**@todo In spxchange, change the status to
206 if (m_status > 0) m_status = REGULAR;
207 */
209 {
210 ERROR = -15, ///< an error occured.
211 NO_RATIOTESTER = -14, ///< No ratiotester loaded
212 NO_PRICER = -13, ///< No pricer loaded
213 NO_SOLVER = -12, ///< No linear solver loaded
214 NOT_INIT = -11, ///< not initialised error
215 ABORT_CYCLING = -8, ///< solve() aborted due to detection of cycling.
216 ABORT_TIME = -7, ///< solve() aborted due to time limit.
217 ABORT_ITER = -6, ///< solve() aborted due to iteration limit.
218 ABORT_VALUE = -5, ///< solve() aborted due to objective limit.
219 SINGULAR = -4, ///< Basis is singular, numerical troubles?
220 NO_PROBLEM = -3, ///< No Problem has been loaded.
221 REGULAR = -2, ///< LP has a usable Basis (maybe LP is changed).
222 RUNNING = -1, ///< algorithm is running
223 UNKNOWN = 0, ///< nothing known on loaded problem.
224 OPTIMAL = 1, ///< LP has been solved to optimality.
225 UNBOUNDED = 2, ///< LP has been proven to be primal unbounded.
226 INFEASIBLE = 3, ///< LP has been proven to be primal infeasible.
227 INForUNBD = 4, ///< LP is primal infeasible or unbounded.
228 OPTIMAL_UNSCALED_VIOLATIONS = 5 ///< LP has beed solved to optimality but unscaled solution contains violations.
229 };
230
231 /// objective for solution polishing
233 {
234 POLISH_OFF, ///< don't perform modifications on optimal basis
235 POLISH_INTEGRALITY, ///< maximize number of basic slack variables, i.e. more variables on bounds
236 POLISH_FRACTIONALITY ///< minimize number of basic slack variables, i.e. more variables in between bounds
237 };
238
239
240 ///@}
241
242private:
243
244 //-----------------------------
245 /**@name Private data */
246 ///@{
247 Type theType; ///< entering or leaving algortihm.
248 Pricing thePricing; ///< full or partial pricing.
249 Representation theRep; ///< row or column representation.
250 SolutionPolish polishObj; ///< objective of solution polishing
251 Timer* theTime; ///< time spent in last call to method solve()
252 Timer::TYPE timerType; ///< type of timer (user or wallclock)
253 Real theCumulativeTime; ///< cumulative time spent in all calls to method solve()
254 int maxIters; ///< maximum allowed iterations.
255 Real maxTime; ///< maximum allowed time.
256 int nClckSkipsLeft; ///< remaining number of times the clock can be safely skipped
257 long nCallsToTimelim; /// < the number of calls to the method isTimeLimitReached()
258 R objLimit; ///< objective value limit.
259 bool useTerminationValue; ///< true, if objective limit should be used in the next solve.
260 Status m_status; ///< status of algorithm.
261
262 R m_nonbasicValue; ///< nonbasic part of current objective value
263 bool m_nonbasicValueUpToDate; ///< true, if the stored objValue is up to date
264
265 R m_pricingViol; ///< maximal feasibility violation of current solution
266 bool m_pricingViolUpToDate; ///< true, if the stored violation is up to date
267
268 R
269 m_pricingViolCo; ///< maximal feasibility violation of current solution in coDim
270 bool m_pricingViolCoUpToDate; ///< true, if the stored violation in coDim is up to date
271 int m_numViol; ///< number of violations of current solution
272
273 R entertolscale; ///< factor to temporarily decrease the entering tolerance
274 R leavetolscale; ///< factor to temporarily decrease the leaving tolerance
275 R theShift; ///< sum of all shifts applied to any bound.
276 R lastShift; ///< for forcing feasibility.
277 int m_maxCycle; ///< maximum steps before cycling is detected.
278 int m_numCycle; ///< actual number of degenerate steps so far.
279 bool initialized; ///< true, if all vectors are setup.
280
282 solveVector2; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
284 solveVector2rhs; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
286 solveVector3; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
288 solveVector3rhs; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
290 coSolveVector2; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
292 coSolveVector2rhs; ///< when 2 systems are to be solved at a time; typically for speepest edge weights
294 coSolveVector3; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
296 coSolveVector3rhs; ///< when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)
297
298 bool freePricer; ///< true iff thepricer should be freed inside of object
299 bool freeRatioTester; ///< true iff theratiotester should be freed inside of object
300 bool freeStarter; ///< true iff thestarter should be freed inside of object
301
302 /* Store the index of a leaving variable if only an instable entering variable has been found.
303 instableLeave == true iff this instable basis change should be performed.
304 (see spxsolve.hpp and leave.hpp) */
308
309 /* Store the id of an entering row or column if only an instable pivot has been found.
310 instableEnter == true iff this instable basis change should be performed.
311 (see spxsolve.hpp and enter.hpp) */
315
316 bool
317 recomputedVectors; ///< flag to perform clean up step to reduce numerical errors only once
318
321 R sparsePricingFactor; ///< enable sparse pricing when viols < factor * dim()
322
324 ///< stored stable basis met before a simplex pivot (used to warm start the solver)
326 ///< They don't have setters because only the internal simplex method is meant to fill them
327
328 bool solvingForBoosted; ///< is this solver involved in a higher precision solving scheme?
329 int storeBasisSimplexFreq; ///< number of simplex pivots -1 to perform before storing stable basis
330
331 bool
332 fullPerturbation; ///< whether to perturb the entire problem or just the bounds relevant for the current pivot
333 int
334 printBasisMetric; ///< printing the current basis metric in the log (-1: off, 0: condition estimate, 1: trace, 2: determinant, 3: condition)
335
336 ///@}
337
338protected:
339
340 //-----------------------------
341 /**@name Protected data */
342 ///@{
343 Array < UnitVectorBase<R> > unitVecs; ///< array of unit vectors
344 const SVSetBase<R>* thevectors; ///< the LP vectors according to representation
345 const SVSetBase<R>* thecovectors; ///< the LP coVectors according to representation
346
347 VectorBase<R> primRhs; ///< rhs VectorBase<R> for computing the primal vector
348 UpdateVector<R> primVec; ///< primal vector
349 VectorBase<R> dualRhs; ///< rhs VectorBase<R> for computing the dual vector
350 UpdateVector<R> dualVec; ///< dual vector
351 UpdateVector<R> addVec; ///< storage for thePvec = &addVec
352
353 VectorBase<R> theURbound; ///< Upper Row Feasibility bound
354 VectorBase<R> theLRbound; ///< Lower Row Feasibility bound
355 VectorBase<R> theUCbound; ///< Upper Column Feasibility bound
356 VectorBase<R> theLCbound; ///< Lower Column Feasibility bound
357
358 /** In entering Simplex algorithm, the ratio test must ensure that all
359 * \em basic variables remain within their feasibility bounds. To give fast
360 * acces to them, the bounds of basic variables are copied into the
361 * following two vectors.
362 */
363 VectorBase<R> theUBbound; ///< Upper Basic Feasibility bound
364 VectorBase<R> theLBbound; ///< Lower Basic Feasibility bound
365
366 /** The values of the rhs corresponding to the current basis.*/
368 /** The values of all basis variables. */
370
371 /* The Copricing rhs and VectorBase<R> */
374 /** The pricing VectorBase<R> */
376
377 UpdateVector<R>* theRPvec; ///< row pricing vector
378 UpdateVector<R>* theCPvec; ///< column pricing vector
379
380 // The following vectors serve for the virtualization of shift bounds
381 //@todo In prinziple this schould be references.
382 VectorBase<R>* theUbound; ///< Upper bound for vars
383 VectorBase<R>* theLbound; ///< Lower bound for vars
384 VectorBase<R>* theCoUbound; ///< Upper bound for covars
385 VectorBase<R>* theCoLbound; ///< Lower bound for covars
386
387 // The following vectors serve for the virtualization of testing vectors
390
391 DSVectorBase<R> primalRay; ///< stores primal ray in case of unboundedness
392 DSVectorBase<R> dualFarkas; ///< stores dual farkas proof in case of infeasibility
393
394 int leaveCount; ///< number of LEAVE iterations
395 int enterCount; ///< number of ENTER iterations
396 int primalCount; ///< number of primal iterations
397 int polishCount; ///< number of solution polishing iterations
398
399 int boundflips; ///< number of performed bound flips
400 int totalboundflips; ///< total number of bound flips
401
402 int enterCycles; ///< the number of degenerate steps during the entering algorithm
403 int leaveCycles; ///< the number of degenerate steps during the leaving algorithm
404 int enterDegenCand; ///< the number of degenerate candidates in the entering algorithm
405 int leaveDegenCand; ///< the number of degenerate candidates in the leaving algorithm
406 R primalDegenSum; ///< the sum of the primal degeneracy percentage
407 R dualDegenSum; ///< the sum of the dual degeneracy percentage
408
412
413 R boundrange; ///< absolute range of all bounds in the problem
414 R siderange; ///< absolute range of all side in the problem
415 R objrange; ///< absolute range of all objective coefficients in the problem
416 ///@}
417
418 //-----------------------------
419 /**@name Precision */
420 ///@{
421 /// is the solution precise enough, or should we increase delta() ?
422 virtual bool precisionReached(R& newpricertol) const;
423
424 /// determine ranges of problem values for bounds, sides and objective to assess numerical difficulties
426 ///@}
427
428public:
429
430 /// The random number generator used throughout the whole computation. Its seed can be modified.
432
433 /** For the leaving Simplex algorithm this vector contains the indices of infeasible basic variables;
434 * for the entering Simplex algorithm this vector contains the indices of infeasible slack variables.
435 */
437 /**For the entering Simplex algorithm these vectors contains the indices of infeasible basic variables.
438 */
440
441 /// store indices that were changed in the previous iteration and must be checked in hyper pricing
444
445 /** Binary vectors to store whether basic indices are infeasible
446 * the i-th entry equals false, if the i-th basic variable is not infeasible
447 * the i-th entry equals true, if the i-th basic variable is infeasible
448 */
450 isInfeasible; ///< 0: index not violated, 1: index violated, 2: index violated and among candidate list
452 isInfeasibleCo; ///< 0: index not violated, 1: index violated, 2: index violated and among candidate list
453
454 /// These values enable or disable sparse pricing
455 bool sparsePricingLeave; ///< true if sparsePricing is turned on in the leaving Simplex
456 bool sparsePricingEnter; ///< true if sparsePricing is turned on in the entering Simplex for slack variables
457 bool sparsePricingEnterCo; ///< true if sparsePricing is turned on in the entering Simplex
458 bool hyperPricingLeave; ///< true if hyper sparse pricing is turned on in the leaving Simplex
459 bool hyperPricingEnter; ///< true if hyper sparse pricing is turned on in the entering Simplex
460
461 int remainingRoundsLeave; ///< number of dense rounds/refactorizations until sparsePricing is enabled again
464
465 /// dual pricing norms
466 VectorBase<R> weights; ///< store dual norms
467 VectorBase<R> coWeights; ///< store dual norms
468 bool weightsAreSetup; ///< are the dual norms already set up?
469
470
471 Timer* multTimeSparse; ///< time spent in setupPupdate() exploiting sparsity
472 Timer* multTimeFull; ///< time spent in setupPupdate() ignoring sparsity
473 Timer* multTimeColwise; ///< time spent in setupPupdate(), columnwise multiplication
474 Timer* multTimeUnsetup; ///< time spent in setupPupdate() w/o sparsity information
475 int multSparseCalls; ///< number of products exploiting sparsity
476 int multFullCalls; ///< number of products ignoring sparsity
477 int multColwiseCalls; ///< number of products, columnwise multiplication
478 int multUnsetupCalls; ///< number of products w/o sparsity information
479
480 SPxOut* spxout; ///< message handler
481
483 integerVariables; ///< supplementary variable information, 0: continous variable, 1: integer variable
484
485 //-----------------------------
486 void setOutstream(SPxOut& newOutstream)
487 {
488 spxout = &newOutstream;
489 SPxLPBase<R>::spxout = &newOutstream;
490 }
491
492 /// set the _tolerances member variable
493 virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances)
494 {
495 this->_tolerances = newTolerances;
496 // set tolerances for all the UpdateVectors
497 this->primVec.setTolerances(newTolerances);
498 this->dualVec.setTolerances(newTolerances);
499 this->addVec.setTolerances(newTolerances);
500 this->theFvec->setTolerances(newTolerances);
501 this->theCoPvec->setTolerances(newTolerances);
502 this->thePvec->setTolerances(newTolerances);
503 this->theRPvec->setTolerances(newTolerances);
504 this->theCPvec->setTolerances(newTolerances);
505 }
506
507 /// returns current tolerances
508 const std::shared_ptr<Tolerances>& tolerances() const
509 {
510 return this->_tolerances;
511 }
512
513 /// set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
515 {
517 }
518
519 /// set refactor threshold for fill-in in current factor update compared to fill-in in last factorization
521 {
523 }
524
525 /// set refactor threshold for memory growth in current factor update compared to the last factorization
526 void setMemFactor(R f)
527 {
529 }
530
531 /**@name Access */
532 ///@{
533 /// return the version of SPxSolverBase as number like 123 for 1.2.3
534 int version() const
535 {
536 return SOPLEX_VERSION;
537 }
538 /// return the internal subversion of SPxSolverBase as number
539 int subversion() const
540 {
541 return SOPLEX_SUBVERSION;
542 }
543 /// return the current basis representation.
545 {
546 return theRep;
547 }
548
549 /// return current Type.
550 Type type() const
551 {
552 return theType;
553 }
554
555 /// return current Pricing.
557 {
558 return thePricing;
559 }
560
561 /// return current starter.
563 {
564 return thestarter;
565 }
566 ///@}
567
568 //-----------------------------
569 /**@name Setup
570 * Before solving an LP with an instance of SPxSolverBase,
571 * the following steps must be performed:
572 *
573 * -# Load the LP by copying an external LP or reading it from an
574 * input stream.
575 * -# Setup the pricer to use by loading an \ref soplex::SPxPricer
576 * "SPxPricer" object (if not already done in a previous call).
577 * -# Setup the ratio test method to use by loading an
578 * \ref soplex::SPxRatioTester "SPxRatioTester" object
579 * (if not already done in a previous call).
580 * -# Setup the linear system solver to use by loading an
581 * \ref soplex::SLinSolver "SLinSolver" object
582 * (if not already done in a previous call).
583 * -# Optionally setup an start basis generation method by loading an
584 * \ref soplex::SPxStarter "SPxStarter" object.
585 * -# Optionally setup a start basis by loading a
586 * \ref soplex::SPxBasisBase<R>::Desc "SPxBasisBase<R>::Desc" object.
587 * -# Optionally switch to another basis
588 * \ref soplex::SPxSolverBase<R>::Representation "Representation"
589 * by calling method \ref soplex::SPxSolverBase<R>::setRep() "setRep()".
590 * -# Optionally switch to another algorithm
591 * \ref soplex::SPxSolverBase<R>::Type "Type"
592 * by calling method \ref soplex::SPxSolverBase<R>::setType() "setType()".
593 *
594 * Now the solver is ready for execution. If the loaded LP is to be solved
595 * again from scratch, this can be done with method
596 * \ref soplex::SPxSolverBase<R>::reLoad() "reLoad()". Finally,
597 * \ref soplex::SPxSolverBase<R>::clear() "clear()" removes the LP from the solver.
598 */
599 ///@{
600 /// read LP from input stream.
601 virtual bool read(std::istream& in, NameSet* rowNames = nullptr,
602 NameSet* colNames = nullptr, DIdxSet* intVars = nullptr);
603
604 /// copy LP.
605 virtual void loadLP(const SPxLPBase<R>& LP, bool initSlackBasis = true);
606 /// setup linear solver to use. If \p destroy is true, \p slusolver will be freed in destructor.
607 virtual void setBasisSolver(SLinSolver<R>* slu, const bool destroy = false);
608 /// setup pricer to use. If \p destroy is true, \p pricer will be freed in destructor.
609 virtual void setPricer(SPxPricer<R>* pricer, const bool destroy = false);
610 /// setup ratio-tester to use. If \p destroy is true, \p tester will be freed in destructor.
611 virtual void setTester(SPxRatioTester<R>* tester, const bool destroy = false);
612 /// setup starting basis generator to use. If \p destroy is true, \p starter will be freed in destructor.
613 virtual void setStarter(SPxStarter<R>* starter, const bool destroy = false);
614 /// set a start basis.
615 virtual void loadBasis(const typename SPxBasisBase<R>::Desc&);
616
617 /// initialize #ROW or #COLUMN representation.
619 /// switch to #ROW or #COLUMN representation if not already used.
621 /// set \ref soplex::SPxSolverBase<R>::LEAVE "LEAVE" or \ref soplex::SPxSolverBase<R>::ENTER "ENTER" algorithm.
622 void setType(Type tp);
623 /// set \ref soplex::SPxSolverBase<R>::FULL "FULL" or \ref soplex::SPxSolverBase<R>::PARTIAL "PARTIAL" pricing.
625
626 /// reload LP.
627 virtual void reLoad();
628
629 /// clear all data in solver.
630 virtual void clear();
631
632 /// unscales the LP and reloads the basis
634
635 /// invalidates the basis, triggers refactorization
637
638 /** Load basis from \p filename in MPS format. If \p rowNames and \p
639 * colNames are \c nullptr, default names are used for the constraints and
640 * variables.
641 */
642 virtual bool readBasisFile(const char* filename,
643 const NameSet* rowNames, const NameSet* colNames);
644
645 /** Write basis to \p filename in MPS format. If \p rowNames and \p
646 * colNames are \c nullptr, default names are used for the constraints and
647 * variables.
648 */
649 virtual bool writeBasisFile(const char* filename,
650 const NameSet* rowNames, const NameSet* colNames, const bool cpxFormat = false) const;
651
652 /** Write current LP, basis, and parameter settings.
653 * LP is written in MPS format to "\p filename".mps, basis is written in "\p filename".bas, and parameters
654 * are written to "\p filename".set. If \p rowNames and \p colNames are \c nullptr, default names are used for
655 * the constraints and variables.
656 */
657 virtual bool writeState(const char* filename, const NameSet* rowNames = nullptr,
658 const NameSet* colNames = nullptr, const bool cpxFormat = false,
659 const bool writeZeroObjective = false) const;
660
661 ///@}
662
663 /**@name Solving LPs */
664 ///@{
665 /// solve loaded LP.
666 /** Solves the loaded LP by processing the Simplex iteration until
667 * the termination criteria is fullfilled (see #terminate()).
668 * The SPxStatus of the solver will indicate the reason for termination.
669 * @param interrupt can be set externally to interrupt the solve
670 * @param polish should solution polishing be considered
671 *
672 * @throw SPxStatusException if either no problem, solver, pricer
673 * or ratiotester loaded or if solve is still running when it shouldn't be
674 */
675 virtual Status solve(volatile bool* interrupt = nullptr, bool polish = true);
676
677 /** Identify primal basic variables that have zero reduced costs and
678 * try to pivot them out of the basis to make them tight.
679 * This is supposed to decrease the number of fractional variables
680 * when solving LP relaxations of (mixed) integer programs.
681 * The objective must not be modified during this procedure.
682 * @return true, if objective was modified (due to numerics) and resolving is necessary
683 */
685
686 /// set objective of solution polishing (0: off, 1: max_basic_slack, 2: min_basic_slack)
688 {
689 polishObj = _polishObj;
690 }
691
692 /// return objective of solution polishing
697
698 /// true if objective limit should be used in the next solve
700 {
701 return useTerminationValue;
702 }
703
704 /// toggle objective limit for next solve
705 void toggleTerminationValue(bool enable)
706 {
707 useTerminationValue = enable;
708 }
709
710 /// Status of solution process.
711 Status status() const;
712
713 /// current objective value.
714 /**@return Objective value of the current solution vector
715 * (see #getPrimalSol()).
716 */
717 virtual R value();
718
719 // update nonbasic part of the objective value by the given amount
720 /**@return whether nonbasic part of objective is reliable
721 */
722 bool updateNonbasicValue(R objChange);
723
724 // trigger a recomputation of the nonbasic part of the objective value
726 {
727 m_nonbasicValue = 0.0;
729 }
730
731 /** helper method that computes a fresh factorization of the basis matrix
732 * (if at least one update has been performed)
733 * and recomputes Frhs, Fvec, CoPrhs, Pvec, and the nonbasic values.
734 * In LEAVE the Ftest is recomputed, in ENTER the CoTest and Test are recomputed.
735 *
736 * This method is called to eliminate accumulated errors from LU updates
737 * especially required before checking if the solver can terminate
738 * (optimality or objective limit)
739 */
740 virtual void factorizeAndRecompute();
741
742 /// get solution vector for primal variables.
743 /** This method returns the Status of the basis.
744 * If it is #REGULAR or better,
745 * the primal solution vector of the current basis will be copied
746 * to the argument \p vector. Hence, \p vector must be of dimension
747 * #nCols().
748 *
749 * @throw SPxStatusException if not initialized
750 */
752
753 /// get VectorBase<R> of slack variables.
754 /** This method returns the Status of the basis.
755 * If it is #REGULAR or better,
756 * the slack variables of the current basis will be copied
757 * to the argument \p vector. Hence, \p VectorBase<R> must be of dimension
758 * #nRows().
759 *
760 * @warning Because SPxSolverBase supports range constraints as its
761 * default, slack variables are defined in a nonstandard way:
762 * Let \em x be the current solution vector and \em A the constraint
763 * matrix. Then the vector of slack variables is defined as
764 * \f$s = Ax\f$.
765 *
766 * @throw SPxStatusException if no problem loaded
767 */
769
770 /// get current solution VectorBase<R> for dual variables.
771 /** This method returns the Status of the basis.
772 * If it is #REGULAR or better,
773 * the VectorBase<R> of dual variables of the current basis will be copied
774 * to the argument \p vector. Hence, \p VectorBase<R> must be of dimension
775 * #nRows().
776 *
777 * @warning Even though mathematically, each range constraint would
778 * account for two dual variables (one for each inequaility), only
779 * #nRows() dual variables are setup via the following
780 * construction: Given a range constraint, there are three possible
781 * situations:
782 * - None of its inequalities is tight: The dual variables
783 * for both are 0. However, when shifting (see below)
784 * occurs, it may be set to a value other than 0, which
785 * models a perturbed objective vector.
786 * - Both of its inequalities are tight: In this case the
787 * range constraint models an equality and we adopt the
788 * standard definition.
789 * - One of its inequalities is tight while the other is not:
790 * In this case only the dual variable for the tight
791 * constraint is given with the standard definition, while
792 * the other constraint is implicitely set to 0.
793 *
794 * @throw SPxStatusException if no problem loaded
795 */
797
798 /// get vector of reduced costs.
799 /** This method returns the Status of the basis.
800 * If it is #REGULAR or better,
801 * the vector of reduced costs of the current basis will be copied
802 * to the argument \p vector. Hence, \p vector must be of dimension
803 * #nCols().
804 *
805 * Let \em d denote the vector of dual variables, as defined above,
806 * and \em A the LPs constraint matrix. Then the reduced cost vector
807 * \em r is defined as \f$r^T = c^T - d^TA\f$.
808 *
809 * @throw SPxStatusException if no problem loaded
810 */
812
813 /// get primal ray in case of unboundedness.
814 /// @throw SPxStatusException if no problem loaded
816
817 /// get dual farkas proof of infeasibility.
818 /// @throw SPxStatusException if no problem loaded
820
821 /// print display line of flying table
822 virtual void printDisplayLine(const bool force = false, const bool forceHead = false);
823
824 /// Termination criterion.
825 /** This method is called in each Simplex iteration to determine, if
826 * the algorithm is to terminate. In this case a nonzero value is
827 * returned.
828 *
829 * This method is declared virtual to allow for implementation of
830 * other stopping criteria or using it as callback method within the
831 * Simplex loop, by overriding the method in a derived class.
832 * However, all implementations must terminate with the
833 * statement \c return SPxSolverBase<R>::#terminate(), if no own termination
834 * criteria is encountered.
835 *
836 * Note, that the Simplex loop stopped even when #terminate()
837 * returns 0, if the LP has been solved to optimality (i.e. no
838 * further pricing succeeds and no shift is present).
839 */
840 virtual bool terminate();
841 ///@}
842
843 //-----------------------------
844 /**@name Control Parameters */
845 ///@{
846 /// values \f$|x| < \epsilon\f$ are considered to be 0.
847 /** if you want another value for epsilon, use
848 * \ref soplex::Tolerances::setEpsilon() "Tolerances::setEpsilon()".
849 */
850 R epsilon() const
851 {
852 return this->tolerances()->epsilon();
853 }
854 /// feasibility tolerance maintained by ratio test during ENTER algorithm.
855 R entertol() const
856 {
857 if(theRep == COLUMN)
858 return this->tolerances()->floatingPointFeastol() * this->entertolscale;
859 else
860 return this->tolerances()->floatingPointOpttol() * this->entertolscale;
861 }
862 /// feasibility tolerance maintained by ratio test during LEAVE algorithm.
863 R leavetol() const
864 {
865 if(theRep == COLUMN)
866 return this->tolerances()->floatingPointOpttol() * this->leavetolscale;
867 else
868 return this->tolerances()->floatingPointFeastol() * this->leavetolscale;
869 }
870 /// scale the entering tolerance
872 {
873 this->entertolscale = d;
874 }
875 /// scale the leaving tolerance
877 {
878 this->leavetolscale = d;
879 }
881 {
882 this->scaleEntertol(d);
883 this->scaleLeavetol(d);
884 }
885 /// guaranteed primal and dual bound violation for optimal solution, returning the maximum of floatingPointFeastol() and floatingPointOpttol().
886 R delta() const
887 {
888 return SOPLEX_MAX(this->tolerances()->floatingPointFeastol(),
889 this->tolerances()->floatingPointOpttol());
890 }
891
892 /// set timing type
902
903 /// set timing type
905 {
906 assert(timerType == theTime->type());
907 assert(timerType == multTimeSparse->type());
908 assert(timerType == multTimeFull->type());
909 assert(timerType == multTimeColwise->type());
910 assert(timerType == multTimeUnsetup->type());
911 return timerType;
912 }
913
914 /// set display frequency
915 void setDisplayFreq(int freq)
916 {
917 displayFreq = freq;
918 }
919
920 /// get display frequency
922 {
923 return displayFreq;
924 }
925
926 /// print basis metric within the usual output
928 {
930 }
931
932 // enable sparse pricing when viols < fac * dim()
934 {
936 }
937 /// enable or disable hyper sparse pricing
938 void hyperPricing(bool h);
939
940 // get old basis status rows
945
946 // get old basis status cols
951
952 // should the basis be stored for use in precision boosting?
954 {
956 }
957
958 // set frequency of storing the basis for use in precision boosting
960 {
962 }
963
964 /** SPxSolverBase considers a Simplex step as degenerate if the
965 * steplength does not exceed #epsilon(). Cycling occurs if only
966 * degenerate steps are taken. To prevent this situation, SPxSolverBase
967 * perturbs the problem such that nondegenerate steps are ensured.
968 *
969 * maxCycle() controls how agressive such perturbation is
970 * performed, since no more than maxCycle() degenerate steps are
971 * accepted before perturbing the LP. The current number of consecutive
972 * degenerate steps is counted by numCycle().
973 */
974 /// maximum number of degenerate simplex steps before we detect cycling.
975 int maxCycle() const
976 {
977 return m_maxCycle;
978 }
979 /// actual number of degenerate simplex steps encountered so far.
980 int numCycle() const
981 {
982 return m_numCycle;
983 }
984
985 /// perturb entire problem or only the bounds relevant to the current pivot
986 void useFullPerturbation(bool full)
987 {
988 fullPerturbation = full;
989 }
990
991 virtual R getBasisMetric(int type)
992 {
993 return basis().getMatrixMetric(type);
994 }
995
996 ///@}
997
998private:
999
1000 //-----------------------------
1001 /**@name Private helpers */
1002 ///@{
1003 ///
1004 void localAddRows(int start);
1005 ///
1006 void localAddCols(int start);
1007 ///
1008 void setPrimal(VectorBase<R>& p_vector);
1009 ///
1010 void setSlacks(VectorBase<R>& p_vector);
1011 ///
1012 void setDual(VectorBase<R>& p_vector);
1013 ///
1014 void setRedCost(VectorBase<R>& p_vector);
1015 ///@}
1016
1017protected:
1018
1019 //-----------------------------
1020 /**@name Protected helpers */
1021 ///@{
1022 ///
1023 virtual void addedRows(int n);
1024 ///
1025 virtual void addedCols(int n);
1026 ///
1027 virtual void doRemoveRow(int i);
1028 ///
1029 virtual void doRemoveRows(int perm[]);
1030 ///
1031 virtual void doRemoveCol(int i);
1032 ///
1033 virtual void doRemoveCols(int perm[]);
1034 ///@}
1035
1036public:
1037
1038 //-----------------------------
1039 /**@name Modification */
1040 /// \p scale determines whether the new data needs to be scaled according to the existing LP (persistent scaling)
1041 ///@{
1042 ///
1043 virtual void changeObj(const VectorBase<R>& newObj, bool scale = false);
1044 ///
1045 virtual void changeObj(int i, const R& newVal, bool scale = false);
1046 ///
1047 using SPxLPBase<R>::changeObj; /// overloading a virtual function
1048 virtual void changeObj(SPxColId p_id, const R& p_newVal, bool scale = false)
1049 {
1050 changeObj(this->number(p_id), p_newVal, scale);
1051 }
1052 ///
1053 virtual void changeMaxObj(const VectorBase<R>& newObj, bool scale = false);
1054 ///
1055 virtual void changeMaxObj(int i, const R& newVal, bool scale = false);
1056 ///
1057 using SPxLPBase<R>::changeMaxObj; /// overloading a virtual function
1058 virtual void changeMaxObj(SPxColId p_id, const R& p_newVal, bool scale = false)
1059 {
1060 changeMaxObj(this->number(p_id), p_newVal, scale);
1061 }
1062 ///
1063 virtual void changeRowObj(const VectorBase<R>& newObj, bool scale = false);
1064 ///
1065 virtual void changeRowObj(int i, const R& newVal, bool scale = false);
1066 ///
1067 using SPxLPBase<R>::changeRowObj;
1068 virtual void changeRowObj(SPxRowId p_id, const R& p_newVal, bool scale = false)
1069 {
1070 changeRowObj(this->number(p_id), p_newVal);
1071 }
1072 ///
1073 virtual void clearRowObjs()
1074 {
1076 unInit();
1077 }
1078 ///
1079 virtual void changeLowerStatus(int i, R newLower, R oldLower = 0.0);
1080 ///
1081 virtual void changeLower(const VectorBase<R>& newLower, bool scale = false);
1082 ///
1083 virtual void changeLower(int i, const R& newLower, bool scale = false);
1084 ///
1085 using SPxLPBase<R>::changeLower;
1086 virtual void changeLower(SPxColId p_id, const R& p_newLower, bool scale = false)
1087 {
1088 changeLower(this->number(p_id), p_newLower, scale);
1089 }
1090 ///
1091 virtual void changeUpperStatus(int i, R newUpper, R oldLower = 0.0);
1092 ///
1093 virtual void changeUpper(const VectorBase<R>& newUpper, bool scale = false);
1094 ///
1095 virtual void changeUpper(int i, const R& newUpper, bool scale = false);
1096 ///
1097 using SPxLPBase<R>::changeUpper; /// overloading virtual function
1098 virtual void changeUpper(SPxColId p_id, const R& p_newUpper, bool scale = false)
1099 {
1100 changeUpper(this->number(p_id), p_newUpper, scale);
1101 }
1102 ///
1103 virtual void changeBounds(const VectorBase<R>& newLower, const VectorBase<R>& newUpper,
1104 bool scale = false);
1105 ///
1106 virtual void changeBounds(int i, const R& newLower, const R& newUpper, bool scale = false);
1107 ///
1108 using SPxLPBase<R>::changeBounds;
1109 virtual void changeBounds(SPxColId p_id, const R& p_newLower, const R& p_newUpper,
1110 bool scale = false)
1111 {
1112 changeBounds(this->number(p_id), p_newLower, p_newUpper, scale);
1113 }
1114 ///
1115 virtual void changeLhsStatus(int i, R newLhs, R oldLhs = 0.0);
1116 ///
1117 virtual void changeLhs(const VectorBase<R>& newLhs, bool scale = false);
1118 ///
1119 virtual void changeLhs(int i, const R& newLhs, bool scale = false);
1120 ///
1121 using SPxLPBase<R>::changeLhs;
1122 virtual void changeLhs(SPxRowId p_id, const R& p_newLhs, bool scale = false)
1123 {
1124 changeLhs(this->number(p_id), p_newLhs, scale);
1125 }
1126 ///
1127 virtual void changeRhsStatus(int i, R newRhs, R oldRhs = 0.0);
1128 ///
1129 virtual void changeRhs(const VectorBase<R>& newRhs, bool scale = false);
1130 ///
1131 virtual void changeRhs(int i, const R& newRhs, bool scale = false);
1132 ///
1133 using SPxLPBase<R>::changeRhs;
1134 virtual void changeRhs(SPxRowId p_id, const R& p_newRhs, bool scale = false)
1135 {
1136 changeRhs(this->number(p_id), p_newRhs, scale);
1137 }
1138 ///
1139 virtual void changeRange(const VectorBase<R>& newLhs, const VectorBase<R>& newRhs,
1140 bool scale = false);
1141 ///
1142 virtual void changeRange(int i, const R& newLhs, const R& newRhs, bool scale = false);
1143 ///
1144 using SPxLPBase<R>::changeRange;
1145 virtual void changeRange(SPxRowId p_id, const R& p_newLhs, const R& p_newRhs, bool scale = false)
1146 {
1147 changeRange(this->number(p_id), p_newLhs, p_newRhs, scale);
1148 }
1149 ///
1150 virtual void changeRow(int i, const LPRowBase<R>& newRow, bool scale = false);
1151 ///
1152 using SPxLPBase<R>::changeRow;
1153 virtual void changeRow(SPxRowId p_id, const LPRowBase<R>& p_newRow, bool scale = false)
1154 {
1155 changeRow(this->number(p_id), p_newRow, scale);
1156 }
1157 ///
1158 virtual void changeCol(int i, const LPColBase<R>& newCol, bool scale = false);
1159 ///
1160 using SPxLPBase<R>::changeCol;
1161 virtual void changeCol(SPxColId p_id, const LPColBase<R>& p_newCol, bool scale = false)
1162 {
1163 changeCol(this->number(p_id), p_newCol, scale);
1164 }
1165 ///
1166 virtual void changeElement(int i, int j, const R& val, bool scale = false);
1167 ///
1168 using SPxLPBase<R>::changeElement;
1169 virtual void changeElement(SPxRowId rid, SPxColId cid, const R& val, bool scale = false)
1170 {
1171 changeElement(this->number(rid), this->number(cid), val, scale);
1172 }
1173 ///
1174 virtual void changeSense(typename SPxLPBase<R>::SPxSense sns);
1175 ///@}
1176
1177 //------------------------------------
1178 /**@name Dimension and codimension */
1179 ///@{
1180 /// dimension of basis matrix.
1181 int dim() const
1182 {
1183 return thecovectors->num();
1184 }
1185 /// codimension.
1186 int coDim() const
1187 {
1188 return thevectors->num();
1189 }
1190 ///@}
1191
1192 //------------------------------------
1193 /**@name Variables and Covariables
1194 * Class SPxLPBase<R> introduces \ref soplex::SPxId "SPxIds" to identify
1195 * row or column data of an LP. SPxSolverBase uses this concept to
1196 * access data with respect to the chosen representation.
1197 */
1198 ///@{
1199 /// id of \p i 'th vector.
1200 /** The \p i 'th Id is the \p i 'th SPxRowId for a rowwise and the
1201 * \p i 'th SPxColId for a columnwise basis represenation. Hence,
1202 * 0 <= i < #coDim().
1203 */
1204 SPxId id(int i) const
1205 {
1206 if(rep() == ROW)
1207 {
1208 SPxRowId rid = SPxLPBase<R>::rId(i);
1209 return SPxId(rid);
1210 }
1211 else
1212 {
1213 SPxColId cid = SPxLPBase<R>::cId(i);
1214 return SPxId(cid);
1215 }
1216 }
1217
1218 /// id of \p i 'th covector.
1219 /** The \p i 'th #coId() is the \p i 'th SPxColId for a rowwise and the
1220 * \p i 'th SPxRowId for a columnwise basis represenation. Hence,
1221 * 0 <= i < #dim().
1222 */
1223 SPxId coId(int i) const
1224 {
1225 if(rep() == ROW)
1226 {
1227 SPxColId cid = SPxLPBase<R>::cId(i);
1228 return SPxId(cid);
1229 }
1230 else
1231 {
1232 SPxRowId rid = SPxLPBase<R>::rId(i);
1233 return SPxId(rid);
1234 }
1235 }
1236
1237 /// Is \p p_id an SPxId ?
1238 /** This method returns wheather or not \p p_id identifies a vector
1239 * with respect to the chosen representation.
1240 */
1241 bool isId(const SPxId& p_id) const
1242 {
1243 return p_id.info * theRep > 0;
1244 }
1245
1246 /// Is \p p_id a CoId.
1247 /** This method returns wheather or not \p p_id identifies a coVector
1248 * with respect to the chosen representation.
1249 */
1250 bool isCoId(const SPxId& p_id) const
1251 {
1252 return p_id.info * theRep < 0;
1253 }
1254 ///@}
1255
1256 //------------------------------------
1257 /**@name Vectors and Covectors */
1258 ///@{
1259 /// \p i 'th vector.
1260 /**@return a reference to the \p i 'th, 0 <= i < #coDim(), vector of
1261 * the loaded LP (with respect to the chosen representation).
1262 */
1263 const SVectorBase<R>& vector(int i) const
1264 {
1265 return (*thevectors)[i];
1266 }
1267
1268 ///
1269 const SVectorBase<R>& vector(const SPxRowId& rid) const
1270 {
1271 assert(rid.isValid());
1272 return (rep() == ROW)
1273 ? (*thevectors)[this->number(rid)]
1274 : static_cast<const SVectorBase<R>&>(unitVecs[this->number(rid)]);
1275 }
1276 ///
1277 const SVectorBase<R>& vector(const SPxColId& cid) const
1278 {
1279 assert(cid.isValid());
1280 return (rep() == COLUMN)
1281 ? (*thevectors)[this->number(cid)]
1282 : static_cast<const SVectorBase<R>&>(unitVecs[this->number(cid)]);
1283 }
1284
1285 /// VectorBase<R> associated to \p p_id.
1286 /**@return Returns a reference to the VectorBase<R> of the loaded LP corresponding
1287 * to \p id (with respect to the chosen representation). If \p p_id is
1288 * an id, a vector of the constraint matrix is returned, otherwise
1289 * the corresponding unit vector (of the slack variable or bound
1290 * inequality) is returned.
1291 * @todo The implementation does not exactly look like it will do
1292 * what is promised in the describtion.
1293 */
1294 const SVectorBase<R>& vector(const SPxId& p_id) const
1295 {
1296 assert(p_id.isValid());
1297
1298 return p_id.isSPxRowId()
1299 ? vector(SPxRowId(p_id))
1300 : vector(SPxColId(p_id));
1301 }
1302
1303 /// \p i 'th covector of LP.
1304 /**@return a reference to the \p i 'th, 0 <= i < #dim(), covector of
1305 * the loaded LP (with respect to the chosen representation).
1306 */
1307 const SVectorBase<R>& coVector(int i) const
1308 {
1309 return (*thecovectors)[i];
1310 }
1311 ///
1312 const SVectorBase<R>& coVector(const SPxRowId& rid) const
1313 {
1314 assert(rid.isValid());
1315 return (rep() == COLUMN)
1316 ? (*thecovectors)[this->number(rid)]
1317 : static_cast<const SVector&>(unitVecs[this->number(rid)]);
1318 }
1319 ///
1320 const SVectorBase<R>& coVector(const SPxColId& cid) const
1321 {
1322 assert(cid.isValid());
1323 return (rep() == ROW)
1324 ? (*thecovectors)[this->number(cid)]
1325 : static_cast<const SVectorBase<R>&>(unitVecs[this->number(cid)]);
1326 }
1327 /// coVector associated to \p p_id.
1328 /**@return a reference to the covector of the loaded LP
1329 * corresponding to \p p_id (with respect to the chosen
1330 * representation). If \p p_id is a coid, a covector of the constraint
1331 * matrix is returned, otherwise the corresponding unit vector is
1332 * returned.
1333 */
1334 const SVectorBase<R>& coVector(const SPxId& p_id) const
1335 {
1336 assert(p_id.isValid());
1337 return p_id.isSPxRowId()
1338 ? coVector(SPxRowId(p_id))
1339 : coVector(SPxColId(p_id));
1340 }
1341 /// return \p i 'th unit vector.
1342 const SVectorBase<R>& unitVector(int i) const
1343 {
1344 return unitVecs[i];
1345 }
1346 ///@}
1347
1348 //------------------------------------
1349 /**@name Variable status
1350 * The Simplex basis assigns a \ref soplex::SPxBasisBase<R>::Desc::Status
1351 * "Status" to each variable and covariable. Depending on the
1352 * representation, the status indicates that the corresponding
1353 * vector is in the basis matrix or not.
1354 */
1355 ///@{
1356 /// Status of \p i 'th variable.
1358 {
1359 return this->desc().status(i);
1360 }
1361
1362 /// Status of \p i 'th covariable.
1364 {
1365 return this->desc().coStatus(i);
1366 }
1367
1368 /// does \p stat describe a basic index ?
1369 bool isBasic(typename SPxBasisBase<R>::Desc::Status stat) const
1370 {
1371 return (stat * rep() > 0);
1372 }
1373
1374 /// is the \p p_id 'th vector basic ?
1375 bool isBasic(const SPxId& p_id) const
1376 {
1377 assert(p_id.isValid());
1378 return p_id.isSPxRowId()
1379 ? isBasic(SPxRowId(p_id))
1380 : isBasic(SPxColId(p_id));
1381 }
1382
1383 /// is the \p rid 'th vector basic ?
1384 bool isBasic(const SPxRowId& rid) const
1385 {
1386 return isBasic(this->desc().rowStatus(this->number(rid)));
1387 }
1388
1389 /// is the \p cid 'th vector basic ?
1390 bool isBasic(const SPxColId& cid) const
1391 {
1392 return isBasic(this->desc().colStatus(this->number(cid)));
1393 }
1394
1395 /// is the \p i 'th row vector basic ?
1396 bool isRowBasic(int i) const
1397 {
1398 return isBasic(this->desc().rowStatus(i));
1399 }
1400
1401 /// is the \p i 'th column vector basic ?
1402 bool isColBasic(int i) const
1403 {
1404 return isBasic(this->desc().colStatus(i));
1405 }
1406
1407 /// is the \p i 'th vector basic ?
1408 bool isBasic(int i) const
1409 {
1410 return isBasic(this->desc().status(i));
1411 }
1412
1413 /// is the \p i 'th covector basic ?
1414 bool isCoBasic(int i) const
1415 {
1416 return isBasic(this->desc().coStatus(i));
1417 }
1418 ///@}
1419
1420 /// feasibility vector.
1421 /** This method return the \em feasibility vector. If it satisfies its
1422 * bound, the basis is called feasible (independently of the chosen
1423 * representation). The feasibility vector has dimension #dim().
1424 *
1425 * For the entering Simplex, #fVec is kept within its bounds. In
1426 * contrast to this, the pricing of the leaving Simplex selects an
1427 * element of #fVec, that violates its bounds.
1428 */
1430 {
1431 return *theFvec;
1432 }
1433 /// right-hand side vector for \ref soplex::SPxSolverBase<R>::fVec "fVec"
1434 /** The feasibility vector is computed by solving a linear system with the
1435 * basis matrix. The right-hand side vector of this system is referred
1436 * to as \em feasibility, \em right-hand \em side \em vector #fRhs().
1437 *
1438 * For a row basis, #fRhs() is the objective vector (ignoring shifts).
1439 * For a column basis, it is the sum of all nonbasic vectors scaled by
1440 * the factor of their bound.
1441 */
1442 const VectorBase<R>& fRhs() const
1443 {
1444 return *theFrhs;
1445 }
1446 /// upper bound for \ref soplex::SPxSolverBase<R>::fVec "fVec".
1447 const VectorBase<R>& ubBound() const
1448 {
1449 return theUBbound;
1450 }
1451 /// upper bound for #fVec, writable.
1452 /** This method returns the upper bound for the feasibility vector.
1453 * It may only be called for the #ENTER%ing Simplex.
1454 *
1455 * For the #ENTER%ing Simplex algorithms, the feasibility vector is
1456 * maintained to fullfill its bounds. As #fVec itself, also its
1457 * bounds depend on the chosen representation. Further, they may
1458 * need to be shifted (see below).
1459 */
1461 {
1462 return theUBbound;
1463 }
1464 /// lower bound for \ref soplex::SPxSolverBase<R>::fVec "fVec".
1465 const VectorBase<R>& lbBound() const
1466 {
1467 return theLBbound;
1468 }
1469 /// lower bound for #fVec, writable.
1470 /** This method returns the lower bound for the feasibility vector.
1471 * It may only be called for the #ENTER%ing Simplex.
1472 *
1473 * For the #ENTER%ing Simplex algorithms, the feasibility vector is
1474 * maintained to fullfill its bounds. As #fVec itself, also its
1475 * bound depend on the chosen representation. Further, they may
1476 * need to be shifted (see below).
1477 */
1479 {
1480 return theLBbound;
1481 }
1482
1483 /// Violations of \ref soplex::SPxSolverBase<R>::fVec "fVec"
1484 /** For the leaving Simplex algorithm, pricing involves selecting a
1485 * variable from #fVec that violates its bounds that is to leave
1486 * the basis. When a SPxPricer is called to select such a
1487 * leaving variable, #fTest() contains the vector of violations:
1488 * For #fTest()[i] < 0, the \c i 'th basic variable violates one of
1489 * its bounds by the given value. Otherwise no bound is violated.
1490 */
1491 const VectorBase<R>& fTest() const
1492 {
1493 assert(type() == LEAVE);
1494 return theCoTest;
1495 }
1496
1497 /// copricing vector.
1498 /** The copricing vector #coPvec along with the pricing vector
1499 * #pVec are used for pricing in the #ENTER%ing Simplex algorithm,
1500 * i.e. one variable is selected, that violates its bounds. In
1501 * contrast to this, the #LEAVE%ing Simplex algorithm keeps both
1502 * vectors within their bounds.
1503 */
1505 {
1506 return *theCoPvec;
1507 }
1508
1509 /// Right-hand side vector for \ref soplex::SPxSolverBase<R>::coPvec "coPvec".
1510 /** The vector #coPvec is computed by solving a linear system with the
1511 * basis matrix and #coPrhs as the right-hand side vector. For
1512 * column basis representation, #coPrhs is build up of the
1513 * objective vector elements of all basic variables. For a row
1514 * basis, it consists of the tight bounds of all basic
1515 * constraints.
1516 */
1517 const VectorBase<R>& coPrhs() const
1518 {
1519 return *theCoPrhs;
1520 }
1521
1522 ///
1523 const VectorBase<R>& ucBound() const
1524 {
1525 assert(theType == LEAVE);
1526 return *theCoUbound;
1527 }
1528 /// upper bound for #coPvec.
1529 /** This method returns the upper bound for #coPvec. It may only be
1530 * called for the leaving Simplex algorithm.
1531 *
1532 * For the leaving Simplex algorithms #coPvec is maintained to
1533 * fullfill its bounds. As #coPvec itself, also its bound depend
1534 * on the chosen representation. Further, they may need to be
1535 * shifted (see below).
1536 */
1538 {
1539 assert(theType == LEAVE);
1540 return *theCoUbound;
1541 }
1542
1543 ///
1544 const VectorBase<R>& lcBound() const
1545 {
1546 assert(theType == LEAVE);
1547 return *theCoLbound;
1548 }
1549 /// lower bound for #coPvec.
1550 /** This method returns the lower bound for #coPvec. It may only be
1551 * called for the leaving Simplex algorithm.
1552 *
1553 * For the leaving Simplex algorithms #coPvec is maintained to
1554 * fullfill its bounds. As #coPvec itself, also its bound depend
1555 * on the chosen representation. Further, they may need to be
1556 * shifted (see below).
1557 */
1559 {
1560 assert(theType == LEAVE);
1561 return *theCoLbound;
1562 }
1563
1564 /// violations of \ref soplex::SPxSolverBase<R>::coPvec "coPvec".
1565 /** In entering Simplex pricing selects checks vectors #coPvec()
1566 * and #pVec() for violation of its bounds. #coTest() contains
1567 * the violations for #coPvec() which are indicated by a negative
1568 * value. That is, if #coTest()[i] < 0, the \p i 'th element of #coPvec()
1569 * is violated by -#coTest()[i].
1570 */
1571 const VectorBase<R>& coTest() const
1572 {
1573 assert(type() == ENTER);
1574 return theCoTest;
1575 }
1576 /// pricing vector.
1577 /** The pricing vector #pVec is the product of #coPvec with the
1578 * constraint matrix. As #coPvec, also #pVec is maintained within
1579 * its bound for the leaving Simplex algorithm, while the bounds
1580 * are tested for the entering Simplex. #pVec is of dimension
1581 * #coDim(). Vector #pVec() is only up to date for #LEAVE%ing
1582 * Simplex or #FULL pricing in #ENTER%ing Simplex.
1583 */
1585 {
1586 return *thePvec;
1587 }
1588 ///
1589 const VectorBase<R>& upBound() const
1590 {
1591 assert(theType == LEAVE);
1592 return *theUbound;
1593 }
1594 /// upper bound for #pVec.
1595 /** This method returns the upper bound for #pVec. It may only be
1596 * called for the leaving Simplex algorithm.
1597 *
1598 * For the leaving Simplex algorithms #pVec is maintained to
1599 * fullfill its bounds. As #pVec itself, also its bound depend
1600 * on the chosen representation. Further, they may need to be
1601 * shifted (see below).
1602 */
1604 {
1605 assert(theType == LEAVE);
1606 return *theUbound;
1607 }
1608
1609 ///
1610 const VectorBase<R>& lpBound() const
1611 {
1612 assert(theType == LEAVE);
1613 return *theLbound;
1614 }
1615 /// lower bound for #pVec.
1616 /** This method returns the lower bound for #pVec. It may only be
1617 * called for the leaving Simplex algorithm.
1618 *
1619 * For the leaving Simplex algorithms #pVec is maintained to
1620 * fullfill its bounds. As #pVec itself, also its bound depend
1621 * on the chosen representation. Further, they may need to be
1622 * shifted (see below).
1623 */
1625 {
1626 assert(theType == LEAVE);
1627 return *theLbound;
1628 }
1629
1630 /// Violations of \ref soplex::SPxSolverBase<R>::pVec "pVec".
1631 /** In entering Simplex pricing selects checks vectors #coPvec()
1632 * and #pVec() for violation of its bounds. Vector #test()
1633 * contains the violations for #pVec(), i.e., if #test()[i] < 0,
1634 * the i'th element of #pVec() is violated by #test()[i].
1635 * Vector #test() is only up to date for #FULL pricing.
1636 */
1637 const VectorBase<R>& test() const
1638 {
1639 assert(type() == ENTER);
1640 return theTest;
1641 }
1642
1643 /// compute and return \ref soplex::SPxSolverBase<R>::pVec() "pVec()"[i].
1644 R computePvec(int i);
1645 /// compute entire \ref soplex::SPxSolverBase<R>::pVec() "pVec()".
1647 /// compute and return \ref soplex::SPxSolverBase<R>::test() "test()"[i] in \ref soplex::SPxSolverBase<R>::ENTER "ENTER"ing Simplex.
1648 R computeTest(int i);
1649 /// compute test VectorBase<R> in \ref soplex::SPxSolverBase<R>::ENTER "ENTER"ing Simplex.
1651
1652 //------------------------------------
1653 /**@name Shifting
1654 * The task of the ratio test (implemented in SPxRatioTester classes)
1655 * is to select a variable for the basis update, such that the basis
1656 * remains priced (i.e. both, the pricing and copricing vectors satisfy
1657 * their bounds) or feasible (i.e. the feasibility vector satisfies its
1658 * bounds). However, this can lead to numerically instable basis matrices
1659 * or -- after accumulation of various errors -- even to a singular basis
1660 * matrix.
1661 *
1662 * The key to overcome this problem is to allow the basis to become "a
1663 * bit" infeasible or unpriced, in order provide a better choice for the
1664 * ratio test to select a stable variable. This is equivalent to enlarging
1665 * the bounds by a small amount. This is referred to as \em shifting.
1666 *
1667 * These methods serve for shifting feasibility bounds, either in order
1668 * to maintain numerical stability or initially for computation of
1669 * phase 1. The sum of all shifts applied to any bound is stored in
1670 * \ref soplex::SPxSolverBase<R>::theShift "theShift".
1671 *
1672 * The following methods are used to shift individual bounds. They are
1673 * mainly intended for stable implenentations of SPxRatioTester.
1674 */
1675 ///@{
1676 /// Perform initial shifting to optain an feasible or pricable basis.
1678 /// Perform initial shifting to optain an feasible or pricable basis.
1680
1681 /// shift \p i 'th \ref soplex::SPxSolver::ubBound "ubBound" to \p to.
1682 void shiftUBbound(int i, R to)
1683 {
1684 assert(theType == ENTER);
1685 // use maximum to not count tightened bounds in case of equality shifts
1686 theShift += SOPLEX_MAX(to - theUBbound[i], 0.0);
1687 theUBbound[i] = to;
1688 }
1689 /// shift \p i 'th \ref soplex::SPxSolver::lbBound "lbBound" to \p to.
1690 void shiftLBbound(int i, R to)
1691 {
1692 assert(theType == ENTER);
1693 // use maximum to not count tightened bounds in case of equality shifts
1694 theShift += SOPLEX_MAX(theLBbound[i] - to, 0.0);
1695 theLBbound[i] = to;
1696 }
1697 /// shift \p i 'th \ref soplex::SPxSolver::upBound "upBound" to \p to.
1698 void shiftUPbound(int i, R to)
1699 {
1700 assert(theType == LEAVE);
1701 // use maximum to not count tightened bounds in case of equality shifts
1702 theShift += SOPLEX_MAX(to - (*theUbound)[i], 0.0);
1703 (*theUbound)[i] = to;
1704 }
1705 /// shift \p i 'th \ref soplex::SPxSolver::lpBound "lpBound" to \p to.
1706 void shiftLPbound(int i, R to)
1707 {
1708 assert(theType == LEAVE);
1709 // use maximum to not count tightened bounds in case of equality shifts
1710 theShift += SOPLEX_MAX((*theLbound)[i] - to, 0.0);
1711 (*theLbound)[i] = to;
1712 }
1713 /// shift \p i 'th \ref soplex::SPxSolver::ucBound "ucBound" to \p to.
1714 void shiftUCbound(int i, R to)
1715 {
1716 assert(theType == LEAVE);
1717 // use maximum to not count tightened bounds in case of equality shifts
1718 theShift += SOPLEX_MAX(to - (*theCoUbound)[i], 0.0);
1719 (*theCoUbound)[i] = to;
1720 }
1721 /// shift \p i 'th \ref soplex::SPxSolver::lcBound "lcBound" to \p to.
1722 void shiftLCbound(int i, R to)
1723 {
1724 assert(theType == LEAVE);
1725 // use maximum to not count tightened bounds in case of equality shifts
1726 theShift += SOPLEX_MAX((*theCoLbound)[i] - to, 0.0);
1727 (*theCoLbound)[i] = to;
1728 }
1729 ///
1730 void testBounds() const;
1731
1732 /// total current shift amount.
1733 virtual R shift() const
1734 {
1735 return theShift;
1736 }
1737 /// remove shift as much as possible.
1738 virtual void unShift(void);
1739
1740 /// get violation of constraints.
1741 virtual void qualConstraintViolation(R& maxviol, R& sumviol) const;
1742 /// get violations of bounds.
1743 virtual void qualBoundViolation(R& maxviol, R& sumviol) const;
1744 /// get the residuum |Ax-b|.
1745 virtual void qualSlackViolation(R& maxviol, R& sumviol) const;
1746 /// get violation of optimality criterion.
1747 virtual void qualRedCostViolation(R& maxviol, R& sumviol) const;
1748 ///@}
1749
1750private:
1751
1752 //------------------------------------
1753 /**@name Perturbation */
1754 ///@{
1755 ///
1757 const UpdateVector<R>& vec, VectorBase<R>& low, VectorBase<R>& up, R eps, R delta,
1758 int start = 0, int incr = 1);
1759 ///
1761 const UpdateVector<R>& vec, VectorBase<R>& low, VectorBase<R>& up, R eps, R delta,
1762 int start = 0, int incr = 1);
1763 ///
1765 VectorBase<R>& low, VectorBase<R>& up, R eps, R delta,
1766 const typename SPxBasisBase<R>::Desc::Status* stat, int start, int incr);
1767 ///
1769 VectorBase<R>& low, VectorBase<R>& up, R eps, R delta,
1770 const typename SPxBasisBase<R>::Desc::Status* stat, int start, int incr);
1771 ///@}
1772
1773 //------------------------------------
1774 /**@name The Simplex Loop
1775 * We now present a set of methods that may be usefull when implementing
1776 * own SPxPricer or SPxRatioTester classes. Here is, how
1777 * SPxSolverBase will call methods from its loaded SPxPricer and
1778 * SPxRatioTester.
1779 *
1780 * For the entering Simplex:
1781 * -# \ref soplex::SPxPricer::selectEnter() "SPxPricer::selectEnter()"
1782 * -# \ref soplex::SPxRatioTester::selectLeave() "SPxRatioTester::selectLeave()"
1783 * -# \ref soplex::SPxPricer::entered4() "SPxPricer::entered4()"
1784 *
1785 * For the leaving Simplex:
1786 * -# \ref soplex::SPxPricer::selectLeave() "SPxPricer::selectLeave()"
1787 * -# \ref soplex::SPxRatioTester::selectEnter() "SPxRatioTester::selectEnter()"
1788 * -# \ref soplex::SPxPricer::left4() "SPxPricer::left4()"
1789 */
1790 ///@{
1791public:
1792 /// Setup vectors to be solved within Simplex loop.
1793 /** Load vector \p y to be #solve%d with the basis matrix during the
1794 * #LEAVE Simplex. The system will be solved after #SPxSolverBase%'s call
1795 * to SPxRatioTester. The system will be solved along with
1796 * another system. Solving two linear system at a time has
1797 * performance advantages over solving the two linear systems
1798 * seperately.
1799 */
1801 {
1802 assert(type() == LEAVE);
1803 solveVector2 = p_y;
1804 solveVector2rhs = p_rhs;
1805 }
1806 /// Setup vectors to be solved within Simplex loop.
1807 /** Load a second additional vector \p y2 to be #solve%d with the
1808 * basis matrix during the #LEAVE Simplex. The system will be
1809 * solved after #SPxSolverBase%'s call to SPxRatioTester.
1810 * The system will be solved along with at least one
1811 * other system. Solving several linear system at a time has
1812 * performance advantages over solving them seperately.
1813 */
1815 {
1816 assert(type() == LEAVE);
1817 solveVector3 = p_y2;
1818 solveVector3rhs = p_rhs2;
1819 }
1820 /// Setup vectors to be cosolved within Simplex loop.
1821 /** Load vector \p y to be #coSolve%d with the basis matrix during
1822 * the #ENTER Simplex. The system will be solved after #SPxSolverBase%'s
1823 * call to SPxRatioTester. The system will be solved along
1824 * with another system. Solving two linear system at a time has
1825 * performance advantages over solving the two linear systems
1826 * seperately.
1827 */
1829 {
1830 assert(type() == ENTER);
1831 coSolveVector2 = p_y;
1832 coSolveVector2rhs = p_rhs;
1833 }
1834 /// Setup vectors to be cosolved within Simplex loop.
1835 /** Load a second vector \p z to be #coSolve%d with the basis matrix during
1836 * the #ENTER Simplex. The system will be solved after #SPxSolverBase%'s
1837 * call to SPxRatioTester. The system will be solved along
1838 * with two other systems.
1839 */
1841 {
1842 assert(type() == ENTER);
1843 coSolveVector3 = p_z;
1844 coSolveVector3rhs = p_rhs;
1845 }
1846
1847 /// maximal infeasibility of basis
1848 /** This method is called before concluding optimality. Since it is
1849 * possible that some stable implementation of class
1850 * SPxRatioTester yielded a slightly infeasible (or unpriced)
1851 * basis, this must be checked before terminating with an optimal
1852 * solution.
1853 */
1854 virtual R maxInfeas() const;
1855
1856 /// check for violations above tol and immediately return false w/o checking the remaining values
1857 /** This method is useful for verifying whether an objective limit can be used as termination criterion
1858 */
1859 virtual bool noViols(R tol) const;
1860
1861 /// Return current basis.
1862 /**@note The basis can be used to solve linear systems or use
1863 * any other of its (const) methods. It is, however, encuraged
1864 * to use methods #setup4solve() and #setup4coSolve() for solving
1865 * systems, since this is likely to have perfomance advantages.
1866 */
1867 const SPxBasisBase<R>& basis() const
1868 {
1869 return *this;
1870 }
1871 ///
1873 {
1874 return *this;
1875 }
1876 /// return loaded SPxPricer.
1877 const SPxPricer<R>* pricer() const
1878 {
1879 return thepricer;
1880 }
1881 /// return loaded SLinSolver.
1883 {
1885 }
1886 /// return loaded SPxRatioTester.
1888 {
1889 return theratiotester;
1890 }
1891
1892 /// Factorize basis matrix.
1893 /// @throw SPxStatusException if loaded matrix is singular
1894 virtual void factorize();
1895
1896private:
1897
1898 /** let index \p i leave the basis and manage entering of another one.
1899 @returns \c false if LP is unbounded/infeasible. */
1900 bool leave(int i, bool polish = false);
1901 /** let id enter the basis and manage leaving of another one.
1902 @returns \c false if LP is unbounded/infeasible. */
1903 bool enter(SPxId& id, bool polish = false);
1904
1905 /// test coVector \p i with status \p stat.
1906 R coTest(int i, typename SPxBasisBase<R>::Desc::Status stat) const;
1907 /// compute coTest vector.
1909 /// recompute coTest vector.
1911
1912 /// test VectorBase<R> \p i with status \p stat.
1913 R test(int i, typename SPxBasisBase<R>::Desc::Status stat) const;
1914 /// recompute test vector.
1916
1917 /// compute basis feasibility test vector.
1919 /// update basis feasibility test vector.
1921
1922 ///@}
1923
1924 //------------------------------------
1925 /**@name Parallelization
1926 * In this section we present the methods, that are provided in order to
1927 * allow a parallel version to be implemented as a derived class, thereby
1928 * inheriting most of the code of SPxSolverBase.
1929 *
1930 * @par Initialization
1931 * These methods are used to setup all the vectors used in the Simplex
1932 * loop, that where described in the previous sectios.
1933 */
1934 ///@{
1935public:
1936 /// intialize data structures.
1937 /** If SPxSolverBase is not \ref isInitialized() "initialized", the method
1938 * #solve() calls #init() to setup all vectors and internal data structures.
1939 * Most of the other methods within this section are called by #init().
1940 *
1941 * Derived classes should add the initialization of additional
1942 * data structures by overriding this method. Don't forget,
1943 * however, to call SPxSolverBase<R>::init().
1944 */
1945 virtual void init();
1946
1947protected:
1948
1949 /// has the internal data been initialized?
1950 /** As long as an instance of SPxSolverBase is not initialized, no member
1951 * contains setup data. Initialization is performed via method
1952 * #init(). Afterwards all data structures are kept up to date (even
1953 * for all manipulation methods), until #unInit() is called. However,
1954 * some manipulation methods call #unInit() themselfs.
1955 */
1956 bool isInitialized() const
1957 {
1958 return initialized;
1959 }
1960
1961 /// resets clock average statistics
1963
1964 /// uninitialize data structures.
1965 virtual void unInit()
1966 {
1967 initialized = false;
1968 }
1969 /// setup all vecs fresh
1970 virtual void reinitializeVecs();
1971 /// reset dimensions of vectors according to loaded LP.
1972 virtual void reDim();
1973 /// compute feasibility vector from scratch.
1975 ///
1976 virtual void computeFrhsXtra();
1977 ///
1978 virtual void computeFrhs1(const VectorBase<R>&, const VectorBase<R>&);
1979 ///
1981 /// compute \ref soplex::SPxSolverBase<R>::theCoPrhs "theCoPrhs" for entering Simplex.
1982 virtual void computeEnterCoPrhs();
1983 ///
1984 void computeEnterCoPrhs4Row(int i, int n);
1985 ///
1986 void computeEnterCoPrhs4Col(int i, int n);
1987 /// compute \ref soplex::SPxSolverBase<R>::theCoPrhs "theCoPrhs" for leaving Simplex.
1988 virtual void computeLeaveCoPrhs();
1989 ///
1990 void computeLeaveCoPrhs4Row(int i, int n);
1991 ///
1992 void computeLeaveCoPrhs4Col(int i, int n);
1993
1994 /// Compute part of objective value.
1995 /** This method is called from #value() in order to compute the part of
1996 * the objective value resulting form nonbasic variables for #COLUMN
1997 * Representation.
1998 */
2000
2001 /// Get pointer to the \p id 'th vector
2002 virtual const SVectorBase<R>* enterVector(const SPxId& p_id)
2003 {
2004 assert(p_id.isValid());
2005 return p_id.isSPxRowId()
2006 ? &vector(SPxRowId(p_id)) : &vector(SPxColId(p_id));
2007 }
2008 ///
2009 virtual void getLeaveVals(int i,
2010 typename SPxBasisBase<R>::Desc::Status& leaveStat, SPxId& leaveId,
2011 R& leaveMax, R& leavebound, int& leaveNum, StableSum<R>& objChange);
2012 ///
2013 virtual void getLeaveVals2(R leaveMax, SPxId enterId,
2014 R& enterBound, R& newUBbound,
2015 R& newLBbound, R& newCoPrhs, StableSum<R>& objChange);
2016 ///
2017 virtual void getEnterVals(SPxId id, R& enterTest,
2018 R& enterUB, R& enterLB, R& enterVal, R& enterMax,
2019 R& enterPric, typename SPxBasisBase<R>::Desc::Status& enterStat, R& enterRO,
2020 StableSum<R>& objChange);
2021 ///
2022 virtual void getEnterVals2(int leaveIdx,
2023 R enterMax, R& leaveBound, StableSum<R>& objChange);
2024 ///
2025 virtual void ungetEnterVal(SPxId enterId, typename SPxBasisBase<R>::Desc::Status enterStat,
2026 R leaveVal, const SVectorBase<R>& vec, StableSum<R>& objChange);
2027 ///
2028 virtual void rejectEnter(SPxId enterId,
2029 R enterTest, typename SPxBasisBase<R>::Desc::Status enterStat);
2030 ///
2031 virtual void rejectLeave(int leaveNum, SPxId leaveId,
2032 typename SPxBasisBase<R>::Desc::Status leaveStat, const SVectorBase<R>* newVec = nullptr);
2033 ///
2034 virtual void setupPupdate(void);
2035 ///
2036 virtual void doPupdate(void);
2037 ///
2038 virtual void clearUpdateVecs(void);
2039 ///
2040 virtual void perturbMinEnter(void);
2041 /// perturb basis bounds.
2042 virtual void perturbMaxEnter(void);
2043 ///
2044 virtual void perturbMinLeave(void);
2045 /// perturb nonbasic bounds.
2046 virtual void perturbMaxLeave(void);
2047 ///@}
2048
2049 //------------------------------------
2050 /** The following methods serve for initializing the bounds for dual or
2051 * primal Simplex algorithm of entering or leaving type.
2052 */
2053 ///@{
2054 ///
2056 ///
2058 ///
2060 /// setup feasibility bounds for entering algorithm
2062 ///
2063 void setEnterBound4Col(int, int);
2064 ///
2065 void setEnterBound4Row(int, int);
2066 ///
2067 virtual void setEnterBounds();
2068 ///
2069 void setLeaveBound4Row(int i, int n);
2070 ///
2071 void setLeaveBound4Col(int i, int n);
2072 ///
2073 virtual void setLeaveBounds();
2074 ///@}
2075
2076 //------------------------------------
2077 /** Compute the primal ray or the farkas proof in case of unboundedness
2078 * or infeasibility.
2079 */
2080 ///@{
2081 ///
2082 void computePrimalray4Col(R direction, SPxId enterId);
2083 ///
2084 void computePrimalray4Row(R direction);
2085 ///
2086 void computeDualfarkas4Col(R direction);
2087 ///
2088 void computeDualfarkas4Row(R direction, SPxId enterId);
2089 ///@}
2090
2091public:
2092
2093 //------------------------------------
2094 /** Limits and status inquiry */
2095 ///@{
2096 /// set time limit.
2098 /// return time limit.
2099 virtual Real terminationTime() const;
2100 /// set iteration limit.
2101 virtual void setTerminationIter(int iteration = -1);
2102 /// return iteration limit.
2103 virtual int terminationIter() const;
2104 /// set objective limit.
2105 virtual void setTerminationValue(R value = R(infinity));
2106 /// return objective limit.
2107 virtual R terminationValue() const;
2108 /// get objective value of current solution.
2109 virtual R objValue()
2110 {
2111 return value();
2112 }
2113 /// get all results of last solve.
2114 Status
2115 getResult(R* value = 0, VectorBase<R>* primal = 0,
2116 VectorBase<R>* slacks = 0, VectorBase<R>* dual = 0,
2117 VectorBase<R>* reduCost = 0);
2118
2119protected:
2120
2121 /**@todo put the following basis methods near the variable status methods!*/
2122 /// converts basis status to VarStatus
2124
2125 /// converts VarStatus to basis status for rows
2127 const;
2128
2129 /// converts VarStatus to basis status for columns
2131 const;
2132
2133public:
2134
2135 /// gets basis status for a single row
2137
2138 /// gets basis status for a single column
2140
2141 /// get current basis, and return solver status.
2142 Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize = -1,
2143 const int colsSize = -1) const;
2144
2145 /// gets basis status
2147 {
2148 return SPxBasisBase<R>::status();
2149 }
2150
2151 /// check a given basis for validity.
2153
2154 /// set the lp solver's basis.
2155 void setBasis(const VarStatus rows[], const VarStatus cols[]);
2156
2157 /// set the lp solver's basis status.
2159 {
2160 if(m_status == OPTIMAL)
2161 m_status = UNKNOWN;
2162
2164 }
2165
2166 /// setting the solver status external from the solve loop.
2168 {
2169 m_status = stat;
2170 }
2171
2172 /// get level of dual degeneracy
2173 // this function is used for the improved dual simplex
2175
2176 /// get number of dual norms
2177 void getNdualNorms(int& nnormsRow, int& nnormsCol) const;
2178
2179 /// get dual norms
2180 bool getDualNorms(int& nnormsRow, int& nnormsCol, R* norms) const;
2181
2182 /// set dual norms
2183 bool setDualNorms(int nnormsRow, int nnormsCol, R* norms);
2184
2185 /// pass integrality information about the variables to the solver
2186 void setIntegralityInformation(int ncols, int* intInfo);
2187
2188 /// reset cumulative time counter to zero.
2190 {
2191 theCumulativeTime = 0.0;
2192 }
2193
2194 /// get number of bound flips.
2195 int boundFlips() const
2196 {
2197 return totalboundflips;
2198 }
2199
2200 /// get number of dual degenerate pivots
2202 {
2203 return (rep() == ROW) ? enterCycles : leaveCycles;
2204 }
2205
2206 /// get number of primal degenerate pivots
2208 {
2209 return (rep() == ROW) ? leaveCycles : enterCycles;
2210 }
2211
2212 /// get the sum of dual degeneracy
2214 {
2215 return dualDegenSum;
2216 }
2217
2218 /// get the sum of primal degeneracy
2220 {
2221 return primalDegenSum;
2222 }
2223
2224 /// get number of iterations of current solution.
2225 int iterations() const
2226 {
2227 return basis().iteration();
2228 }
2229
2230 /// return number of iterations done with primal algorithm
2232 {
2233 assert(iterations() == 0 || primalCount <= iterations());
2234 return (iterations() == 0) ? 0 : primalCount;
2235 }
2236
2237 /// return number of iterations done with primal algorithm
2239 {
2240 return iterations() - primalIterations();
2241 }
2242
2243 /// return number of iterations done with primal algorithm
2245 {
2246 return polishCount;
2247 }
2248
2249 /// time spent in last call to method solve().
2250 Real time() const
2251 {
2252 return theTime->time();
2253 }
2254
2255 /// returns whether current time limit is reached; call to time() may be skipped unless \p forceCheck is true
2256 ///
2257 bool isTimeLimitReached(const bool forceCheck = false);
2258
2259 /// the maximum runtime
2261 {
2262 return maxTime;
2263 }
2264
2265 /// cumulative time spent in all calls to method solve().
2267 {
2268 return theCumulativeTime;
2269 }
2270
2271 /// the maximum number of iterations
2273 {
2274 return maxIters;
2275 }
2276
2277 /// return const lp's rows if available.
2278 const LPRowSetBase<R>& rows() const
2279 {
2280 return *this->lprowset();
2281 }
2282
2283 /// return const lp's cols if available.
2284 const LPColSet& cols() const
2285 {
2286 return *this->lpcolset();
2287 }
2288
2289 /// copy lower bound VectorBase<R> to \p p_low.
2290 void getLower(VectorBase<R>& p_low) const
2291 {
2292 p_low = SPxLPBase<R>::lower();
2293 }
2294 /// copy upper bound VectorBase<R> to \p p_up.
2295 void getUpper(VectorBase<R>& p_up) const
2296 {
2297 p_up = SPxLPBase<R>::upper();
2298 }
2299
2300 /// copy lhs value VectorBase<R> to \p p_lhs.
2301 void getLhs(VectorBase<R>& p_lhs) const
2302 {
2303 p_lhs = SPxLPBase<R>::lhs();
2304 }
2305
2306 /// copy rhs value VectorBase<R> to \p p_rhs.
2307 void getRhs(VectorBase<R>& p_rhs) const
2308 {
2309 p_rhs = SPxLPBase<R>::rhs();
2310 }
2311
2312 /// optimization sense.
2314 {
2315 return this->spxSense();
2316 }
2317
2318 /// returns statistical information in form of a string.
2319 std::string statistics() const
2320 {
2321 std::stringstream s;
2322 s << basis().statistics()
2323 << "Solution time : " << std::setw(10) << std::fixed << std::setprecision(
2324 2) << time() << std::endl
2325 << "Iterations : " << std::setw(10) << iterations() << std::endl;
2326
2327 return s.str();
2328 }
2329
2330 ///@}
2331
2332 //------------------------------------
2333 /** Mapping between numbers and Ids */
2334 ///@{
2335 /// RowId of \p i 'th inequality.
2336 SPxRowId rowId(int i) const
2337 {
2338 return this->rId(i);
2339 }
2340 /// ColId of \p i 'th column.
2341 SPxColId colId(int i) const
2342 {
2343 return this->cId(i);
2344 }
2345 ///@}
2346
2347 //------------------------------------
2348 /** Constructors / destructors */
2349 ///@{
2350 /// default constructor.
2351 explicit
2355 // virtual destructor
2357 ///@}
2358
2359 //------------------------------------
2360 /** Miscellaneous */
2361 ///@{
2362 /// check consistency.
2363 bool isConsistent() const;
2364 ///@}
2365
2366 //------------------------------------
2367 /** assignment operator and copy constructor */
2368 ///@{
2369 /// assignment operator
2371 /// copy constructor
2373 ///@}
2374
2375 void testVecs();
2376};
2377
2378//
2379// Auxiliary functions.
2380//
2381
2382/// Pretty-printing of variable status.
2383template <class R>
2384std::ostream& operator<<(std::ostream& os,
2385 const typename SPxSolverBase<R>::VarStatus& status);
2386
2387/// Pretty-printing of solver status.
2388template <class R>
2389std::ostream& operator<<(std::ostream& os,
2390 const typename SPxSolverBase<R>::Status& status);
2391
2392/// Pretty-printing of algorithm.
2393template <class R>
2394std::ostream& operator<<(std::ostream& os,
2395 const typename SPxSolverBase<R>::Type& status);
2396
2397/// Pretty-printing of representation.
2398template <class R>
2399std::ostream& operator<<(std::ostream& os,
2400 const typename SPxSolverBase<R>::Representation& status);
2401
2402/* For Backwards compatibility */
2404
2405} // namespace soplex
2406
2407// For general templated functions
2408#include "spxsolver.hpp"
2409#include "spxsolve.hpp"
2410#include "changesoplex.hpp"
2411#include "leave.hpp"
2412#include "enter.hpp"
2413#include "spxshift.hpp"
2414#include "spxbounds.hpp"
2415#include "spxchangebasis.hpp"
2416#include "spxvecs.hpp"
2417#include "spxwritestate.hpp"
2418#include "spxfileio.hpp"
2419#include "spxquality.hpp"
2420
2421#endif // _SPXSOLVER_H_
Save arrays of arbitrary types.
Dynamic index set.
Definition didxset.h:52
Dynamic sparse vectors.
Safe arrays of data objects.
Definition dataarray.h:75
int info
user information to store values -1, 0, +1
Definition datakey.h:64
bool isValid() const
returns TRUE, iff the DataKey is valid.
Definition datakey.h:101
LP column.
Definition lpcolbase.h:55
(In)equality for LPs.
Definition lprowbase.h:55
Set of LP rows.
Set of strings.
Definition nameset.h:71
Random numbers.
Definition random.h:66
Sparse Linear Solver virtual base class.
Definition slinsolver.h:53
Basis descriptor.
Definition spxbasis.h:116
Status & status(int i)
Definition spxbasis.h:281
Status & coStatus(int i)
Definition spxbasis.h:296
const Desc & desc() const
Definition spxbasis.h:473
R fillFactor
allowed increase in relative fill before refactorization
Definition spxbasis.h:391
void setStatus(SPxStatus stat)
sets basis SPxStatus to stat.
Definition spxbasis.h:443
R memFactor
allowed total increase in memory consumption before refactorization
Definition spxbasis.h:394
SPxBasisBase(Timer::TYPE ttype=Timer::USER_TIME)
default constructor.
SLinSolver< R > * factor
Definition spxbasis.h:367
SPxStatus status() const
returns current SPxStatus.
Definition spxbasis.h:437
R nonzeroFactor
allowed increase of nonzeros before refactorization.
Definition spxbasis.h:385
SPxStatus
basis status.
Definition spxbasis.h:102
Bound flipping ratio test ("long step dual") for SoPlex.
Ids for LP columns.
Definition spxid.h:46
Fast shifting ratio test.
Definition spxfastrt.h:54
Generic Ids for LP rows or columns.
Definition spxid.h:95
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
Definition spxid.h:153
bool isSPxRowId() const
is id a row id?
Definition spxid.h:163
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition spxlpbase.h:260
SPxSense spxSense() const
Returns the optimization sense.
Definition spxlpbase.h:554
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition spxlpbase.h:294
SPxSense
Optimization sense.
Definition spxlpbase.h:125
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Definition spxlpbase.h:566
const LPColSetBase< R > * lpcolset() const
Returns the LP as an LPColSetBase.
Definition spxlpbase.h:2140
friend class SPxLPBase
Definition spxlpbase.h:109
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition spxlpbase.h:527
virtual void clearRowObjs()
Clears row objective function values for all rows.
Definition spxlpbase.h:1739
std::shared_ptr< Tolerances > _tolerances
Definition spxlpbase.h:2085
SPxRowId rId(int n) const
Returns the row identifier for row n.
Definition spxlpbase.h:606
const LPRowSetBase< R > * lprowset() const
Returns the LP as an LPRowSetBase.
Definition spxlpbase.h:2134
SPxColId cId(int n) const
Returns the column identifier for column n.
Definition spxlpbase.h:612
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition spxlpbase.h:500
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition spxout.h:78
Abstract pricer base class.
Definition spxpricer.h:57
Abstract ratio test base class.
Ids for LP rows.
Definition spxid.h:65
Sequential object-oriented SimPlex.
Definition spxsolver.h:104
virtual void reLoad()
reload LP.
void setOutstream(SPxOut &newOutstream)
Definition spxsolver.h:486
virtual void changeElement(int i, int j, const R &val, bool scale=false)
SPxId coId(int i) const
id of i 'th covector.
Definition spxsolver.h:1223
bool getDualNorms(int &nnormsRow, int &nnormsCol, R *norms) const
get dual norms
void scaleLeavetol(R d)
scale the leaving tolerance
Definition spxsolver.h:876
virtual R terminationValue() const
return objective limit.
void setSolverStatus(typename SPxSolverBase< R >::Status stat)
setting the solver status external from the solve loop.
Definition spxsolver.h:2167
R entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
Definition spxsolver.h:855
virtual void changeRange(int i, const R &newLhs, const R &newRhs, bool scale=false)
void resetClockStats()
resets clock average statistics
void shiftLPbound(int i, R to)
shift i 'th lpBound to to.
Definition spxsolver.h:1706
virtual void perturbMaxLeave(void)
perturb nonbasic bounds.
void shiftLCbound(int i, R to)
shift i 'th lcBound to to.
Definition spxsolver.h:1722
VectorBase< Real > theUCbound
Definition spxsolver.h:355
bool isCoId(const SPxId &p_id) const
Is p_id a CoId.
Definition spxsolver.h:1250
VectorBase< Real > * theCoLbound
Definition spxsolver.h:385
DSVectorBase< Real > primalRay
Definition spxsolver.h:391
virtual void qualRedCostViolation(R &maxviol, R &sumviol) const
get violation of optimality criterion.
virtual void changeCol(SPxColId p_id, const LPColBase< R > &p_newCol, bool scale=false)
Definition spxsolver.h:1161
VectorBase< Real > * theFrhs
Definition spxsolver.h:367
Pricing
Pricing type.
Definition spxsolver.h:171
int iterations() const
get number of iterations of current solution.
Definition spxsolver.h:2225
virtual void changeElement(SPxRowId rid, SPxColId cid, const R &val, bool scale=false)
Definition spxsolver.h:1169
VectorBase< R > & lcBound()
lower bound for coPvec.
Definition spxsolver.h:1558
UpdateVector< Real > * theFvec
Definition spxsolver.h:369
int primalIterations()
return number of iterations done with primal algorithm
Definition spxsolver.h:2231
const SPxPricer< Real > * pricer() const
Definition spxsolver.h:1877
virtual void changeMaxObj(int i, const R &newVal, bool scale=false)
void updateFtest()
update basis feasibility test vector.
virtual void changeRhs(int i, const R &newRhs, bool scale=false)
bool isInitialized() const
has the internal data been initialized?
Definition spxsolver.h:1956
void testBounds() const
UpdateVector< Real > * theCPvec
Definition spxsolver.h:378
virtual void doRemoveRows(int perm[])
virtual void changeSense(typename SPxLPBase< R >::SPxSense sns)
virtual bool terminate()
Termination criterion.
const VectorBase< R > & ucBound() const
Definition spxsolver.h:1523
void updateCoTest()
recompute coTest vector.
virtual void setTester(SPxRatioTester< R > *tester, const bool destroy=false)
setup ratio-tester to use. If destroy is true, tester will be freed in destructor.
VectorBase< Real > theCoTest
Definition spxsolver.h:388
Type
Algorithmic type.
Definition spxsolver.h:143
bool isBasic(const SPxRowId &rid) const
is the rid 'th vector basic ?
Definition spxsolver.h:1384
void setup4solve(SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
Setup vectors to be solved within Simplex loop.
Definition spxsolver.h:1800
bool isCoBasic(int i) const
is the i 'th covector basic ?
Definition spxsolver.h:1414
SPxStarter< Real > * thestarter
Definition spxsolver.h:411
virtual R value()
current objective value.
bool isBasic(const SPxColId &cid) const
is the cid 'th vector basic ?
Definition spxsolver.h:1390
SolutionPolish getSolutionPolishing()
return objective of solution polishing
Definition spxsolver.h:693
R delta() const
guaranteed primal and dual bound violation for optimal solution, returning the maximum of floatingPoi...
Definition spxsolver.h:886
VarStatus basisStatusToVarStatus(typename SPxBasisBase< R >::Desc::Status stat) const
converts basis status to VarStatus
int boundFlips() const
get number of bound flips.
Definition spxsolver.h:2195
virtual Status getPrimalSol(VectorBase< R > &vector) const
get solution vector for primal variables.
virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper, bool scale=false)
DataArray< int > integerVariables
Definition spxsolver.h:483
const VectorBase< R > & fTest() const
Violations of fVec.
Definition spxsolver.h:1491
virtual void setTerminationValue(R value=R(infinity))
set objective limit.
void shiftPvec()
Perform initial shifting to optain an feasible or pricable basis.
bool setDualNorms(int nnormsRow, int nnormsCol, R *norms)
set dual norms
virtual void computeFrhs1(const VectorBase< R > &, const VectorBase< R > &)
virtual R maxInfeas() const
maximal infeasibility of basis
SSVectorBase< Real > * coSolveVector2
Definition spxsolver.h:290
virtual void qualBoundViolation(R &maxviol, R &sumviol) const
get violations of bounds.
Pricing pricing() const
return current Pricing.
Definition spxsolver.h:556
const SVSetBase< Real > * thecovectors
Definition spxsolver.h:345
void useFullPerturbation(bool full)
perturb entire problem or only the bounds relevant to the current pivot
Definition spxsolver.h:986
virtual void changeMaxObj(SPxColId p_id, const R &p_newVal, bool scale=false)
overloading a virtual function
Definition spxsolver.h:1058
VarStatus getBasisColStatus(int col) const
gets basis status for a single column
virtual void changeObj(SPxColId p_id, const R &p_newVal, bool scale=false)
overloading a virtual function
Definition spxsolver.h:1048
SPxStarter< R > * starter() const
return current starter.
Definition spxsolver.h:562
void setPrimalBounds()
setup feasibility bounds for entering algorithm
void setup4solve2(SSVectorBase< R > *p_y2, SSVectorBase< R > *p_rhs2)
Setup vectors to be solved within Simplex loop.
Definition spxsolver.h:1814
int getDisplayFreq()
get display frequency
Definition spxsolver.h:921
virtual void setStarter(SPxStarter< R > *starter, const bool destroy=false)
setup starting basis generator to use. If destroy is true, starter will be freed in destructor.
Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get current basis, and return solver status.
void getLhs(VectorBase< R > &p_lhs) const
copy lhs value VectorBase<R> to p_lhs.
Definition spxsolver.h:2301
virtual Status getSlacks(VectorBase< R > &vector) const
get VectorBase<R> of slack variables.
bool updateNonbasicValue(R objChange)
void hyperPricing(bool h)
enable or disable hyper sparse pricing
void clearDualBounds(typename SPxBasisBase< R >::Desc::Status, R &, R &) const
bool isConsistent() const
check consistency.
virtual void changeCol(int i, const LPColBase< R > &newCol, bool scale=false)
virtual void perturbMaxEnter(void)
perturb basis bounds.
virtual void ungetEnterVal(SPxId enterId, typename SPxBasisBase< R >::Desc::Status enterStat, R leaveVal, const SVectorBase< R > &vec, StableSum< R > &objChange)
void setup4coSolve(SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
Setup vectors to be cosolved within Simplex loop.
Definition spxsolver.h:1828
SPxPricer< Real > * thepricer
Definition spxsolver.h:409
virtual void computeLeaveCoPrhs()
compute theCoPrhs for leaving Simplex.
bool isRowBasic(int i) const
is the i 'th row vector basic ?
Definition spxsolver.h:1396
int coDim() const
codimension.
Definition spxsolver.h:1186
bool isId(const SPxId &p_id) const
Is p_id an SPxId ?
Definition spxsolver.h:1241
virtual void perturbMinEnter(void)
virtual Status getRedCostSol(VectorBase< R > &vector) const
get vector of reduced costs.
DataArray< VarStatus > oldBasisStatusRows
Definition spxsolver.h:323
DataArray< VarStatus > & getOldBasisStatusCols()
Definition spxsolver.h:947
virtual bool precisionReached(R &newpricertol) const
is the solution precise enough, or should we increase delta() ?
virtual Real terminationTime() const
return time limit.
virtual void qualSlackViolation(R &maxviol, R &sumviol) const
get the residuum |Ax-b|.
virtual void changeRhs(const VectorBase< R > &newRhs, bool scale=false)
void setSolvingForBoosted(bool value)
Definition spxsolver.h:953
virtual void clearRowObjs()
Definition spxsolver.h:1073
virtual void setTolerances(std::shared_ptr< Tolerances > newTolerances)
set the _tolerances member variable
Definition spxsolver.h:493
void resetCumulativeTime()
reset cumulative time counter to zero.
Definition spxsolver.h:2189
bool isTimeLimitReached(const bool forceCheck=false)
returns whether current time limit is reached; call to time() may be skipped unless forceCheck is tru...
UpdateVector< R > & pVec() const
pricing vector.
Definition spxsolver.h:1584
void setMemFactor(R f)
set refactor threshold for memory growth in current factor update compared to the last factorization
Definition spxsolver.h:526
void setDisplayFreq(int freq)
set display frequency
Definition spxsolver.h:915
void forceRecompNonbasicValue()
Definition spxsolver.h:725
virtual void changeLhs(SPxRowId p_id, const R &p_newLhs, bool scale=false)
Definition spxsolver.h:1122
void setSparsePricingFactor(R fac)
Definition spxsolver.h:933
const SVectorBase< R > & vector(const SPxRowId &rid) const
Definition spxsolver.h:1269
void setup4coSolve2(SSVectorBase< R > *p_z, SSVectorBase< R > *p_rhs)
Setup vectors to be cosolved within Simplex loop.
Definition spxsolver.h:1840
SPxBasisBase< R >::SPxStatus getBasisStatus() const
gets basis status
Definition spxsolver.h:2146
const SVectorBase< R > & vector(const SPxId &p_id) const
VectorBase<R> associated to p_id.
Definition spxsolver.h:1294
void setRep(Representation p_rep)
switch to ROW or COLUMN representation if not already used.
virtual void reinitializeVecs()
setup all vecs fresh
SPxRowId rowId(int i) const
RowId of i 'th inequality.
Definition spxsolver.h:2336
const SVectorBase< R > & coVector(int i) const
i 'th covector of LP.
Definition spxsolver.h:1307
UpdateVector< Real > * theRPvec
Definition spxsolver.h:377
DataArray< VarStatus > & getOldBasisStatusRows()
Definition spxsolver.h:941
virtual Status solve(volatile bool *interrupt=nullptr, bool polish=true)
solve loaded LP.
void setMetricInformation(int type)
print basis metric within the usual output
Definition spxsolver.h:927
virtual void setEnterBounds()
R coTest(int i, typename SPxBasisBase< R >::Desc::Status stat) const
test coVector i with status stat.
void setRedCost(VectorBase< R > &p_vector)
virtual const SVectorBase< R > * enterVector(const SPxId &p_id)
Get pointer to the id 'th vector.
Definition spxsolver.h:2002
void computePvec()
compute entire pVec().
void computeTest()
compute test VectorBase<R> in ENTERing Simplex.
VectorBase< R > & ucBound()
upper bound for coPvec.
Definition spxsolver.h:1537
void invalidateBasis()
invalidates the basis, triggers refactorization
virtual void setLeaveBounds()
virtual void changeUpper(int i, const R &newUpper, bool scale=false)
virtual void changeLowerStatus(int i, R newLower, R oldLower=0.0)
VarStatus getBasisRowStatus(int row) const
gets basis status for a single row
virtual void getEnterVals(SPxId id, R &enterTest, R &enterUB, R &enterLB, R &enterVal, R &enterMax, R &enterPric, typename SPxBasisBase< R >::Desc::Status &enterStat, R &enterRO, StableSum< R > &objChange)
const SVSetBase< Real > * thevectors
Definition spxsolver.h:344
void computeCoTest()
compute coTest vector.
SPxId id(int i) const
id of i 'th vector.
Definition spxsolver.h:1204
SPxSolverBase(Type type=LEAVE, Representation rep=ROW, Timer::TYPE ttype=Timer::USER_TIME)
default constructor.
virtual void setupPupdate(void)
virtual void changeObj(const VectorBase< R > &newObj, bool scale=false)
scale determines whether the new data needs to be scaled according to the existing LP (persistent sca...
virtual R objValue()
get objective value of current solution.
Definition spxsolver.h:2109
void setDual(VectorBase< R > &p_vector)
SPxBasisBase< R >::Desc::Status covarStatus(int i) const
Status of i 'th covariable.
Definition spxsolver.h:1363
R perturbMin(const UpdateVector< R > &uvec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, const typename SPxBasisBase< R >::Desc::Status *stat, int start, int incr)
bool enter(SPxId &id, bool polish=false)
void setEnterBound4Row(int, int)
void computeDualfarkas4Row(R direction, SPxId enterId)
const VectorBase< R > & coTest() const
violations of coPvec.
Definition spxsolver.h:1571
virtual bool read(std::istream &in, NameSet *rowNames=nullptr, NameSet *colNames=nullptr, DIdxSet *intVars=nullptr)
read LP from input stream.
void getRhs(VectorBase< R > &p_rhs) const
copy rhs value VectorBase<R> to p_rhs.
Definition spxsolver.h:2307
virtual void factorize()
Factorize basis matrix.
Representation rep() const
return the current basis representation.
Definition spxsolver.h:544
Timer::TYPE getTiming()
set timing type
Definition spxsolver.h:904
void calculateProblemRanges()
determine ranges of problem values for bounds, sides and objective to assess numerical difficulties
bool isColBasic(int i) const
is the i 'th column vector basic ?
Definition spxsolver.h:1402
virtual void doRemoveCols(int perm[])
bool isTerminationValueEnabled() const
true if objective limit should be used in the next solve
Definition spxsolver.h:699
virtual void changeUpper(SPxColId p_id, const R &p_newUpper, bool scale=false)
overloading virtual function
Definition spxsolver.h:1098
R sumPrimalDegeneracy()
get the sum of primal degeneracy
Definition spxsolver.h:2219
virtual void changeRowObj(int i, const R &newVal, bool scale=false)
R getDegeneracyLevel(VectorBase< R > degenvec)
get level of dual degeneracy
const SLinSolver< R > * slinSolver() const
return loaded SLinSolver.
Definition spxsolver.h:1882
void computeEnterCoPrhs4Row(int i, int n)
const VectorBase< R > & lpBound() const
Definition spxsolver.h:1610
virtual void setBasisSolver(SLinSolver< R > *slu, const bool destroy=false)
setup linear solver to use. If destroy is true, slusolver will be freed in destructor.
void setFillFactor(R f)
set refactor threshold for fill-in in current factor update compared to fill-in in last factorization
Definition spxsolver.h:520
int numCycle() const
actual number of degenerate simplex steps encountered so far.
Definition spxsolver.h:980
void unscaleLPandReloadBasis()
unscales the LP and reloads the basis
virtual void loadLP(const SPxLPBase< R > &LP, bool initSlackBasis=true)
copy LP.
virtual void changeLower(SPxColId p_id, const R &p_newLower, bool scale=false)
Definition spxsolver.h:1086
SPxColId colId(int i) const
ColId of i 'th column.
Definition spxsolver.h:2341
bool isBasic(int i) const
is the i 'th vector basic ?
Definition spxsolver.h:1408
virtual void changeRange(SPxRowId p_id, const R &p_newLhs, const R &p_newRhs, bool scale=false)
Definition spxsolver.h:1145
UpdateVector< R > & fVec() const
feasibility vector.
Definition spxsolver.h:1429
VectorBase< R > & upBound()
upper bound for pVec.
Definition spxsolver.h:1603
int subversion() const
return the internal subversion of SPxSolverBase as number
Definition spxsolver.h:539
virtual void changeMaxObj(const VectorBase< R > &newObj, bool scale=false)
virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs, bool scale=false)
const SVectorBase< R > & coVector(const SPxId &p_id) const
coVector associated to p_id.
Definition spxsolver.h:1334
R computePvec(int i)
compute and return pVec()[i].
void scaleEntertol(R d)
scale the entering tolerance
Definition spxsolver.h:871
DSVectorBase< Real > dualFarkas
Definition spxsolver.h:392
void setNonzeroFactor(R f)
set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
Definition spxsolver.h:514
void computeFrhs()
compute feasibility vector from scratch.
VectorBase< Real > coWeights
Definition spxsolver.h:467
void scaleTolerances(R d)
Definition spxsolver.h:880
R perturbMax(const UpdateVector< R > &uvec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, const typename SPxBasisBase< R >::Desc::Status *stat, int start, int incr)
R nonbasicValue()
Compute part of objective value.
virtual void changeUpper(const VectorBase< R > &newUpper, bool scale=false)
virtual void setPricer(SPxPricer< R > *pricer, const bool destroy=false)
setup pricer to use. If destroy is true, pricer will be freed in destructor.
SSVectorBase< Real > * coSolveVector2rhs
Definition spxsolver.h:292
SPxSolverBase(const SPxSolverBase< R > &base)
copy constructor
virtual bool noViols(R tol) const
check for violations above tol and immediately return false w/o checking the remaining values
virtual void init()
intialize data structures.
SSVectorBase< Real > * solveVector3
Definition spxsolver.h:286
void shiftUBbound(int i, R to)
shift i 'th ubBound to to.
Definition spxsolver.h:1682
UpdateVector< Real > * theCoPvec
Definition spxsolver.h:373
void setType(Type tp)
set LEAVE or ENTER algorithm.
const SPxRatioTester< R > * ratiotester() const
return loaded SPxRatioTester.
Definition spxsolver.h:1887
int dualIterations()
return number of iterations done with primal algorithm
Definition spxsolver.h:2238
virtual void computeEnterCoPrhs()
compute theCoPrhs for entering Simplex.
const SVectorBase< R > & coVector(const SPxColId &cid) const
Definition spxsolver.h:1320
R test(int i, typename SPxBasisBase< R >::Desc::Status stat) const
test VectorBase<R> i with status stat.
const SPxBasisBase< R > & basis() const
Return current basis.
Definition spxsolver.h:1867
virtual void factorizeAndRecompute()
const SVectorBase< R > & vector(const SPxColId &cid) const
Definition spxsolver.h:1277
bool leave(int i, bool polish=false)
virtual void perturbMinLeave(void)
int version() const
return the version of SPxSolverBase as number like 123 for 1.2.3
Definition spxsolver.h:534
Status getResult(R *value=0, VectorBase< R > *primal=0, VectorBase< R > *slacks=0, VectorBase< R > *dual=0, VectorBase< R > *reduCost=0)
get all results of last solve.
void getNdualNorms(int &nnormsRow, int &nnormsCol) const
get number of dual norms
R epsilon() const
values are considered to be 0.
Definition spxsolver.h:850
virtual void reDim()
reset dimensions of vectors according to loaded LP.
void setPricing(Pricing pr)
set FULL or PARTIAL pricing.
void setEnterBound4Col(int, int)
VectorBase< R > & lbBound()
lower bound for fVec, writable.
Definition spxsolver.h:1478
DataArray< int > isInfeasibleCo
Definition spxsolver.h:452
void localAddCols(int start)
DataArray< int > isInfeasible
Definition spxsolver.h:450
SSVectorBase< Real > * solveVector3rhs
Definition spxsolver.h:288
void computeFtest()
compute basis feasibility test vector.
void shiftFvec()
Perform initial shifting to optain an feasible or pricable basis.
void setSlacks(VectorBase< R > &p_vector)
virtual void unInit()
uninitialize data structures.
Definition spxsolver.h:1965
void setLeaveBound4Row(int i, int n)
int maxCycle() const
maximum number of degenerate simplex steps before we detect cycling.
Definition spxsolver.h:975
virtual void changeLower(int i, const R &newLower, bool scale=false)
void setStoreBasisFreqForBoosting(int freq)
Definition spxsolver.h:959
void localAddRows(int start)
SSVectorBase< Real > * solveVector2rhs
Definition spxsolver.h:284
UpdateVector< Real > primVec
Definition spxsolver.h:348
int polishIterations()
return number of iterations done with primal algorithm
Definition spxsolver.h:2244
VectorBase< R > & lpBound()
lower bound for pVec.
Definition spxsolver.h:1624
virtual void clear()
clear all data in solver.
int dim() const
dimension of basis matrix.
Definition spxsolver.h:1181
SolutionPolish
objective for solution polishing
Definition spxsolver.h:233
void shiftUCbound(int i, R to)
shift i 'th ucBound to to.
Definition spxsolver.h:1714
void perturbMax(const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
const LPRowSetBase< Real > & rows() const
Definition spxsolver.h:2278
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusCol(int col, VarStatus stat) const
converts VarStatus to basis status for columns
SPxBasisBase< R > & basis()
Definition spxsolver.h:1872
VectorBase< Real > theLCbound
Definition spxsolver.h:356
virtual void printDisplayLine(const bool force=false, const bool forceHead=false)
print display line of flying table
void computeDualfarkas4Col(R direction)
virtual Status getDualfarkas(VectorBase< R > &vector) const
get dual farkas proof of infeasibility.
void setSolutionPolishing(SolutionPolish _polishObj)
set objective of solution polishing (0: off, 1: max_basic_slack, 2: min_basic_slack)
Definition spxsolver.h:687
void toggleTerminationValue(bool enable)
toggle objective limit for next solve
Definition spxsolver.h:705
virtual void changeLhs(int i, const R &newLhs, bool scale=false)
void setBasis(const VarStatus rows[], const VarStatus cols[])
set the lp solver's basis.
R sumDualDegeneracy()
get the sum of dual degeneracy
Definition spxsolver.h:2213
void updateTest()
recompute test vector.
virtual void setTerminationTime(Real time=infinity)
set time limit.
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusRow(int row, VarStatus stat) const
converts VarStatus to basis status for rows
VectorBase< Real > * theCoUbound
Definition spxsolver.h:384
VectorBase< Real > weights
Definition spxsolver.h:466
void computeLeaveCoPrhs4Row(int i, int n)
const SVectorBase< R > & coVector(const SPxRowId &rid) const
Definition spxsolver.h:1312
virtual void changeRow(int i, const LPRowBase< R > &newRow, bool scale=false)
VectorBase< Real > theLRbound
Definition spxsolver.h:354
VectorBase< Real > dualRhs
Definition spxsolver.h:349
const VectorBase< R > & lbBound() const
lower bound for fVec.
Definition spxsolver.h:1465
void setPrimal(VectorBase< R > &p_vector)
virtual void changeBounds(int i, const R &newLower, const R &newUpper, bool scale=false)
virtual void setTerminationIter(int iteration=-1)
set iteration limit.
VectorBase< Real > theTest
Definition spxsolver.h:389
virtual void changeLower(const VectorBase< R > &newLower, bool scale=false)
void getUpper(VectorBase< R > &p_up) const
copy upper bound VectorBase<R> to p_up.
Definition spxsolver.h:2295
UpdateVector< R > & coPvec() const
copricing vector.
Definition spxsolver.h:1504
SSVectorBase< Real > * coSolveVector3
Definition spxsolver.h:294
virtual void changeLhs(const VectorBase< R > &newLhs, bool scale=false)
UpdateVector< Real > addVec
Definition spxsolver.h:351
virtual bool writeState(const char *filename, const NameSet *rowNames=nullptr, const NameSet *colNames=nullptr, const bool cpxFormat=false, const bool writeZeroObjective=false) const
VectorBase< Real > * theLbound
Definition spxsolver.h:383
SPxSolverBase< R > & operator=(const SPxSolverBase< R > &base)
assignment operator
SPxRatioTester< Real > * theratiotester
Definition spxsolver.h:410
SSVectorBase< Real > * solveVector2
Definition spxsolver.h:282
virtual void changeUpperStatus(int i, R newUpper, R oldLower=0.0)
void setLeaveBound4Col(int i, int n)
VectorBase< Real > theURbound
Definition spxsolver.h:353
bool isBasisValid(DataArray< VarStatus > rows, DataArray< VarStatus > cols)
check a given basis for validity.
virtual void rejectEnter(SPxId enterId, R enterTest, typename SPxBasisBase< R >::Desc::Status enterStat)
VectorBase< Real > primRhs
Definition spxsolver.h:347
int dualDegeneratePivots()
get number of dual degenerate pivots
Definition spxsolver.h:2201
const VectorBase< R > & ubBound() const
upper bound for fVec.
Definition spxsolver.h:1447
int getMaxIters()
the maximum number of iterations
Definition spxsolver.h:2272
std::string statistics() const
returns statistical information in form of a string.
Definition spxsolver.h:2319
virtual bool readBasisFile(const char *filename, const NameSet *rowNames, const NameSet *colNames)
void shiftLBbound(int i, R to)
shift i 'th lbBound to to.
Definition spxsolver.h:1690
SPxBasisBase< R >::Desc::Status varStatus(int i) const
Status of i 'th variable.
Definition spxsolver.h:1357
SPxLPBase< R >::SPxSense sense() const
optimization sense.
Definition spxsolver.h:2313
virtual void rejectLeave(int leaveNum, SPxId leaveId, typename SPxBasisBase< R >::Desc::Status leaveStat, const SVectorBase< R > *newVec=nullptr)
R computeTest(int i)
compute and return test()[i] in ENTERing Simplex.
const VectorBase< R > & lcBound() const
Definition spxsolver.h:1544
virtual void changeLhsStatus(int i, R newLhs, R oldLhs=0.0)
virtual void changeRowObj(const VectorBase< R > &newObj, bool scale=false)
const VectorBase< R > & test() const
Violations of pVec.
Definition spxsolver.h:1637
const VectorBase< R > & upBound() const
Definition spxsolver.h:1589
Status status() const
Status of solution process.
const SVectorBase< Real > & vector(int i) const
Definition spxsolver.h:1263
int primalDegeneratePivots()
get number of primal degenerate pivots
Definition spxsolver.h:2207
virtual void unShift(void)
remove shift as much as possible.
Type type() const
return current Type.
Definition spxsolver.h:550
virtual R shift() const
total current shift amount.
Definition spxsolver.h:1733
VectorBase< R > & ubBound()
upper bound for fVec, writable.
Definition spxsolver.h:1460
void getLower(VectorBase< R > &p_low) const
copy lower bound VectorBase<R> to p_low.
Definition spxsolver.h:2290
DataArray< VarStatus > oldBasisStatusCols
Definition spxsolver.h:325
Array< UnitVectorBase< Real > > unitVecs
Definition spxsolver.h:343
SSVectorBase< Real > * coSolveVector3rhs
Definition spxsolver.h:296
void computePrimalray4Col(R direction, SPxId enterId)
UpdateVector< Real > * thePvec
Definition spxsolver.h:375
void computePrimalray4Row(R direction)
virtual void clearUpdateVecs(void)
void setIntegralityInformation(int ncols, int *intInfo)
pass integrality information about the variables to the solver
virtual void getLeaveVals(int i, typename SPxBasisBase< R >::Desc::Status &leaveStat, SPxId &leaveId, R &leaveMax, R &leavebound, int &leaveNum, StableSum< R > &objChange)
const VectorBase< R > & coPrhs() const
Right-hand side vector for coPvec.
Definition spxsolver.h:1517
virtual void doPupdate(void)
virtual void addedCols(int n)
void computeLeaveCoPrhs4Col(int i, int n)
virtual void addedRows(int n)
virtual void getEnterVals2(int leaveIdx, R enterMax, R &leaveBound, StableSum< R > &objChange)
bool isBasic(typename SPxBasisBase< R >::Desc::Status stat) const
does stat describe a basic index ?
Definition spxsolver.h:1369
bool isBasic(const SPxId &p_id) const
is the p_id 'th vector basic ?
Definition spxsolver.h:1375
virtual void computeFrhsXtra()
void setTiming(Timer::TYPE ttype)
set timing type
Definition spxsolver.h:893
const SVectorBase< R > & unitVector(int i) const
return i 'th unit vector.
Definition spxsolver.h:1342
const std::shared_ptr< Tolerances > & tolerances() const
returns current tolerances
Definition spxsolver.h:508
virtual void changeBounds(SPxColId p_id, const R &p_newLower, const R &p_newUpper, bool scale=false)
Definition spxsolver.h:1109
R leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Definition spxsolver.h:863
virtual void doRemoveCol(int i)
void setBasisStatus(typename SPxBasisBase< R >::SPxStatus stat)
set the lp solver's basis status.
Definition spxsolver.h:2158
void shiftUPbound(int i, R to)
shift i 'th upBound to to.
Definition spxsolver.h:1698
void computeFrhs2(VectorBase< R > &, VectorBase< R > &)
VectorBase< Real > * theUbound
Definition spxsolver.h:382
virtual void changeRow(SPxRowId p_id, const LPRowBase< R > &p_newRow, bool scale=false)
Definition spxsolver.h:1153
virtual void qualConstraintViolation(R &maxviol, R &sumviol) const
get violation of constraints.
virtual void changeObj(int i, const R &newVal, bool scale=false)
const LPColSet & cols() const
Definition spxsolver.h:2284
virtual Status getPrimalray(VectorBase< R > &vector) const
get primal ray in case of unboundedness.
virtual void loadBasis(const typename SPxBasisBase< R >::Desc &)
set a start basis.
Representation
LP basis representation.
Definition spxsolver.h:124
void perturbMin(const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
Real cumulativeTime() const
cumulative time spent in all calls to method solve().
Definition spxsolver.h:2266
virtual void doRemoveRow(int i)
void initRep(Representation p_rep)
initialize ROW or COLUMN representation.
virtual R getBasisMetric(int type)
Definition spxsolver.h:991
virtual void changeRhsStatus(int i, R newRhs, R oldRhs=0.0)
UpdateVector< Real > dualVec
Definition spxsolver.h:350
virtual Status getDualSol(VectorBase< R > &vector) const
get current solution VectorBase<R> for dual variables.
virtual void changeRhs(SPxRowId p_id, const R &p_newRhs, bool scale=false)
Definition spxsolver.h:1134
void computeEnterCoPrhs4Col(int i, int n)
virtual int terminationIter() const
return iteration limit.
VectorBase< Real > theUBbound
Definition spxsolver.h:363
const VectorBase< R > & fRhs() const
right-hand side vector for fVec
Definition spxsolver.h:1442
VectorBase< Real > theLBbound
Definition spxsolver.h:364
VectorBase< Real > * theCoPrhs
Definition spxsolver.h:372
Real getMaxTime()
the maximum runtime
Definition spxsolver.h:2260
virtual void changeRowObj(SPxRowId p_id, const R &p_newVal, bool scale=false)
Definition spxsolver.h:1068
virtual bool writeBasisFile(const char *filename, const NameSet *rowNames, const NameSet *colNames, const bool cpxFormat=false) const
virtual void getLeaveVals2(R leaveMax, SPxId enterId, R &enterBound, R &newUBbound, R &newLBbound, R &newCoPrhs, StableSum< R > &objChange)
SoPlex start basis generation base class.
Definition spxstarter.h:52
Semi sparse vector.
Sparse vector set.
Definition svsetbase.h:73
Sparse vectors.
static Timer * switchTimer(Timer *timer, Timer::TYPE ttype)
Wrapper for the system time query methods.
Definition timer.h:86
TYPE
types of timers
Definition timer.h:109
Dense Vector with semi-sparse Vector for updates.
void setTolerances(std::shared_ptr< Tolerances > &tolerances)
set tolerances
Dense vector.
Definition vectorbase.h:86
Everything should be within this namespace.
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
LPColSetBase< Real > LPColSet
Definition lpcolset.h:36
double Real
Definition spxdefines.h:268
SPxSolverBase< Real > SPxSolver
Definition spxsolver.h:2403
SVectorBase< Real > SVector
Definition svector.h:38
SOPLEX_THREADLOCAL const Real infinity
Random numbers.
Simplex basis.
Debugging, floating point type and parameter definitions.
#define SOPLEX_MAX(x, y)
Definition spxdefines.h:296
#define SOPLEX_SUBVERSION
Definition spxdefines.h:94
#define SOPLEX_VERSION
Definition spxdefines.h:93
Saving LPs in a form suitable for SoPlex.
Saving LPs in a form suitable for SoPlex.
Timer class.
TimerFactory class.
Sparse vector .
Dense VectorBase<R> with semi-sparse VectorBase<R> for updates.