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