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